Одномерные массивы

Массив - это структура, представляющая собой упорядоченную совокупность элементов одного типа, объединенных одним именем.
Определение
Каждому массиву, используемому в программе, выделяется место в памяти.
Массиву отводится не одна ячейка, а последовательность расположенных друг за другом ячеек, в каждую из которых записывается значение соответствующего элемента.

Индекс массива - это величина целого типа, характеризующая положение элемента в массиве.
Определение
Для получения доступа к элементу массива используется индекс
1 2 3 4 5 6 7

1 2 3 4 5 6 7
А
A [ 4 ] := 11;
Имя массива
Индекс (порядковый номер) элемента массива
Значение элемента массива
Определение 1

Объявление массивов
Зачем объявлять?
определить имя массива
определить тип массива
определить число элементов
выделить место в памяти
Массив целых чисел:
Размер через константу:
имя
начальный индекс
конечный индекс
тип
элементов
var A: array[1.. ] of integer;
const N=5;
N
var A : array[ 1 .. 5 ] of integer ;

Описание массива
Var имя:ARRAY[1..N] OF тип;
Объявление массива в разделе описания переменных:
Например:
Var A:Array[1..10] of Integer;
Var Tem:Array[1..100] of Real;
Имя массива
Количество элементов
Тип элементов

Объявление массивов
Массивы других типов:
Другой диапазон индексов:
Индексы других типов:
var X, Y: array [1..10] of real;
C: array [1..20] of char;
var Q: array [0..9] of real;
C: array [-5..13] of char;
var A: array ['A'..'Z'] of real;
B: array [False..True] of integer;
...
A['C'] := 3.14259*A['B'];
B[False] := B[False] + 1;

Type t=array[1..10] of integer;
Var a : t;
Const
m=10;
Var a : array [1.. m] of integer;
Количество элементов можно описать в разделе констант
Иногда массив объявляют как пользовательский тип данных
Описание массива

Сonst a:array[1..5] of integer =
(3,-2,1,4,3);
Массив констант
Описание массива
Var N:Array ['A'..'Z'] of Integer;
Var R:Array [-20..20] of Real;
В зависимости от задачи индексы элементов могут начинаться не только с единицы или быть символьного типа

Что неправильно?
var a: array[10..1] of integer;
...
A[5] := 4.5;
[1..10]
var a: array ['z'..'a'] of integer;
...
A['B'] := 15;
A['b']
['a'..'z']
var a: array [0..9] of integer;
...
A[10] := 'X';

Массивы
Объявление:
Ввод с клавиатуры:
Поэлементные операции:
Вывод на экран:
const N = 5;
var a: array[1..N] of integer;
i: integer;
for i:=1 to N do begin
write('a[', i, ']=');
read ( a[i] );
end;
a[1] =
a[2] =
a[3] =
a[4] =
a[5] =
5
12
34
56
13
for i:=1 to N do a[i]:=a[i]+1;
writeln('Массив A:');
for i:=1 to N do write(a[i]:4);
Массив A:
6 13 35 57 14

1. Заполнение массива с клавиатуры
For i:=1 to N do begin
Write(' a [ ' , i , ' ] = ' );
ReadLn ( a [ i ] );
End;
Заполнение массива

2. Заполнение массива случайными числами.
m[i]:=RANDOM (А)
случайное число из интервала [0; А)
m[i] :=RANDOM(B-A)+A;
случайное число из интервала [A ; B)
m[i] :=RANDOM(B-A+1)+A;
случайное число из интервала [A ; B]
Заполнение массива
Например:
Случайное число из интервала [-5 ; 8).
А = - 5, В = 8,
подставим в формулу
m[i] :=RANDOM(B-A)+A;
m[i] :=RANDOM(8-(-5))+(-5);
такую запись нужно упростить
m[i] :=RANDOM(13)-5;
For i:=1 to N do begin
a[i]:=Random(B-A)+A;
WriteLn(a[i]:10:5);
End;

3. Заполнение массива при помощи прогрессии.
Заполнить массив числами 3,5,7,9,11 и т.д.
На первом месте стоит 3
На втором 3+2 = 5
На третьем 5+2 = 7 и т.д.
То есть ai = ai - 1 + 2
Это арифметическая прогрессия.
Заполнение массива
a[1]:=3;
Writeln(a[1]);
For i:=2 to N do begin
a[i]:=a[i-1] + 2;
Writeln(a[i]:5);
End;

