SHPORA.net :: PDA

Login:
регистрация

Main
FAQ

гуманитарные науки
естественные науки
математические науки
технические науки
Search:
Title: | Body:

Одномерные Массивы. Операции с Массивами




ВВЕДЕНИЕ В МАССИВЫ



Понятие массива



Чтобы определить понятие “массив”, сначала необходимо обратиться к понятию “простая переменная”.

Простая переменная - это одно значение, имеющее имя и занимающее одну ячейку памяти. Размер этой ячейки зависит от типа переменной.

Например:



Var

X : Real; {Простая переменная X, занимает 6 байт памяти}

N : Integer; {Простая переменная N, занимает 2 байта памяти}



Обращение к простой переменной производится через ее имя.



Например:



X := 10.4; {X присвоили значение 10.4}

N := round(X) + 5; {N присвоили значение округленного

до целого X (а это 10) + 5= 10+5=15}



Массив, в отличие от простой переменной, представляет собой не одно значение, а множество значений, объединенных одним именем. В языке Turbo Pascal все значения из этого множества должны иметь один и тот же тип.

Каждое из значений массива называется элементом массива.

Доступ к элементам массива производится посредством указания имени массива и номера элемента массива, заключенного в квадратные скобки.

Номер элемента массива называется индексом элемента массива.

Использование элемента массива не отличается от использования простой переменной, имеющей тот же тип, что и элемент массива.

В Turbo Pascal массив объявляется при помощи ключевого слова array, после которого в квадратных скобках указываются границы индексов: верхняя, а после двух точек нижняя. После ключевого слова of, стоящего за квадратными скобками, указывается тип элементов массива.

Пример определения массивов:



Var

A : Array [1..10] of integer; {Массив A, состоящий

из 10 элементов целого типа

с индексами от 1 до 10}

B : Array [5..8] of real; {Массив B, состоящий

из 4 элементов вещественного

типа с индексами от 5 до 8}



Пример работы с массивами:



Begin

A[1] := 3; {В элемент массива A с индексом 1 записали число 3}

A[4] := A[1] + 1; {В элемент массива A с индексом 4 записали

число 3+1=4}

B[5] := 0.111; {В элемент массива B с индексом 5 записали

число 0.111}

B[ A[1] + A[4] ] := B[5] * 2; {В элемент массива B

с индексом 7 (A[1]+A[4]=3+4=7) записали число 0.222}

End.





Индексы массива



В качестве индекса массива можно использовать любой порядковый тип, кроме типа Longint. Напомним, что порядковый тип – это тип, все значения которого можно перечислить. К таким типам относятся все целые типы (integer, shortint, longint, byte, word), все логические (boolean, wordbool, longbool, bytebool), символьный тип (char), перечисляемые типы и типы-диапазоны.

Примеры использования в качестве индексов порядковых типов:

Var {Примеры объявления массивов}

A : Array [Byte] of integer; {Массив A, состоящий из 256

элементов, нижняя граница индекса 0, верхняя 255}

