Массив — это структура данных, которую можно рассматривать как набор переменных одинакового типа, имеющих общее имя. Массивы бывают одномерные и многомерные. Доступ к элементам массива осуществляется по индексу.
Массив в программах должен быть объявлен. Это делается следующим образом:
<имя>: array [<н_индекс>..<в_индекс>] of <тип>;
Здесь <имя> — имя переменной-массива, array — зарезервированное слово языка Паскаль, обозначающее, что переменная является массивом, <н_индекс> и <в_индекс> — соответственно нижний и верхний индексы, которыми являются целые константы, определяющие диапазон изменения индексов элементов одномерного массива (то есть размер массива), <тип> — тип элементов массива.
Под выводом массива понимается вывод всех значений элементов массива.
Под вводом массива понимается получение от пользователя во время работы программы значений элементов массива.
Массив можно задать, используя константы и счетчик случайных чисел, а также вычислять элементы массива по заданным формулам или просто вводить их последовательно.
Для ввода больших массивов удобно использовать специальную функцию-генератор случайных чисел. В языке Паскаль это функция random(х). Вызов ее без аргумента возвращает случайное вещественное число из интервала [0; 1), а вызов с аргументом х, где х — случайное целое число (типа integer) из промежутка [0; n). Случайные целые числа, принадлежащие отрезку [a; b], вычисляют по формуле a + random(b – a + 1). Например, если необходимо случайное число на отрезке [10; 99], функцию random можно записать следующим образом: otr := 10 + random(90);. Эта функция в Паскале обычно используется совместно с процедурой randomize, переустанавливающей базу генерации случайных чисел, то есть позволяющей при последовательных запусках программы получать разные случайные последовательности [13].
Существуют типовые алгоритмы обработки одномерных массивов. Приведем типовые фрагменты программ на языке Паскаль.
Поэлементный ввод:
for i:=1 to n do
readln(mas[i]);
Вывод массива в строку:
for i:=1 to n do
write(mas[i]);
Вывод массива в столбец:
for i:=1 to n do
writeln(mas[i]);
Поиск минимального элемента массива:
min:=1;
for i:=2 to n do
if mas[i]<mas[min] then min:=i;
write('Минимальный элемент массива = ',mas[min]);
Перестановка элементов на четных и нечетных местах:
for i:=1 to n div 2 do
begin
p:=mas[2*i-1];
mas[2*i-1]:=mas[2*i];
mas[2*i]:=p
end;
Объединение двух одномерных массивов с поочередной выборкой:
for i:=1 to n do
begin
mas[2*i-1]:=a[i];
mas[2*i]:=b[i]
end;
Перестановку элементов массива, состоящего из значений 0, 1 и 2, так чтобы расположить сначала все нули, затем все единицы и, наконец, все двойки, можно выполнить без применения дополнительного массива. Можно просто подсчитать количество значений 0, 1, 2 и заполнить массив заново требуемым образом:
var a: array [1..50] of integer;
i,nul,ed,dva,n: integer;
BEGIN
n:=10;
randomize;
for i:=1 to n do
begin
a[i]:=random(3);
write(a[i]:4)
end;
writeln;
nul:=0; ed:=0; dva:=0;
for i:=1 to n do
case a[i] of
0: inc(nul);
1: inc(ed);
2: inc(dva);
end;
for i:=1 to nul do a[i]:=0;
for i:=nul+1 to ed+nul+1 do a[i]:=1;
for i:=ed+nul+1 to n do a[i]:=2;
for i:=1 to n do
write(a[i]:4);
END.
Смена всех элементов Xi и Yi (i = 1, …, n) в однотипных массивах X и Y размерностью n без использования промежуточных величин:
for i:=1 to n do
begin
x[i]:=x[i]+y[i];
y[i]:=x[i]-y[i];
x[i]:=x[i]-y[i]
end;
Практически каждый программист в своей работе сталкивается с необходимостью сортировать данные, иначе говоря, упорядочивать их определенным образом. Существует целый класс алгоритмов сортировки.
Рассмотрим несколько методов сортировки одномерных массивов.
Пусть дан массив из пяти целых чисел. Отсортировать его по возрастанию методом прямого выбора (перебором).
Алгоритм сортировки этим методом будет выглядеть следующим образом.
1. Просмотреть массив, начиная от первого элемента, найти минимальный элемент и поместить его на место первого элемента, а первый — на место минимального.
2. Просмотреть массив, начиная от второго элемента, найти минимальный элемент и поместить его на место второго элемента, а второй — на место минимального и т. д., пока не будет отсортирован весь массив.
Теперь без труда можно написать программу на нужном языке.
Отсортируем тот же массив из пяти целых чисел методом прямого обмена (его называют еще «пузырьковым» методом, или методом перестановки соседних элементов).
Организовать такую перестановку можно следующим образом.
1. Весь массив просматривается с конца (то есть снизу вверх) и в том случае, если из двух соседних элементов «нижний» элемент меньше, чем «верхний», элементы меняются местами. Таким образом самый меньший (самый «легкий») элемент оказывается ближе к началу массива («всплывает»). Отсюда и одно из названий метода — «пузырьковой» сортировки.
3. Операция повторяется для оставшихся элементов и т. д.
Ниже показан соответствующий фрагмент программы:
var a: array [1..5] of integer;
i,j,n,c: integer;
BEGIN
n:=5;
randomize;
for i:=1 to n do
begin
a[i]:=random(15)-3;
write(a[i]:4)
end;
writeln;
for i:=1 to n-1 do
for j:=1 to n-1 do
if a[j]>a[j+1] then
begin
c:=a[j];
a[j]:=a[j+1];
a[j+1]:=c
end;
for i:=1 to n do
write(a[i]:4)
END.
Еще один метод сортировки массива был предложен Д. Л. Шеллом в 1959 году. Основная идея алгоритма заключается в том, чтобы вначале устранить массовый беспорядок в массиве, сравнивая далеко отстоящие друг от друга элементы, и постепенно уменьшить этот интервал до единицы. Это означает, что на последних шагах сортировка сводится просто к перестановкам соседних элементов (если, конечно, такие перестановки необходимы). Фрагмент программы, выполняющий сортировку массива из пяти элементов методом Шелла, выглядит следующим образом:
const n=5;
var a: array[1..n] of integer;
c,k,i,j: integer;
BEGIN
randomize;
for i:=1 to n do
begin
a[i]:=random(15)-3;
write(a[i]:4)
end;
k:=n div 2; {вычисление шага}
while k>0 do begin
for j:=n-k downto 1 do begin
i:=j;
while i<=n-k do begin
if a[i]>a[i+k] then begin
c:=a[i];
a[i]:=a[i+k];
a[i+k]:=c
end;
i:=i+k;
end
end;
k:=k div 2
end;
writeln;
for i:=1 to n do
write(a[i]:4);
END.
Примеры
Пример 1. Составить программу, которая осуществляет перестановку одномерного массива без использования дополнительного массива.
Листинг 1.
const n=20;
var a: array [1..n] of integer;
i,c: integer;
BEGIN
randomize;
for i:=1 to n do
begin
a[i]:=random(30)-4;
write(a[i]:4)
end;
for i:=1 to n div 2 do
begin
c:=a[i];
a[i]:=a[n-i+1];
a[n-i+1]:=c
end;
writeln;
for i:=1 to n do
write(a[i]:4);
writeln
END.
Пример 2. Найти сумму всех элементов массива A, больших заданного числа.
Листинг 2.
var a: array [1..100] of integer;
i,ch,n,s: integer;
BEGIN
randomize;
write('Введите размер массива -> ');
readln(n);
for i:=1 to n do
begin
a[i]:=random(20)-5;
write(a[i]:4)
end;
writeln;
write('Введите число -> ');
readln(ch);
s:=0;
for i:=1 to n do
if a[i]>ch then s:=s+a[i];
writeln('Сумма элементов, больших числа ',ch,' равна ',s)
END.
Пример 3. Заполнить массив, применив для его заполнения следующее значение: .
Листинг 3.
const n=10;
var a: array [1..n] of real;
i: integer;
x: real;
BEGIN
write('Введите значение х -> ');
readln(x);
for i:=1 to n do
begin
a[i]:=x*sqr(i)/(i+x);
write(a[i]:8:4)
end;
END.
Пример 4. В одномерном массиве целых чисел заменить все элементы, меньшие среднего арифметического, значением среднего арифметического, округленного до целого. Массив заполняется случайным образом.
Листинг 4.
const n=10;
var a: array [1..n] of integer;
i,s: integer;
sred: real;
BEGIN
randomize;
s:=0;
for i:=1 to n do
begin
a[i]:=random(20)-5;
write(a[i]:4);
s:=s+a[i];
end;
writeln;
sred:=s/n;
for i:=1 to n do
begin
if a[i]<sred then a[i]:=round(sred);
write(a[i]:4)
end;
writeln
END.
Пример 5. В одномерном массиве целых чисел удалить k-й элемент массива.
Листинг 5.
const n=10;
var a: array [1..n] of integer;
i,k: integer;
BEGIN
randomize;
for i:=1 to n do
begin
a[i]:=random(20)-5;
write(a[i]:4)
end;
writeln;
write('Введите номер элемента для удаления
(k < ',n,')->');
readln(k);
for i:=k to n-1 do
a[i]:=a[i+1];
for i:=1 to n-1 do
write(a[i]:4);
writeln
END.
Пример 6. В одномерном массиве целых чисел удалить элемент, равный заданному числу, если он есть. Если таких элементов несколько, то удалить последний из найденных.
Листинг 6.
const n=10;
var a: array [1..n] of integer;
i,k,kk: integer;
BEGIN
randomize;
for i:=1 to n do
begin
a[i]:=random(20)-5;
write(a[i]:4)
end;
writeln;
write('Введите число ->');
readln(kk);
for i:=1 to n do
if a[i]=kk then k:=i;
for i:=k to n-1 do
a[i]:=a[i+1];
for i:=1 to n-1 do
write(a[i]:4);
writeln
END.
Пример 7. Вставить на k-е место массива целых чисел элемент, равный наименьшему элементу массива.
Листинг 7.
const n=10;
var a: array [1..n+1] of integer;
i,k,min: integer;
BEGIN
randomize;
for i:=1 to n do
begin
a[i]:=random(20)-5;
write(a[i]:4)
end;
writeln;
min:=a[1];
for i:=2 to n do
if a[i]<a[min] then min:=a[i];
write('Введите значение k (k < ',n,') ->');
readln(k);
for i:=n+1 downto k do
a[i]:=a[i-1];
a[k]:=min;
for i:=1 to n+1 do
write(a[i]:4);
writeln
END.
Пример 8. Имеются два одномерных массива целых чисел размера n. Создать из них один одномерный массив, в котором сначала идут отрицательные элементы, затем нулевые и затем положительные.
Решим задачу следующим образом. Соединим два массива в один, а затем упорядочим полученный массив, используя «пузырьковый» метод сортировки.
Листинг 8.
const n=10;
var a,b: array [1..n] of integer;
c: array [1..2*n] of integer;
i,j,k: integer;
BEGIN
randomize;
for i:=1 to n do
begin
a[i]:=random(20)-5;
b[i]:=random(12)
end;
writeln('Массив А');
for i:=1 to n do
write(a[i]:4);
writeln;
writeln('Массив B');
for i:=1 to n do
write(b[i]:4);
writeln;
for i:=1 to n do
c[i]:=a[i];
k:=1;
for i:=n+1 to 2*n do
begin
c[i]:=b[k];
inc(k)
end;
for i:=1 to 2*n-1 do
for j:=1 to 2*n-1 do
if c[j]>c[j+1] then
begin
k:=c[j];
c[j]:=c[j+1];
c[j+1]:=k
end;
writeln('Массив С');
for i:=1 to 2*n do
write(c[i]:4);
writeln
END.
Пример 9. Дан массив чисел. Найти, сколько в нем пары одинаковых соседних элементов [6].
Листинг 9.
const n=10;
var a: array [1..n] of integer;
i,k: integer;
BEGIN
randomize;
for i:=1 to n do
begin
a[i]:=random(20)-5;
write(a[i]:4)
end;
writeln;
k:=0;
for i:=1 to n-1 do
if a[i] = a[i+1] then k:=k+1;
writeln('Одинаковых пар соседних элементов
в массиве ',k)
END.
Пример 10. Даны три одномерных числовых массива A, B, C. Сформировать массив K такой же длины, элементы которого вычисляются по формуле: [15].
Листинг 10.
const n=10;
var a,b,c: array [1..n] of integer;
k: array [1..n] of real;
i: integer;
BEGIN
randomize;
writeln;
writeln('МАССИВ А');
for i:=1 to n do
begin
a[i]:=random(20)-5;
b[i]:=random(30)-2;
c[i]:=random(40);
write(a[i]:4)
end;
writeln;
writeln('МАССИВ В');
for i:=1 to n do
write(b[i]:4);
writeln;
writeln('МАССИВ C');
for i:=1 to n do
write(c[i]:4);
writeln;
writeln('МАССИВ K');
for i:=1 to n do
begin
k[i]:=(a[i]-b[i])/(1+c[i]);
write(k[i]:8:4)
end
END.
Пример 11. Даны натуральные числа A1, A2, …, AN (N = 10). Не создавая дополнительные массивы, определить, какой из элементов повторяется в последовательности A1, A2, …, AN наибольшее число раз, и найти его порядковый номер, ближайший к началу последовательности [32].
Листинг 11.
const n=10;
var a: array [1..n] of integer;
i,j,max,k,q: integer;
BEGIN
randomize;
for i:=1 to n do
begin
a[i]:=random(20);
write(a[i]:4)
end;
writeln;
max:=0;
for i:=1 to n-1 do
begin
k:=1;
for j:=i+1 to n do
if a[i]=a[j] then inc(k);
if k>max then
begin
max:=k;
q:=i
end
end;
write(a[q]:6,q:6,max:6);
writeln
END.
Пример 12. В заполненном наполовину массиве, не создавая дополнительный массив, продублировать все элементы с сохранением порядка их следования. Например, из массива А (1, 2, 3, …) необходимо получить массив (1, 1, 2, 2, 3, 3) [32].
Листинг 12.
const n=5;
var a: array [1..2*n] of integer;
i: integer;
BEGIN
randomize;
for i:=1 to n do
begin
a[i]:=random(20);
write(a[i]:4)
end;
writeln;
i:=2*n;
while (i<=2*n) and (i>=2) do
begin
a[i]:=a[i div 2];
a[i-1]:=a[i];
dec(i,2);
end;
for i:=1 to 2*n do
write(a[i]:4);
writeln
END.
Пример 13. Заданы два одномерных массива различных размеров M и N и число K (K < M). Не создавая дополнительный массив, включить второй массив в первый между K-м и (К+1)-м его элементами [32].
Листинг 13.
const m=5; n=5;
var a: array [1..m+n] of integer;
b: array [1..n] of integer;
i,k: integer;
BEGIN
randomize;
write('Введите значение k -> ');
readln(k);
for i:=1 to m do
begin
a[i]:=random(20)-2;
write(a[i]:4)
end;
writeln;
for i:=1 to n do
begin
b[i]:=random(15)+4;
write(b[i]:4)
end;
writeln;
for i:=m+n downto (m+n)-(m-k)+1 do
a[i]:=a[i-n];
for i:=1 to n do
a[k+i]:=b[i];
for i:=1 to m+n do
write(a[i]:4);
writeln
END.
Пример 14. Сообщество роботов живет по следующим законам: один раз в год они объединяются в группы по 3 или 5 роботов; за год группа из 3 роботов собирает 5, а группа из 5 — 9 новых собратьев; каждый робот живет 3 года после сборки. Известно начальное количество роботов (K > 7), все они только что собраны. Определить, сколько роботов будет через N лет. [13]
Листинг 14.
var k,n,i,r: byte;
new: LongInt;
d,q: array [-2..100] of LongInt;
BEGIN
write('Введите начальное кол-во роботов и кол-во лет -> ');
readln(k,n);
write('Всего роботов: ');
if k<3 then
if n in [0,1,2] then write(k) else write ('0')
else
begin
d[-2]:=0; d[-1]:=0; d[0]:=k; q[0]:=k;
for i:=1 to n do
begin
r:=q[i-1] mod 5;
new:=q[i-1] div 5*9+r;
if r in [3,4] then inc(new,5-r);
d[i]:=new;
q[i]:=q[i-1]+new-d[i-3]
end;
write(q[n])
end;
END.
Пример 15. Даны натуральные числа А1, …, А10. Предположим, что имеется 10 видов монет достоинством А1, …, А10. Обозначим через N число способов, которыми можно выплатить сумму K этими монетами, то есть N — это число решений уравнения A1X1 + … + A10X10 = K, где Xi может принимать целые неотрицательные значения. Требуется найти N [32].
Листинг 15.
label 1;
var a,b,c: array [1..10] of integer;
i,j,n,s,k: integer;
BEGIN
write('Введите сумму -> ');
readln(k);
for i:=1 to 10 do
begin
write('a[',i,'] = ');
readln(a[i])
end;
for i:=1 to 10 do
b[i]:=k div a[i];
n:=0;
for i:=1 to 10 do
c[i]:=0;
1: s:=0;
for i:=1 to 10 do
s:=s+a[i]*c[i];
if s=k then inc(n);
for i:=10 downto 1 do
begin
if c[i]=b[i] then
for j:=i to 10 do
c[j]:=0 else
begin
c[i]:=c[i]+1;
goto 1
end;
end;
writeln('N = ',n);
END.
Пример 16. Составить программу для вычисления полинома y = 2x8 – x6 – 4x5 – 5x2 + 6x + 1, используя формулу Горнера [5].
Формула Горнера для полинома n-й степени y = a1xn + a2xn–1 + … + anx + an+1 выглядит следующим образом:
y = (…((a1x + a2)x + a3)x + … + an)x + an+1
Листинг 16.
var a: array [1..10] of real;
md,i: integer;
x,y: real;
BEGIN
write('Введите старшую степень полинома
(она не должна быть больше 9) -> ');
readln(md);
writeln('Введите коэффициенты полинома
(начиная с коэффициента при
свободном члене) ');
for i:=1 to md do
read(a[i]);
y:=a[1];
for i:=2 to md do
begin
x:=i;
y:=y*x+a[i]
end;
writeln(y:8:6);
END.
Пример 17. Заданный массив А сдвинуть циклически на m элементов вправо [7].
При циклическом сдвиге вправо выталкиваемые элементы с конца массива заполняют освобождающиеся места в начале массива. Например, при сдвиге вправо на 3 разряда массива А (1, 2, 3, 4, 5, 6, 7) получаем массив А (5, 6, 7, 1, 2, 3, 4).
Рассмотрим два варианта. В первом варианте используется дополнительный массив того же размера, что и исходный. Во втором варианте используется дополнительная память только для одного элемента массива.
Листинг 17.1.
const n=5;
var a,b: array [1..n] of integer;
i,c,k: integer;
BEGIN
write('На сколько элементов сдвигать вправо? -> ');
readln(c);
for i:=1 to n do
begin
a[i]:=random(20)-3;
write(a[i]:4)
end;
writeln;
for i:=1 to n do
begin
k:=(i+c-1) mod n+1;
b[k]:=a[i]
end;
for i:=1 to n do
write(b[i]:4)
END.
Листинг 17.2.
const n=5;
var a: array [1..n] of integer;
i,c,k,j: integer;
BEGIN
write('На сколько сдвигать вправо -> ');
readln(c);
for i:=1 to n do
begin
a[i]:=random(20)-3;
write(a[i]:4)
end;
writeln;
for i:=1 to c do
begin
k:=a[n];
for j:=n downto 2 do
a[j]:=a[j-1];
a[1]:=k
end;
for i:=1 to n do
write(a[i]:4);
END.
Пример 18. Билет с шестизначным цифровым номером считается «счастливым», если сумма трех старших цифр совпадает с сумой трех младших цифр. В предположении, что в билетной кассе находится миллион билетов с номерами от 000000 до 999999, надо определить количество потенциально осчастливленных пассажиров [18].
Можно организовать шесть вложенных циклов, в каждом из которых перебирается очередная цифра номера. В самом внутреннем цикле можно проверять суммы старших и младших цифр номера и вести подсчет счастливых билетов, но такая проверка нерациональна. Гораздо меньше операций можно проделать, если подсчитать, сколько раз сумма трех цифр равна 0, 1, 2, …, 27.
.
[15].