а) в столбик:
For i:=1 to N do Writeln(a[i]:4:2);
б) в строку
For i:=1 to N do Write(a[i]:4:2);
2.23
3.19
1.44
4.93
5.58
2.23 3.19 1.44 4.93 5.58
Вывод массива

Вывод массива в две строки
Задача 1. Заполнить массив из 10 элементов случайными числами из интервала от -10 до 10, вывести на экран, а затем увеличить каждый элемент массива на 1 и повторно вывес­ти на экран.
var A:array [1..10] of integer;
i:integer;
Begin
Clrscr;
for i:=1 to 10 do begin
a[i]:= random(21)-10;
write(a[i]:5);
end;
writeln;
for i:=1 to 10 do begin
a[i]:=a[i]+1;
write(a[i]:5);
end;
end.
Оператор вывода без LN, вывод осуществляется в строку
Пустой оператор вывода с LN, когда первая строка закончена, переход на вторую
Оператор вывода без LN, вывод осуществляется в строку

Вывод массива в две строки
1
Пустой Writeln между циклами обычно в блок-схеме не изображают.
Разрыв блок-схемы, если она целиком на лист не убирается

Заполнение массива
Задача 2. Составить программу заполняющую массив из 10 элементов, числовой последовательностью: 1,4,9,16…
Program n2;
Uses Crt;
var a:array[1..10] of integer;
i:integer;
begin
clrscr;
for i:=1 to 10 do begin
a[i]:=i*i;
write(a[i]:5);
end;
end.
Значение элемента массива зависит только от порядкового номера

Заполнение массива
Задача 3. Составить программу заполняющую массив из 10 элементов, числовой последовательностью: 2, 3, 5, 9, 17 и т.д.
Uses Crt;
var a:array[1..10] of integer;
i:integer;
begin
clrscr;
a[1]:=2;
write(a[1]:5);
for i:=2 to 10 do begin
a[i]:=2*a[i-1]-1;
write(a[i]:5);
end;
end.
Значение элемента массива зависит от предшествующего элемента

Задания
«3»: Ввести c клавиатуры массив из 5 элементов, умножить их на 2 и вывести на экран.
Пример:
Введите пять чисел:
4 15 3 10 14
Результат: 8 30 6 20 28
«4»: Ввести c клавиатуры массив из 5 элементов, найти среднее арифметическое всех элементов массива.
Пример:
Введите пять чисел:
4 15 3 10 14
среднее арифметическое 9.200

Задания
«5»: Ввести c клавиатуры массив из 5 элементов, найти минимальный из них. Пример:
Введите пять чисел:
4 15 3 10 14
минимальный элемент 3

Практикум: заполнение массива
«3»: 1. Заполните массив A нулями.
2. Заполните массив A первыми N натуральными числами, начиная с 1.
3. Заполните массив A первыми N натуральными числами, начиная с X (ввести X с клавиатуры).
«4»: 4. Заполните массив A первыми N натуральными числами, начиная с X (ввести X с клавиатуры).
5. Заполнить массив A первыми N числами Фибоначчи. Первые два числа Фибоначчи равны единице, а каждое последующее число Фибоначчи вычисляется как сумма двух предыдущих.
«5»: 6. Заполните массив степенями числа 2, так чтобы последний элемент массива был равен 1, а каждый предыдущий был в 2 раза больше следующего. Например: 32 16 8 4 2 1
7. Заполните массив целыми числами, так чтобы средний элемент массива был равен X, слева от него элементы стоят по возрастанию, а справа – по убыванию (ввести X с клавиатуры). Соседние элементы отличаются на единицу. Например: 1 2 3 2 1.

Практикум: изменение элементов массива
«3»:
1. Увеличить все элементы массива A на 1.
2. Умножить все элементы массива A на 2.
3. Возвести в квадрат все элементы массива A.
«4»:
4. Увеличить на 4 все элементы в первой половине массива A (считать, что в массиве чётное число элементов).
5. Разделить на 2 все элементы массива A, кроме первого и последнего (считать, что в массиве есть, по крайней мере, два элемента и все элементы чётные).
«5»:
6. Умножить на 3 все элементы во второй половине массива A (считать, что в массиве чётное число элементов).
7. Найти среднее арифметическое всех элементов массива A.