B : Array [Char] of real; {Массив B, состоящий из 256

элементов, нижняя граница индекса #0(символ с кодом 0),

верхняя граница индекса #255(символ с кодом 255)}

I : Byte; {Переменная, используемая как индекс массива A}

C : Char; {Переменная, используемая как индекс массива B}



Begin {Примеры обращения к элементам массива}

A[45] := 0; {В элемент массива A, имеющий индекс 45,

записали 0 }

B[‘t’] := 2.4; {В элемент массива B, имеющий индекс ‘t’,

записали 2.4}

I := 200; {i присвоили значение 200 }

C := ’#’; {c присвоили значение ‘#’ }

A[i] := 23400; {В элемент массива A, имеющий индекс i=200,

записали 23400}

B[c] := 123.456; {В элемент массива B, имеющий индекс c=’#’,

записали 123.456}

End.



Обычно в качестве индекса используют диапазон значений какого-либо перечисляемого типа.



Например:

Var {Примеры объявления массивов}

C : Array [-10..5] of integer; {Массив C, состоящий из

16 элементов, нижняя граница индекса -10, верхняя 5}

D : Array [‘A’..’Z’] of char; {Массив D, состоящий из

26 элементов, нижняя граница индекса ’A’,

верхняя граница индекса ‘Z’}

j : -10..5; {Переменная, используемая как индекс массива C}

c1 : ‘A’..’Z’; {Переменная, используемая как индекс

массива D}

k : integer; {Эту переменную можно использовать в качестве

индекса массива C, т.к. –10..5 – это диапазон

значений целого типа}

c2 : char; {Эту переменную можно использовать в качестве

индекса массива D, т.к.’A’..’Z’ – это диапазон

значений символьного типа}

begin {Примеры обращения к элементам массивов}

C[-4] := 3;

D[‘F’] := ’%’;

J := 4; C[j] := -10;

c1 := ’R’; D[c1] := ’q’;

K := -3; C[k] := 80;

c2 := ’G’; D[c2] := ’Й’;

end.



Чаще же всего используют диапазон значений целого типа, причем нижний индекс обычно берут равным 1.

Например:

Var

E: Array [1..10] of integer; {Массив E, состоящий

из 10 элементов, нижняя граница индекса 1,

верхняя 10}





Представление массива в памяти



Элементы массива размещаются в памяти в последовательных ячейках. Массив занимает количество байт, равное произведению количества элементов массива на размер одного элемента:

SizeOfArray = NumElement * SizeOfElement

где SizeOfArray – размер массива

NumElement – количество элементов в массиве

SizeOfElement – размер одного элемента

Адрес первого (по порядку) элемента массива является адресом массива (будем обозначать его AdrArray). Адрес i-го элемента массива (его будем обозначать AdrI) можно вычислить по формуле:

AdrI = AdrArray + (i – нижняя_граница_индекса) * SizeOfElement



Для примера рассмотрим массив A, определенный ниже:





A : Array [5..8] of Real;



Нижняя граница индекса этого массива 5. Первый (по порядку) элемент массива - A[5]. Допустим, его адрес 100. ( Adr5 = 100 )

Поскольку элементы имеют тип Real, то каждый элемент занимает 6 байт памяти. Вычислим адреса остальных элементов массива

Adr6 = 100 + (6-5)*6 = 100 + 1*6 = 106

Adr7 = 100 + (7-5)*6 = 100 + 2*6 = 112

Adr8 = 100 + (8-5)*6 = 100 + 3*6 = 118



Графически покажем взаимное расположение элементов этого массива:

Адрес элемента Элемент

100 A[5]

106 A[6]

112 A[7]

118 A[8]



Замечание: один массив может занимать в памяти не более 65520 байт. Нельзя, например, определить такой массив C:

Var

C: array[1..50000] of integer;

- каждый элемент этого массива занимает в памяти 2 байта, элементов 50000, значит, весь массив занимает 100000 байт > 65520 байт.







Пользовательский тип - массив



В программе можно определить тип массива, с тем чтобы в дальнейшем использовать его для определения переменных типа массива.

Пример:

Type

Arr = array[1..20] of integer; {Определили тип массива

целых чисел, содержащего 20 элементов}

Var

A, B : Arr; {A и B – массивы целых чисел, содержащие

по 20 элементов}



Дальше с массивами A и B можно работать, как с обычными массивами:

A[3] := 2;

B[4] := A[3];

и т.д.



Кроме типа массива, в программе можно определить и специальный тип для индексов. Этот тип должен быть интервальным.

Пример:



Type

IndexEl = 1 .. 20; {Тип индекса элемента}

Arr = array[IndexEl] of integer; {Тип массива целых чисел,

содержащего 20 элементов}

Var

A, B : Arr; {A и B – массивы целых чисел, содержащие

по 20 элементов}

i, j : IndexEl; {Переменные, используемые для указания

индекса элемента}







ОСНОВНЫЕ АЛГОРИТМЫ



Общие замечания



Алгоритмы обработки массивов включают в себя, как правило, последовательную обработку каждого из элементов массива. Такая последовательная обработка называется сканированием массива, и для ее реализации удобнее всего использовать цикл for. Например, фрагмент программы, выполняющий подсчет суммы элементов массива, имеет такой вид:

S := 0; {Значение суммы S обнуляем}

For I := 1 to N do {Проходим по всем N элементам массива}

S := S + a[i]; {Прибавляя к сумме S значение i-го элемента}

По сложившейся традиции, переменная, используемая в качестве счетчика цикла сканирования элементов массива, называется I (Index). Если в программе требуется не одна, а две переменные-счетчики, то им дают имена i и j. Если же требуется более двух переменных-счетчиков, то первым двум дают имена i и j, а остальным, как правило, дают тоже однобуквенные имена (например, k, l, z и т.д.). Все эти переменные должны иметь тип, совместимый с типом индекса элемента массива.

В целом же при работе с одномерными массивами нужны:



а) константы:

