Справочник «Типовые алгоритмы и задачи обработки одномерных массивов»

№

Типовой алгоритм

Программная реализация

(Паскаль)

1

Заполнение массива

Program z1;

const n=10;

var a: array [1..n] of …;

i:integer;

begin

for i:=1 to n do

readln (a[i]);

…

2

Вывод в строку

…

for i:=1 to n do

write (a[i]);

…

3

Сумма, произведение элементов

…

s:=0; p:=1;

for i:=1 to n do

begin

s:=s+a[i]; p:=p+a[i];

end;

…

3

Выбор по условию

…

k:=0; s:=0; p:=1;

for i:=1 to n do

if {условие} then

begin

k=k+1; s:=s+a[i]; p:=p+a[i];

end;

write (k,s,p);

…

4

Максимальный (минимальный) элемент

…

max:=a[1]; min:=a[1];

for i:=2 to n do

begin

if a[i]>max then max:=a[i];

if a[i]<min then min:=a[i];

№

Типовой алгоритм

Программная реализация

(Паскаль)

end;

…

4.1

Замена максимального из обработанных чисел на предыдущее максимальное число

const n=5;

a: array [1..n] of integer=(1,2,2,-6,11);

var i,b,c: integer;

begin

b:=a[1];

for i:=2 to n do

if a[i]>=b then

begin

c:=b;

b:=a[i];

a[i]:=c;

end;

for i:=1 to n do write (a[i]:3)

end.

4.2

Нахождение индекса минимального элемента в массиве (если их несколько, то выводится последний)

const n=5;

a: array [1..n] of integer=(5,-7,14,14,-7);

var i,b,c: integer;

begin

b:=a[1];с:=1;

for i:=2 to n do

if a[i]<=b then

begin

b:=a[i];

c:=i;

end;

writeln(c);

end.

№

Типовой алгоритм

Программная реализация

(Паскаль)

4.3

Синоптики фиксировали дневные температуры в течение всего года. Найти

максимальную годовую температуру и следующую за ней по величине температуру

const n=365;

var

mas: array [1..n] of integer;

i,max1,max2: integer;

begin

randomize;

for i := 1 to n do

mas[i]:= -20 + random(40);

if mas[1] < mas[2] then

begin

max1:= mas[2];max2:=mas[1]

end

else

begin

max1:= mas[1];max2:=mas[2]

end

for i:= 3 to n do

if max1 < mas[i] then

begin

max2:=max1;max1:=mas[i]

end

else if max2 < mas[i] then

max2:=mas[i];

writeln(max1:3,max2:3)

end.

4.4

Опишите алгоритм поиска номера первого из двух последовательных элементов в целочисленном массиве из 30 элементов, сумма которых максимальна

const N = 30;

var a:array[1..N] of integer;

MaxSum, MaxNum, i: integer;

begin

MaxNum := 1;

MaxSum := a[1] + a[2];

for i:= 2 to N–1 do

begin

if a[i] + a[i + 1] > MaxSum then

№

Типовой алгоритм

Программная реализация

(Паскаль)

(если таких пар несколько, то можно выбрать любую из них)

begin

MaxNum:=i;

MaxSum:=a[i] + a[i +1]

end

end;

writeln(MaxNum)

end.

5

Вставка

…

for i:=n downto k do

a[i+1]:=a[i];

a[k]:=x;

…

6

Удаление

…

for i:=k to (n-1) do

a[i]:= a[i+1];

…

7

Cортировка методом «пузырька»

…

for j:=n downto 2 do

for i:=1 to j-1 do

if a[i]>a[i+1] then

begin

x:= a[i]; a[i]:= a[i+1]; a[i+1]:=x;

end;

…

7.1

Дан ряд целых случайных чисел. Преобразовать его в ряд чисел, между которыми можно было бы поставить знаки «<» и «>» в чередующемся порядке.

…

{сортируеммассив}

for j:=n downto 2 do

for i:=1 to j-1 do

if a[i]>a[i+1] then

begin

x:= a[i]; a[i]:= a[i+1]; a[i+1]:=x;

end;

x:=1;

{меняем местами пару чисел}

№

Типовой алгоритм

Программная реализация

(Паскаль)

for i:=1 to (n div 2) do

begin

x:=a[j]; a[j]:= a[j+1]; a[j+1]:=x; j:=j+2;

end;

for i:=1 to n do

writeln (a[i]);

…

7.2

В последовательности чисел выделить все подпоследовательности подряд идущих чисел

…

{сортируеммассив}

for j:=n downto 2 do

for i:=1 to j-1 do

if a[i]>a[i+1] then

begin

