Одномерные Массивы. Операции с Массивами
ВВЕДЕНИЕ В МАССИВЫ
Понятие массива
Чтобы определить понятие “массив”, сначала необходимо обратиться к понятию “простая переменная”.
Простая переменная - это одно значение, имеющее имя и занимающее одну ячейку памяти. Размер этой ячейки зависит от типа переменной.
Например:
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;
…