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