Const

maxN = 20; {Максимальное количество элементов в массиве}



б) типы:

Type

IndexEl = 1 .. maxN; {Тип индекса элемента}

arrInt = array[IndexEl] of integer; {Тип массива

целых чисел}



в) переменные:

Var

A : arrInt; {Обрабатываемый массив}

N : integer; {Количество используемых элементов в массиве}

I : IndexEl; {Счетчик, используемый для сканирования}



Замечание:

1. Знаком … будем обозначать, что некоторая часть исходного текста программы пропущена.

2. Если в алгоритме будут нужны еще какие-то переменные, то они будут указаны дополнительно.





Ввод/вывод массива



Задача 1: Ввод массива с клавиатуры.



Алгоритм состоит из двух пунктов:

1 . Ввод количества элементов.

2 . Ввод элементов массива поодиночке в цикле.



Фрагмент программы:



{1 - ввод количества элементов}

repeat

write('Введите n:');

readln(n);

until ( n >= 1 ) and ( n <= maxN );

{2 - ввод элементов массива поодиночке}

for I := 1 to n do

begin

write('a[', i, ']');

readln(a[i]);

end;





Задача 2: Заполнение массива случайными числами.



Алгоритм состоит из трех пунктов:

1 . Перезапустить генератор случайных чисел.

2 . Ввести количество элементов n (или сгенерировать

случайное значение n).

3 . Сгенерировать значения для всех элементов.



Фрагмент программы:





{1 - перезапускаем генератор случайных чисел}

randomize;

{2 - генерируем случайное значение n}

n := random(maxN);

{3 - генерируем n элементов массива}

for I := 1 to n do

a[i] := random(100); {Каждый элемент примет значение

из интервала 0..99}





Задача 3: Вывод массива.



Алгоритм состоит из двух пунктов:

1. Вывод имени массива.

2. Вывод массива по элементам.



Фрагмент программы:



{1 - вывод имени массива}

writeln('Массив А[', n, ']');

{2 - вывод элементов массива}

for I := 1 to n do

writeln('A[', i, ']=', a[i]);





Использование генератора псевдослучайных чисел



Если в программе требуется использовать случайную последовательность чисел, тогда используют генератор псевдослучайных чисел. Перед использованием генератора псевдослучайных чисел его рекомендуется запустить – для этого используется Randomize. Для получения очередного случайного числа используется Random.

Randomize - инициализирует (запускает) генератор случайных чисел случайным значением (случайное значение зависит от момента перезапуска, т.е. от времени).

Random(Num) - возвращает случайное целое число, находящееся в интервале 0 .. (Num-1). (Например, если Num=100, то Random возвращает числа в интервале от 0 до 99).

Если Num<=0, то Random всегда будет возвращать 0.

Чтобы получить значения в интервале, отличном от [0..Num-1], необходимо к значению, возвращаемому Random, прибавить смещение начала интервала.

Пример 1: необходим интервал [-50 .. 50].

Длина интервала 101, смещение начала интервала –50.

random(101) - 50

Пример 2: необходим интервал [20 .. 30].

Длина интервала 11, смещение начала интервала 20.

random(11) + 20

Пример 3: необходим интервал [-1000 .. -500]

Длина интервала 501, смещение начала интервала –1000.

random(501) - 1000





Вычисление суммы и среднего арифметического элементов массива



Задача 4: Подсчитать сумму элементов массива.



Алгоритм содержит два пункта:

1. Сумма S=0.

2. Проход по всем элементам массива и прибавление их значений к сумме S.



Приведем полный текст программы – решение этой задачи:

{Пример обработки одномерного массива}

{ Задание: Ввести массив. Подсчитать сумму элементов массива.}

Program SumExample;

Const {Определение констант}

maxN = 20; {Максимально возможное количество элементов

в массиве}

Type {Определение типов}

IndexEl = 1 .. maxN; {Индексы массива лежат в интервале

от 1 до maxN}