Изменение элементов массива удовлетворяющих условию
For i:=1 to N do If (условие) then a[i]:=значение:
Условия:
a [ i ] > 0 – положительный элемент массива
a [ i ] Mod 2 = 0 – четный элемент массива
a [ i ] = int(a [ i ]) – целый элемент массива
a [ i ] = i – элемент массива равен своему порядковому номеру
i Mod 2 = 0 – четные порядковые номера
a [ i ] = К – элемент массива равный числу К
Изменения:
a [ i ] :=5 – заменить i-ый элемент на число 5
a [ i ] := - a [ i ] – заменить i-ый элемент на противоположный по знаку
a [ i ] := a [ i ] * 2 – удвоить каждый элемент массива
a [ i ] := a [ i - 1]+3 –заменить i-ый элемент предшествующим плюс 3
Обработка массива

Нахождение суммы элементов массива удовлетворяющих условию:
s:=0;
For i:=1 to N do If (условие) then s:=s+ a[i];
WriteLn ('Сумма = ', s:10:5);
Нахождение суммы и произведения элементов массива
Предполагаем, что сумма равна нулю
Если элемент подходит по условию, добавляем его к сумме
Нахождение произведения элементов массива удовлетворяющих условию:
p:=1;
For i:=1 to N do If (условие) then p:=p* a[i];
WriteLn('Произведение = ', p:10:5);
Если элемент подходит по условию, добавляем его к произведению
Предполагаем, что произведение равно единице

Подсчет количества элементов удовлетворяющих условию:
k:=0;
For i:=1 to N do If (условие) then k:=k+1;
WriteLn('Кол-во=',k:10);
Предполагаем, что таких элементов нет
Если такой элемент есть, то К увеличиваем на 1.
Подсчет количества элементов удовлетворяющих условию

Задача 4. Дан массив из 15 целых чисел заполненный случайными числами из интервала [0; 20]. Выведите этот массив в строку и найдите количество четных элементов массива, которые меньше среднего арифметического его элементов.
ClrScr;
s:=0;
For i:=1 to 15 do begin
a[i]:=Random(21);
write (a[i]:10);
S:=S+a[i];
end;
Предполагаем, что сумма равна нулю
Организуем цикл из 15 повторений
Нахождение суммы элементов массива
Определяем число случайным образом
Выводим его на экран
Добавляем к сумме