x:= a[i]; a[i]:= a[i+1]; a[i+1]:=x;

end;

write (a[1]);

for i:=2 to n do

begin

if (a[i]-a[i-1])<>1 then writeln;

write (a[i]);

end;

…

7.3

В последовательности чисел найти и вывести подпоследовательность подряд идущих чисел наибольшей длины

…

{сортируеммассив}

for j:=n downto 2 do

for i:=1 to j-1 do

if a[i]>a[i+1] then

begin

x:= a[i]; a[i]:= a[i+1]; a[i+1]:=x;

end;

max:=0;

k:=1;

for i:=1 to n-1 do

№

Типовой алгоритм

Программная реализация

(Паскаль)

begin

if a[i+1]-a[i]=1 then k:=k+1

else k:=1;

if k>max then

begin

max:=k;

number:=i+1;

end;

end;

writeln (‘максимальная длина =’, max);

writeln (‘самая длинная последовательность =’);

for i:=( number – max + 1) to do

writeln (a[i]);

…

7.4

МассивA заполнен положительными и отрицательными целыми числами. Необходимо отсортировать положительные элементы по возрастанию, отрицательные - оставить на своих местах (вводится доп.массив В, который заполняется индексами положительных элементов массива А)

…

j:=1;

k:=0;

for i:=1 to n do

if a[i]>0 then

begin

b(j):=i;

j:=j+1; k:=k+1;

end;

for j:=k downto 2 do

for i:=1 to j-1 do

if a[b[i]]>a[b[i+1]] then

begin

x:=a[b[i]];

a[b[i]]:= a[b[i+1]];

a[b[i+1]]:=x;

end;

for i:=1 to n do write (a[i],’’);

…

№

Типовой алгоритм

Программная реализация

(Паскаль)

8

Задачи на «Индекс и значение элемента массива»

8.1

Вывести на экран значения всех элементов массива MAS с четными индексами

…

for i:=1 to n do

begin

k:=i mod 2;

if k=0 then write (mas[i]:4);

end;

…

8.2

Вычислить сумму элементов массива MAS с нечетными значениями

…

S:=0;

for i:=1 to n do

begin

k:=mas[i] mod 2;

if k<>0 then s:=s+mas[i];

end;

writeln (‘сумма элементов с неч.индексами=’,s);

…

8.3

Обнулить значения отрицательных элементов массива MAS с четными индексами

…

for i:=1 to n do

begin

k:=i mod 2;

if (k=0) and (mas[i]<0) then mas[i]:=0;

write (mas[i]:4);

end;

…

8.4

В элемент массива, находящийся ровно в центре массива, занести значение суммы двух соседних элементов

…

var

mas: array [m..n] of integer;

…

r:= (n+m) div 2;

mas[r]:= mas[r-1] + mas[r+1];

…

№

Типовой алгоритм

Программная реализация

(Паскаль)

8.5

В элемент массива, находящийся ровно в центре массива, занести значение суммы крайних элементов

…

var

mas: array [m..n] of integer;

…

r:= (n+m) div 2;

mas[r]:= mas[m] + mas[n];

…

8.6

В элемент массива, находящийся ровно в центре массива, занести значение модуля разности крайних элементов

…

var

mas: array [m..n] of integer;

…

r:= (n+m) div 2;

mas[r]:= abs(mas[m] - mas[n]);

…

8.7

Каждому i-му элементу массива присвоить сумму первых iэлементов массива

const n=5;

a: array [1..n] of integer=(-1,2,5,4,1);

var i: integer;

begin

for i:=2 to n do

a[i]:= a[i]+ a[i-1];

for i:=1 to n do

writeln (a[i]:3);

end.

8.8

Подсчитать количество элементов массива, значение которых равно их индексу

const n=5;

a: array [1..n] of integer=(2,2,3,3,4);

var i,c: integer;

begin

c:=0;

for i:=1 to n do

if a[i]=i then c:=c+1;

writeln (c);

end.

№

Типовой алгоритм

Программная реализация

(Паскаль)

8.9

Удвоить каждый элемент массива, совпадающий со своим индексом

const n=5;

a: array [1..n] of integer=(2,-8,3,77,7);

var i: integer;

begin

for i:=1 to n do

if a[i]=i then a[i]:= a[i]+i;

for i:=1 to n do

writeln (a[i]:3);

end.

8.10

Умножить на -1 каждый элемент массива, стоящего на четном месте

const n=5;

a: array [1..n] of integer=(5,15,9,8,-77);

var i: integer;

begin

for i:=1 to n do

if i mod 2 = 0 then a[i]:= a[i]*(-1);

for i:=1 to n do

writeln (a[i]:3);