arrInt = array[interval] of integer; {Массив целых чисел,

содержащий до maxN элементов}

Var

A : arrInt; {Массив}

N : interval; {Размерность массива}

I : IndexEl; {Переменная для сканирования массива}

S : integer; {Сумма элементов массива}



Begin

{ Ввод массива с клавиатуры }

write(‘Введите n=’);

read(n); {Ввод количества элементов}

for I := 1 to n do

read(A[i]); {Ввод самих элементов}



{Подсчет суммы элементов массива}

{1} s:=0;

{2} for I := 1 to n do

s := s + A[i];



{Вывод полученного значения суммы}

writeln(‘сумма элементов массива S=’, S);



end. {Конец программы}



Задача 5: Вычислить среднее арифметическое элементов массива.



Алгоритм содержит три пункта. Первые два совпадают с предыдущей задачей:

1. Сумма S=0.

2. Проход по всем элементам массива и прибавление их значений к сумме S.

3. Сумму делим на количество элементов массива SA=S/N .



Фрагмент программы:

Var

S : integer; {Сумма элементов массива}

Sa : real; {Среднее арифметическое элементов массива}



Begin



{1} s := 0;

{2} for I := 1 to n do

s := s + A[i];

{3} sa := s / n;







Поиск максимального/минимального элемента массива



Задача 6: Найти значение максимального элемента массива.



Алгоритм содержит три пункта:

1. Максимальным элементом считаем первый элемент: max=A[1].

2. Начиная со второго элемента, сравниваем имеющийся максимальный элемент max с очередным элементом массива A[i].

3. Если очередной элемент массива больше имеющегося максимального элемента, то это и есть новый максимальный элемент max=A[i].



Фрагмент программы:

Var

Max : integer; {Значение максимального элемента массива}



Begin



{1} max := A[1];

{2} for I := 2 to n do

{3} if A[i] > max then max := A[i];





Задача 7: Найти min и max значения элементов массива.



Фрагмент программы:

Var

max,min:integer; {Значение максимального и минимального

элементов массива}



Begin



max := A[1];

min := A[1];

for i := 2 to n do

if A[i] > max then max := A[i]

else if A[i] < min then min := A[i];



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



Задача 8: Подсчитать, сколько раз в массиве встречается элемент, равный 10.



Задача решается по следующему алгоритму:

1. Количество нужных элементов К=0.

2. Проходим по всем элементам массива.

3. Если очередной элемент массива равен 10,

4. Тогда увеличиваем К (количество элементов равных 10) на 1.



Фрагмент программы:

Var

k:integer; {Количество элементов, равных 10}



Begin



{1} k:=0;

{2} for I := 1 to n do

{3} if A[i] = 10

{4} then k := k+1;





Удаление элемента из массива



Задача 9: Удалить из массива первый элемент.



Удаление элемента заключается в:

1. Сдвиге элементов, стоящих правее удаляемого, влево.

2. Уменьшении количества элементов массива n на количество удаляемых элементов.



Сдвиг элементов выполняется так:

1. Начиная с удаляемого элемента, копируем содержимое элемента, стоящего правее в текущий элемент: A[i]:=A[i+1].

2. Переходим к следующему элементу вправо: i:=i+1.

3. Заканчиваем сдвиг, когда i=n-1, так как i+1 при i=n-1 равен n..



Фрагмент программы:



{1 - сдвигаем элементы на одну позицию вправо}

{Вначале i:=1, потому что надо удалить 1-ый элемент}

for I := 1 to n - 1 do

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

{2 - уменьшаем количество элементов в массиве}

n := n-1;



Задача 10: Удалить из массива максимальный элемент массива.



Для этого надо:

1. Найти индекс максимального элемента.

2. Удалить элемент с найденным индексом.



Фрагмент программы:



Var

imax:IndexEl; {Индекс максимального элемента}



Begin



{1 - ищем индекс максимального элемента массива}

imax := 1; {Вначале imax указывает на первый элемент}

{В цикле начиная со 2-го элемента}

for I := 2 to n do

{Сравниваем i-ый элемент с максимальным на текущий

момент времени, и если i-ый элемент больше

максимального, то максимальным становится

i-ый элемент}

if A[i] > A[imax] then imax := i;



{2 - удаляем элемент массива с индексом imax}

for I := imax to n - 1 do

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

dec(n); {Уменьшаем n на 1}