Writeln;
s:=s/15;
Writeln('Среднее арифметическое = ',s:10:5);
k:=0;
For i:=1 to 15 do
if (a[i] Mod 2 = 0) and (a[i]
Writeln('Четных чисел меньших среднего арифметического ', k:8);
Находим среднее арифметическое
Выводим его на экран
Предполагаем, что таких элементов нет
Организуем цикл из 15 повторений
Если элемент четный и меньше среднего арифметического, увеличиваем К на единицу
Выводим К на экран
Нахождение суммы элементов массива

Нахождение максимального элемента в массиве и его номера:
max:=a[1];
k:=1;
for i:=2 to N do if (a[i]>max) then begin
max:=a[i];
k:=i;
end;
WriteLn(‘Max=’,max:10:5);
WriteLn(‘Номер=’,k:5);
Предполагаем, что наибольший элемент стоит на первом месте
Если находится больший элемент
Он становится максимальным
Когда массив закончился, выводим наибольший элемент и его номер
Максимальный и минимальный элемент массива

max:= 1;
for i:=2 to N do if a[i] > a[max] then max:=i;
writeln('Максимальный элемент ',а[max]);
writeln('Его номер ', Max);
Иногда в задаче достаточно определить индекс наибольшего элемента
Максимальный и минимальный элемент массива
Предполагаем, что наибольший элемент стоит на первом месте
Если i-ый элемент больше стоящего на месте max
то, запоминаем его индекс в переменной max

1.Дан массив из 100 элементов заполненный случайными целыми числами из интервала [-100, 100]. Найдите наибольший элемент среди четных элементов массива.
Решение задач
2. Дан массив А размера N, введенный с клавиатуры и заполненный нулями и единицами. Найти наибольшее количество идущих подряд единиц.
3. Даны два массива А и В размера N, введенные с клавиатуры. Сформировать новый массив С по правилу: на нечетных местах стоят элементы массива А, а на четных местах стоят элементы массива В.
4. Дан массив А размера N, заданный случайным образом [-100, 100]. Сформировать новый массив B из отрицательных элементов массива А.

Вставка элементов удовлетворяющих условию в другой массив. Пусть нам дан массив с именем А, а переместить элементы нужно в массив В
j:=0;
For i:=1 to N do
if (а[i]…) then begin
j:=j+1;
b[j]:=a[i];
end;
K:=j;
Порядковый номер элемента в массиве В
Если элемент из А удовлетворяет условию
То, увеличиваем количество элементов в В, и под этим индексом помещаем элемент из А
Количество элементов в массиве В будет равно последнему порядковому номеру перенесенного элемента
Выбор элементов массива в другой массив

Вставка элемента с номером p в последовательность
For i:=N downto p do a[i+1]:=a[i];
a[p]:=значение;
N:=N+1;
За каждый оборот цикла смещаем элементы на один номер в право.
Вставка и удаление элементов массива
Перебираем элементы от последнего до места на которое нужно вставить,
На место с индексом Р ставим нужное значение и увеличиваем на 1 количество элементов
9
14
11
12
7
100
N
p
9

Написать программу к задаче:
Сформировать массив из 20 элементов случайным образом на отрезке [-100,100]. Вывести его на экран. Вставить перед каждым отрицательным элементом массива 0. Вывести измененный массив на экран.
Вставка и удаление элементов массива

Заполнение массива 30
Задача 7. Вставить перед каждым отрицательным элементом массива 0.
i:=1; n:=10;
while i<=n do
begin
if a[i]<0 then begin
for j:=n downto i do a[j+1]:=a[j];
a[i]:=0; i:=i+2; n:=n+1;
end
else i:=i+1;
end;

Удаление элемента с номером p из массива:
for i:=p to (N-1) do a[i]:=a[i+1];
N:=N-1;
Вставка и удаление элементов массива
Перебираем элементы от места которое удаляем до предпоследнего элемента
Уменьшаем на 1 количество элементов
За каждый оборот цикла смещаем элементы на один номер в лево.
14
11
12
7
p
9
N
100

Написать программу к задаче:
Сформировать массив из 20 элементов случайным образом на отрезке [-100,100]. Вывести его на экран. Удалить из массива все нулевые элементы .
Вставка и удаление элементов массива

Удалить из массива все нулевые элементы:
1 способ
j:=1;
While j<=N do
begin
If a[j]=0 then begin
k:=j
for i:=k to (N-1) do a[i]:=a[i+1];
N:=N-1;
end
else j:=j+1;
end;
Вставка и удаление элементов массива

Удалить из массива все нулевые элементы:
2 способ
For i:=N downto 1 do If a[i]=0 then begin
for k:=i to (N-1) do a[k]:=a[k+1];
N:=N-1;
end;
Вставка и удаление элементов массива

Поиск трех минимальных элементов в неповторяющемся массиве
min1 :=maxint; min2 :=maxint; min3 := maxint;
for i:=1 to N do begin
if p[i] < min1 then begin { новый min1 }
min3 := min2; min2 := min1;
min1 := p[i]; end
else if p[i] < min2 then begin { новый min2 }
min3 := min2;
min2 := p[i]; end
else if p[i] < min3 then { новый min3 }
min3 := p[i];
end;

min1:=maxint; min2:=maxint; min3:= maxint;
for i:=1 to N do begin
if a[i] < min1 then begin
min3:=min2; min2:=min1; min1:=a[i]; end
else if (a[i] < min2) and (a[i]<>min1) then begin min3:= min2; min2:=a[i]; end
else if (a[i] < min3) and (a[i]<>min2) and (a[i]<>min1) then
min3 := a[i];
end; writeln;
writeln('min1=',min1,' min2=',min2,' min3=',min3);

Задача 5. Дан массив из 10 целых, положительных не повторяющихся чисел. Проверить образуют ли его элементы арифметическую прогрессию. Если образуют, то вывести разность прогрессии.
// заполнить массив
r:= a[2]-a[1];
flag:=true;
For i:=2 to 9 do if (a[i+1]-a[i]<>r) then flag:=false;
If flag then Begin
Writeln('Арифметическая прогрессия');
Writeln('Разность = ',r:8);
End
else
Writeln('Не арифметическая прогрессия');
Проверка массива 27
Находим разность между первым и вторым элементом
Предполагаем, что массив – арифметическая прогрессия
Организуем цикл от второго до предпоследнего элемента
Если находится пара элементов, у которых другая разность, то это не арифметическая прогрессия
Если значение истинно
То выводим разность и соответствующее сообщение
Иначе – выводим соответствующее сообщение

Начало
Проверка массива 28
r:= a2-a1;
flag:=true
i, 2, 9
ai+1-ai ≠ r
flag:=false
flag=true
1
Вывод:
Прогрессия
Вывод:
Не прогрессия
Конец
Заполнение массива и вывод его на экран
1
Нет
Нет
Да
Да
Цикл в котором проверяется разность между соседними элементами
Условие проверяющее изменилась ли переменная Flag

Задача 6. Дан массив из 10 случайных чисел из интервала от -10 до 10. Найти номер первого отрицательного элемента (Он обязательно существует)
Поиск элемента 29
// заполнить массив
i:=1;
while (a[i]>=0) do i:=i+1;
write('Первое отрицательное ',a[i]:4);
Пока элемент массива положителен или ноль берем следующий элемент

Заполнение массива 30
Задача 7. Заполнить массив из 10 элементов случайными числами из интервала [0; 10), так, чтобы числа не повторялись.
For i:=1 to 10 do
begin
repeat
r:=false;
a[i]:=random(10);
for j:=1 to i-1 do if a[i]=a[j] then r:=true;
until r=false;
write(a[i]:5);
end;

Заполнение массива 30
Задача 7. Заполнить массив из 10 элементов случайными числами из интервала [0; 10), так, чтобы числа не повторялись.
For i:=1 to 10 do
begin
repeat
flag:=false;
a[i]:=random(10);
for j:=1 to i-1 do if a[i]=a[j] then flag:=true;
until flag=false;
write(a[i]:5);
end;
Цикл отвечающий за количество чисел в массиве
Цикл возвращающий процесс назад если такое число уже было
Цикл в котором проверяется не встречалось ли такое число

Заполнение массива 31
i,1,10
flag=false
a i = случайное[0;10)
j, 1, i-1
ai=a j
flag=true
flag=false
Вывод
a i
Да
Нет
Да
Нет
Цикл возвращающий процесс назад если такое число уже было
Цикл отвечающий за количество чисел в массиве
Цикл в котором проверяется не встречалось ли такое число

Сортировка массива методом пузырька
Идея – самый маленький («легкий» элемент перемещается вверх («всплывает»).

Сортировка массива метод пузырька
for j:=1 to n-1 do begin
for i:=1 to n-j do
if a[i]
a[i]:=a[i+1];
a[i+1]:=c;
end;
Сортировка по убыванию

Метод выбора (минимального элемента)
Идея: найти минимальный элемент и поставить его на первое место.
for i:= 1 to N-1 do begin
{ найти номер nMin минимального элемента из A[i]..A[N] }
if i <> nMin then begin
{ поменять местами A[i] и A[nMin] }
end
end;

Метод выбора (минимального элемента)
for i:= 1 to N-1 do begin
if i <> nMin then begin
{ поменять местами A[i] и A[nMin] }
end
end;
nMin:= i;
for j:=i+1 to N do
if A[j] < A[nMin] then
nMin:= j;

Сортировка вставками
Идея: сначала упорядочиваются два элемента, затем делается вставка третьего элемента относительно двух первых. Затем вставка четвертого относительно трех первых и т.д.
for i:=2 to N do
begin
k:=a[i]; j:=i-1;
while (j>=1) and (a[j]>k) do
begin
a[j+1]:=a[j]; j:=j-1;
end;
a[j+1]:=k;
end;

Задачи
«A»: Массив содержит четное количество элементов. Напишите программу, которая сортирует первую половину массива по возрастанию, а вторую – по убыванию. Каждый элемент должен остаться в «своей» половине.
Пример:
Массив:
5 3 4 2 1 6 3 2
После сортировки:
2 3 4 5 6 3 2 1

Задачи
«B»: Напишите программу, которая сортирует массив и находит количество различных чисел в нем.
Пример:
Массив:
5 3 4 2 1 6 3 2 4
После сортировки:
1 2 2 3 3 4 4 5 6
Различных чисел: 5
«C»: Напишите программу, которая сравнивает число перестановок элементов при использовании сортировки «пузырьком» и методом выбора. Проверьте ее на разных массивах, содержащих 1000 случайных элементов, вычислите среднее число перестановок для каждого метода.

Сортировка массива выбором (поиск минимального или максимального)
Общая идея алгоритма:
Берем i-ый элемент
Последовательно сравниваем его со всеми элементами справа
Если находится элемент меньший чем i-ый, то они меняются местами
Так на i-ом месте окажется самый маленький элемент
i увеличиваем на единицу и повторяем процесс…

Сортировка выбором
элементов массива по возрастанию
For i:=1 to N-1 do
For j:=i to N do
if (a[i]>a[j]) then begin
p:=a[i];
a[i]:=a[j];
a[j]:=p;
end;
Сортировка массива
Перебираем элементы от первого до предпоследнего
Перебираем от i-ого элемента до конца
Если в оставшейся строке находится элемент меньше чем i-ый …
То меняем их местами
Сортировка массива:
4; -2; 6; -5
по возрастанию с изменениями происходящими в массиве

Сортировка массива
Упорядочить по возрастанию: 4 -2 6 -5