end.

8.11^*

Значения массива сдвинуть циклически вправо на одну позицию так, чтобы последний элемент стал первым

const n=10;

var

i,t: integer;

x: array [1..n] of integer;

begin

…

t:=x[n];

for i:=n downto 2 do

x[i]:= x[i-1];

x[1]:=t;

…

end.

8.12^*

Программа циклического сдвига значений массива вправо на k позиций,

const n=10;

var

a: array [1..n] of integer;

k,t,p: integer;

№

Типовой алгоритм

Программная реализация

(Паскаль)

подмассиве от (i+1) до n. В худшем случае, если все элементы в массиве различны, операция сравнения выполняется n(n-1)/2 раз.)

b := b and (a[i] <> a[j]);

inc(j)

end;

inc(i)

end;

writeln(b);

readln

end.

№

Типовой алгоритм

Программная реализация

(Паскаль)

где n>k (идея: запишем в обратном порядке первые n-k элементов, затем в обратном порядке последние kэлементов, а затем перепишем в обратном порядке весь измененный массив)

begin

{заполнениемассива}

for p:=1 to (n-k) div 2 do

begin

t:= a[p];

a[p]:=a[(n-k)-p+1];

a[(n-k)-p+1]:=t

end;

for p:=1 to k div 2 do

begin

t:= a[n-k+p];

a[n-k+p]:= a[n-p+1];

a[n-p+1]:=t

end;

for p:=1 to n div 2 do

begin

t:=a[p];

a[p]:=a[n-p+1];

a[n-p+1]:=t

end

end.

8.13^*

Массив (размерности n) «сожмите», выбросив из него каждый второй элемент. «Освободившиеся» места в правой части массива заполните нулями. Дополнительный массив не использовать

const n=10;

a: array [1..n] of

byte=(1,2,3,4,5,6,7,8,9,10);

var i,j,k: integer;

begin

k:=0;

i:=1;

while i<=n do

begin

a[i - i div 2]:= a[i];

{перемещаем элемент с чётным индексом на «своё» место}

i:=i+2;

№

Типовой алгоритм

Программная реализация

(Паскаль)

end;

for i:= n – n div 2 + 1 to n do

a[i]:=0;

{последние (n-ndiv 2 + 1) элементы обнуляем}

for i:=1 to n do writeln (a[i]:3);

readln

end.

8.14^*

Дан массив, содержащий нулевые элементы. «Сожмите» его, передвинув нулевые элементы в конец массива. Дополнительный массив не использовать

const n=10;

a: array [1..n] of

byte=(1,0,0,2,0,3,4,7,0,1);

var i,k: integer;

begin

k:=0;

i:=1;

for i:=1 to n do

begin

if a[i]=0 then inc (k)

{подсчитываем количество нулей в части массива от 1 до i}

elsea[i-k]:=a[i];

{перемещаем ненулевой элемент на первое свободное место}

end;

for i:=n-k+1 to n do a[i]:=0;

{освободившиесяместазаполняемнулями}

for i:= 1 to n do writeln (a[i]:2);

readln

end.

8.15

На атомной электростанции система каждую секунду записывает свои показания. Если хотя бы одно из показаний, записанных

const n=60;

var i: integer;

mas:array[1..n] of integer;

flag:boolean;

{флаг, который отвечает за равенство

элементов}

begin

№

Типовой алгоритм

Программная реализация

(Паскаль)

в течение минуты, отличается от предыдущих, значит в системе произошёл сбой и необходимо изменить настройки. Проверить, надо ли менять настройки системы

randomize;

for i:=1 to n do

mas[i]:=random(2);

flag:=true;

{предполагаем, что все значения равны}

i:=2;

while (i <= n) and flag do

{цикл выполняется до тех пор, пока не будут

обработаны все элементы или пока не

найдется такой элемент, который не будет

равенпредыдущим}

begin

flag:=mas[i–1]=mas[i];

{проверка элементов на равенство

предыдущему}

ins(i)

end;

if flag then writeln(‘системаработаетнормально’)

elsewriteln(‘надо проверить систему’);

readln

end.

8.16

В базе данных хранятся номера сотрудников, которым была выписана премия за месяц. Проверить, не попал ли кто-либо из сотрудников в эту базу дважды. (С помощью внутреннего цикла мы проверяем, не встречается ли обрабатываемый элемент a[i] в

const n = 10;

a: array [1..n] of byte =

(1,2,3,4,5,6,7,8,9,10);

var i, j: integer;

b: boolean;

begin

i := 1;

b := true;

while (i <= n – 1) and b do

begin

j := i + 1;

while (j <= n) and b do

begin