Замечание: в языке Тurbo Рascal имеются процедуры увеличения и уменьшения переменной целого типа.



Inc - увеличение значения переменной.

Вид вызова для целого X

Inc(x); X := x + 1;

Inc(x, n); X := x + n;



где x - переменная целого типа,

n - целочисленное выражение.



В первом случае переменной x присваивается следующее значение (например, x была равна 10, тогда после выполнения inc(x) x равна 11). Таким образом, можно сказать, что запись inc(x) эквивалентна записи x:=x+1.

Можно также сказать, что запись inc(x,n) эквивалентна записи x:=x+n.







Dec – уменьшение значения переменной.

Вид вызова для целого X

Dec(x); X := x - 1;

Dec(x, n); X := x - n;





Вставка новых элементов в массив



Задача 11: В массив после максимального элемента вставить элемент, равный 0.

Пример исходного массива A: 1 2 5 1 0 1 2 .

максимальный элемент A[3]=5

Массив после вставки элемента: 1 2 5 0 1 0 1 2.



Алгоритм вставки элемента в массив:

1. Сдвинуть элементы от позиции вставляемого элемента в конец.

2. В позицию вставляемого элемента вписать нужное значение.

3. Количество элементов n увеличить на 1 .



Общий алгоритм программы следующий:

1 . Введем массив А.

2 . Найдем индекс max элемента.

3 . Вставим после max 0.

4 . Выведем получившийся массив.



Приведем полный текст программы:



{Пример обработки одномерного массива

Задание: в массив после максимального элемента

вставить элемент, равный 0}

Program InsertExample;

Const {Определение констант}

maxN = 20; {Максимально возможное количество элементов

в массиве}

Type {Определение типов}

IndexEll = 1 .. maxN; {Индексы массива лежат в интервале

от 1 до maxN}

arrInt = array[interval] of integer; {Массив целых чисел,

содержащий до maxN элементов}

Var

A : arrInt; {Массив}

N : integer; {Количество элементов в массиве}

I : IndexEl; {Переменная для сканирования массива}

Max : IndexEl; {Номер max элемента массива}



Begin

{1 - ввод массива - генерируем случайные элементы}

randomize;

n := random(6) + 5; {n в интервале 5..10}

for I := 1 to n do

A[i] := random(19) - 9; {Генерируем элементы массива.

Каждый элемент имеет значение в интервале -9..9}



{2 - ищем индекс max элемента}

max := 1;

for I := 2 to n do

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



{3- вставляем 0 после максимального элемента.

Сначала сдвигаем “хвост” массива вправо}

for I := n downto max + 1 do

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

{Заносим в следующий за максимальным элемент 0}

A[max+1] := 0;

{Увеличиваем количество элементов массива}

Inc(n);



{4 - выводим массив}

writeln('Массив А после вставки:');

for I := 1 to n do

write(A[i]:3);

readln; {Ждем нажатия клавиши Enter}

End.



Данная программа демонстрирует модульный подход к решению задач: задача разбивается на подзадачи, полученные подзадачи решаются отдельно. Если подзадача не решается непосредственно, то она снова разбивается на подзадачи и т.д. Такой подход называется "программирование сверху вниз".



Замечание: данная программа таит в себе ошибку. Если n=20, то после вставки еще одного элемента n станет равной 21, и, скорее всего, программа повиснет (потому что элементов в массиве может быть НЕ БОЛЬШЕ 20). Следовательно, при вставке элементов необходимо следить, чтобы было n<=maxN.





Удаление нескольких элементов массива



Задача 12: Удалить из массива все элементы между k-м и z-м элементами.



Рассмотрим задачу на примере при количестве элементов в массиве n=10, k=3, z=7 (т.е. надо удалить элементы между третьим и седьмым).

Будем использовать переменную d - количество удаляемых элементов. Значение d можно вычислить по формуле: d = z - k – 1 (в нашем примере получится d = 7 - 3 - 1 = 3).



Массив A до удаления:

a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]

1 3 9 1 0 1 3 2 7 2

^ ^ ^

a[k] a[z] a[n]



Массив A после удаления:

a[1] a[2] a[3] a[4] a[5] a[6] a[7]

1 3 9 3 2 7 2

^ ^ ^

a[k] a[z] a[n]



После удаления n стало меньше на d (в нашем примере на 3).



Общий алгоритм решения:

1 . Сдвинуть элементы вперед на d элементов, начиная с z-го.

2 . Уменьшить n на d.



Фрагмент программы:

Var

K : integer; {Индекс элемента, после которого удаляем}

Z : integer; {Индекс элемента, до которого удаляем}

D : integer; {Количество удаляемых элементов}



Begin



{Вычисляем количество удаляемых элементов}

d := z - k - 1;

{1 - сдвигаем элементы}

for I := z to n do

A[ I – d ] := A[i];

{2 - уменьшаем n на d}

Dec(n, d);





Задача 13: Из массива удалить все элементы, которые меньше 0.



Рассмотрим два решения этой задачи.



Алгоритм первого решения:

1. Просматриваем массив .

2. Если элемент<0, то удаляем его и n уменьшаем.

3. Если элемент>=0, то переходим к следующему.

Фрагмент программы:



{В цикле просматриваем элементы массива}

I := 1;

while I <= n do

begin

{Проверяем, не нужно ли i-ый элемент удалять}

if A[i] < 0 then

begin

{Если нужно – удаляем i-ый элемент}

for j := i to n - 1 do {Сдвигаем}

A[j] := A[j+1];

Dec(n); {Уменьшаем количество элементов}

end

else Inc(i); {Если удалять не нужно, то переходим

к следующему элементу}

end;





Пример прогона алгоритма:

Исходный массив:

0: i=1, n=6: -1 -2 2 -3 -4 3



Состояния массива после обработки очередного элемента массива:

1: i=1, n=5: -2 2 -3 -4 3 (удален -1)

2: i=1, n=4: 2 -3 -4 3 (удален -2)

3: i=2, n=4: 2 -1 -2 3 (перешли на следующий)

4: i=2, n=3: 2 -4 3 (удален -3)

5: i=2, n=2: 2 3 (удален -4)

6: i=3, n=2: 2 3 (перешли на следующий)



Алгоритм второго решения:

1. Счетчик переписанных элементов k=0.

2. Просматриваем элементы массива.

3. Если элемент A[i] не меньше 0, k увеличиваем на 1 и переписываем элемент A[i] на k-ое место.

4. После просмотра всего массива количество переписанных элементов k заносим в n.



Фрагмент программы:

Var

K : IndexEl; {Количество переписанных элементов}



Begin



{1 - переписанных элементов пока не было}

k := 0;

{2 - в цикле просматриваем элементы массива}

for I := 1 to n do

{3 - если A[i] не <0}

if not( A[i] < 0) then

begin

Inc(k); {Увеличиваем значение k на 1}

A[k] := A[i]; {Переписываем i-ый элемент в позицию k}

end;

{4 - в массиве оставляем k элементов}

n := k;







Пример прогона программы:

Исходный массив: -1 -2 2 -3 -4 3



Состояния массива после просмотра очередного элемента массива:

0: k=0, i=1, n=6: -1 -2 2 -3 -4 3 {не переписываем}

1: k=0, i=2, n=6; -1 -2 2 -3 -4 3 {не переписываем}

2: k=1, i=3, n=6; 2 -2 2 -3 -4 3 {переписываем

a[1]:=a[3]}

3: k=1, i=4, n=6; 2 -2 2 -3 -4 3 {не переписываем}

4: k=1, i=5, n=6; 2 -2 2 -3 -4 3 {не переписываем}

5: k=2, i=6, n=6; 2 3 2 -3 -4 3 {переписываем

a[2]:=a[6]}

6: k=2, i=7, n=6: 2 3 2 -3 -4 3 {выход из цикла}

7: n=2: 2 3 {значение k переписываем в n}





Обработка нескольких массивов



Задача 14: Массивы А и В имеют одинаковую длину. Массив С необходимо заполнить суммами соответствующих элементов массивов А и В. n - длина массивов А и В (и С тоже).



Фрагмент программы:



{Проходим по всем элементам массивов}

for I := 1 to n do

{Сумму i-ых элементов массивов A и B заносим в i-ый элемент C}

C[i] := A[i] + B[i];





Задача 15: В конец массива А[n] приписать все элементы массива В[m].



Фрагмент программы:



{Проходим в цикле по массиву B}

for I := 1 to m do

A[n + i] := B[i]; {Дописываем элементы в “хвост” A}

Inc(n, m); {Увеличиваем значение n (длину массива A) на

m (длину массива B)}





Замечание: необходимо следить, чтобы n не превысило значение maxN.

Например, так:



if n + m > maxN

then writeln('В массив А все элементы массива В ‘,

’не поместятся')

else … {А вот здесь выполняем добавление элементов}









Задача 16: Сформировать массив В из отрицательных элементов массива А. Массив А не изменять.



Фрагмент программы:



m := 0; {m - количество элементов в массиве В -

вначале массив B пустой}

{Проходим по всем элементам массива A}

for I := 1 to n do

if A[i] < 0 then {Если i-ый элемент массива A

отрицательный}

begin

{То копируем его в массив B}

Inc(m); {В B добавляется еще один элемент -

увеличиваем m на 1}

B[m] := A[i]; {Копируем i-ый элемент массива A

в m-ый элемент массива B}

end;





Задача 17: Подсчитать, сколько элементов массива А совпадают с элементами массива В.



Алгоритм программы:

1. Ввести массив А[n].

2. Ввести массив В[m] .

3. Счетчик совпадений cnt обнулить.

4. Пройти по всем элементам массива A.

5. Сравнить i-ый элемент массива А со всеми элементами

массива В.

6. Если А[i] совпадает хотя бы с одним элементом массива B,

то счетчик повторений увеличить на 1.

7. Вывести количество совпадений.



Текст программы:



{Подсчитать, сколько элементов массива А совпадают с элементами массива В}

Program TwoArrayExample;

Const

maxN = 20; {Максимальное количество элементов массива}

Type

IndexEl = 1 .. maxN; {Индексы массива лежат в интервале

от 1 до maxN}

arrInt = array[IndexEl] of integer; {Массив целых чисел,

содержащий до maxN элементов}

Var

a, b: arrInt; {Массивы A и B}

n : integer; {Количество элементов массива A}

m : integer; {Количество элементов массива B}

i, j : IndexEl; {Переменные для сканирования массивов}

cnt : integer; {Количество совпадений элементов A

с элементами B}

k: integer; {Количество совпадений элемента A[i]

с элементами B}

Begin



{1 - ввод массива A}

{Ввод количества элементов}

repeat

write('Введите n:');

readln(n);

until ( n >= 1 ) and ( n <= maxN ); {Выйдем из цикла лишь

тогда, когда n будет принадлежать интервалу [1..maxN]}

{Ввод элементов массива A поодиночке}

for I := 1 to n do

begin

write('a[', i, ']');

readln(a[i]);

end;



{2 - ввод массива B}

{ Ввод количества элементов}

repeat

write('Введите m:');

readln(m);

until (m >= 1) and (m <= maxN);

{ Ввод элементов массива B поодиночке}

for I := 1 to m do

begin

write('b[', i, ']');

readln(b[i]);

end;



{3 - счетчик повторений обнуляем}

cnt := 0;



{4 - проходим по всем элементам массива A}

for I := 1 to n do

begin

{5 - сравниваем i-ый элемент массива А со всеми

элементами массива В}

k := 0; {k - количество совпадений i-го элемента массива A

с элементами массива В}

{Считаем количество совпадений A[i] с элементами

массива B}

for j := 1 to m do

if A[i] = B[j] then Inc(k);



{6 - если А[i] совпадает хотя бы с одним элементом массива B,

счетчик повторений увеличить на 1}

if k > 0 then Inc(cnt);

end;



{7 - выводим количество повторений}

writeln('Количество совпадений cnt=', cnt);

readln; {Ждем нажатия клавиши Enter}

End.



Проверка соседних элементов массива



Задача 18: Подсчитать, сколько в массиве элементов, равных 0, справа и слева от которых стоят отрицательные элементы.



Фрагмент программы:



k := 0; {Количество таких элементов}



{Проходим по всем элементам массива A. Начинаем не

с первого элемента, а со второго, потому что у первого элемента

нет стоящего слева от него. Заканчиваем на n-1 элементе, а не

на n, потому что у последнего n-го элемента нет элемента,

стоящего от него справа}

for I := 2 to n - 1 do

{Если i-ый элемент равен 0 и элемент слева от него и

элемент справа от него отрицательные}

if ( A[i] = 0 ) and ( A[i-1] < 0 ) and ( A[i+1] < 0 )

then Inc(k); {Тогда увеличиваем счетчик}





Задача 19: Найти номер первого элемента массива, который находится между двумя положительными элементами.



Фрагмент программы:



k := 0; {k - номер искомого элемента}

I := 2; {начинаем со второго элемента}

{Пока не нашли искомый элемент и не просмотрели

все элементы массива}

while (I <= n - 1) and (k = 0) do

begin

{Если элемент тот, что надо, то запоминаем его индекс}

if (A[i-1] > 0) and (A[i+1] > 0) then k := i;

Inc(i); {Переходим к следующему элементу}

end;

{Выводим позицию искомого элемента}

if k = 0

then writeln('искомых элементов в массиве нет')

else writeln('искомый элемент занимает позицию ', k);







Сортировка массива и работа с отсортированным массивом



Задача 20: Отсортировать массив по возрастанию.

Массив A является отсортированным (упорядоченным) по возрастанию, если для всех i из интервала [1..n-1] выполняется условие A[i]<=A[i+1].



Существует множество методов сортировки, мы же воспользуемся одним из самых простых - методом сортировки выбором (поиском минимального элемента).



Суть этого метода сортировки заключается в следующем:

1. В массиве находим минимальный элемент.

2. Меняем минимальный элемент с первым.

3. В усеченном (исключая первый элемент) массиве находим

минимальный элемент.

4. Ставим его на второе место.

И так далее n-1 раз.



Пример:

Массив A, исходное состояние 1 3 0 9 2.



Процесс сортировки

0: 1 3 0 9 2 min=a[3]=0 Переставляем a[1]<->a[3]

1: 0|3 1 9 2 min=a[3]=1 Переставляем a[2]<->a[3]

2: 0 1|3 9 2 min=a[5]=2 Переставляем a[3]<->a[5]

3: 0 1 2|9 3 min=a[5]=3 Переставляем a[4]<->a[5]

4: 0 1 2 3 9 Готово



Здесь знак | отделяет уже отсортированную часть массива от еще не отсортированной.



На Turbo Pascal этот алгоритм будет выглядеть следующим образом:

Var

Buf : integer; {Через buf будем менять значения двух

элементов массива}

imin : IndexEl; {Индекс минимального элемента

неотсортированной части массива}



Begin



{n-1 раз ищем минимальный элемент массива}

for I := 1 to n - 1 do

begin

{Ищем минимальный элемент в несортированной

части массива (от i-го элемента)}

imin := i;

for j := I + 1 to n do

if A[j] < A[imin] then imin := j;

{Переставляем i-ый и imin-ый элементы}

buf := A[i];

A[i] := A[imin];

A[imin] := buf;

End;





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



Алгоритм решения задачи следующий:

1. Ищем в массиве тот элемент, который больше вставляемого. Для этого последовательно просматриваем все элементы, начиная с первого.

2. Увеличиваем длину массива на 1.

3. После этого все элементы, стоящие правее от найденного, включая сам найденный элемент, сдвигаются вправо.

4. На освободившуюся позицию вставляется искомый элемент.

Замечание: если все элементы массива меньше вставлямого, то новый элемент надо вставить в конец массива. Если все элементы массива больше вставляемого, то новый элемент надо вставить в начало массива.



Пример: Надо вставить 5 в массив A: 3 4 7 9.

1. Ищем элемент, больший вставляемого. Это элемент A[3]=7.

2. Увеличиваем длину массива на 1.

Получаем массив A: 3 4 7 9 X.

3. Сдвигаем элементы, начиная с 3-го, вправо.

Получаем массив A: 3 4 7 7 9.

4. В элемент A[3] заносим 5.

Получаем массив: 3 4 5 7 9.



Фрагмент программы, реализующей данный алгоритм:



{Считываем число, которое надо вставить в массив}

read(g);



{1. Ищем элемент больше вставляемого }

k := 1; {k – индекс сравниваемого элемента}

{Ищем в массиве первый из элементов, которые больше

вставляемого элемента}

while (k <= n) and (a[k] <= g) do

k := k + 1;



{2. Увеличиваем длину массива на 1}

n := n + 1;



{3. Сдвигаем элементы начиная с k-го вправо}

for I := n downto k + 1 do

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



{4. В A[k] заносим g}

a[k] := g;