5. Массивы: заполнение, вывод на экран, сортировка

Цель

Ознакомиться со структурой данных «массив». Научиться заполнять массив вручную и автоматически случайными значениями; выводить значения элементов массива на экран в удобочитаемом виде; находить наибольший и наименьший элементы массива; сортировать элементы массива. Применить полученные навыки в решении задач.

Теория

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

Описание типа массива задается следующим образом:

<имя типа> = ARRAY [ <сп.инд.типов> ] OF <тип>

<имя типа> - правильный идентификатор;

ARRAY, OF - зарезервированные слова (массив, из);

<сп.тд.типов> - список из одного или нескольких индексных типов, разделенных запятыми; квадратные скобки, обрамляющие список, - требование синтаксиса;

<тип> - любой тип Паскаля.

В качестве индексных типов в Паскале можно использовать любые порядковые типы, кроме LONGINT и типов-диапазонов с базовым типом LONGINT.

type

aInt = array [1..10] of integer;

var

x, y: aInt;

begin

x[1]:=10;

x[2]:=15;

y[1]:=x[1]+x[2];

...

end.

В примере объявлен тип данных массив, который может содержать 10 элементов целочисленного типа. Далее описаны две переменные, как принадлежащие этому типу. В тексте программы показан пример заполнения элементов массива целыми числами. Отметим, что по умолчанию значения элементов массива равны нулю.

Определить переменную как массив можно и непосредственно при описании этой переменной, без предварительного описания типа массива, например:

var

а,b : array [1..10] of Real;

Обычно в качестве индексного типа используется тип-диапазон, в котором задаются границы изменения индексов. Так как тип <тип>, идущий за словом OF, - любой тип Паскаля, то он может быть, в частности, и другим массивом, например:

Всякая обработка массива производится поэлементно. Исходя из того, что элементы массива проиндексированы, удобно обрабатывать массив в итерационном цикле.

Например, заполнение массива случайными числами:

var

a:array [1..5] of Integer;

i:Byte;

begin

Randomize;

for i:=1 to 5 do

a[i]:=Random(100);

...

end.

Или вывод значений элементов массива на экран:

...

begin

...

for i:=1 to 5 do

Write(a[i]:5);

...

end.

Наиболее распространенной задачей при работе с массивами является задача сортировки. Начнем ее рассмотрение с элементарной подзадачи – поиска наибольшего или наименьшего элемента в массиве.

Общий алгоритм отыскания наибольшего элемента в массиве заключается в следующем:

1) взять за наибольший элемент первый элемент массива и поместить его в отдельную переменную (например max);

2) последовательно перебрать в цикле элементы массива начиная со второго, на каждой итерации сравнивая элемент со значением переменной max;

3) в случае, если значение какого-либо элемента превышает значение переменной max, заменить значение переменной max на значение этого элемента.

Наименьший элемент массива находится аналогичным способом.

Далее рассмотрим два наиболее простых алгоритма сортировки массива.

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

1. В массиве определяется наибольший элемент;

2. этот элемент ставится на последнее место (значения элементов меняются);

3. размерность массива уменьшается на единицу и действия повторяются.

Отметим, что реализация данного алгоритма потребует умения находить наибольший элемент массива с сохранением не только его значения, но и индекса. Кроме того, необходимо уметь менять местами значения двух переменных (например, с использованием третьей, буферной переменной).

Данный алгоритм может быть модифицирован, если на каждой итерации находить не наибольший, а наименьший элемент. Это позволит отсортировать массив в обратном порядке.

Сортировка перестановками

1. Попарно сравниваются каждые два элемента массива, начиная с первых;

2. если правый элемент больше левого, их значения меняются;

3. размерность массива уменьшается на единицу и действия повторяются.

Таким образом, результатом каждой итерации будет массив с наибольшим элементом на последней позиции, в результате перестановок он как бы «всплывает наверх», поэтому такая сортировка также получила название «пузырьковая».

Отметим, что реализация данного алгоритма потребует меньших затрат: в данном случае нужно только уметь сравнивать два числа и, при необходимости, менять их значения.

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

Для реализации этих алгоритмов потребуется организовать два цикла: один цикл будет перебирать элементы массива, и результатом его работы будет наибольший (наименьший) элемент в последней позиции; другой цикл будет на каждом шаге уменьшать размерность массива и запускать первый цикл. Такая структура называется – «вложенным циклом», т.е. цикл на каждой итерации цикла.

Такая вложенность может потребоваться при обработке двумерных массивов – массивов, организация индексирования которых имеет второй порядок. Ярким примером использования двумерного массива может служить таблица значений или матрица. Очевидно, что такие структуры данных неудобно хранить в одномерном массиве. Рассмотрим пример организации и заполнения двумерного массива целых чисел:

var

a:array [1..5, 1..4] of Integer;

I,j:Byte;

begin

Randomize;

for i:=1 to 5 do

for j:=1 to 4 do

a[i,j]:=Random(100);

...

end.

Организована табличная структура данных размерностью 5x4. Значения ее заполнены псевдослучайными целыми числами. Каждый элемент имеет два индекса, первый определяет строку, второй определяет столбец, т.е. указывается координата элемента в таблице.

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

Задание

1. Автоматически заполнить одномерный массив случайными значениями (положительными и отрицательными) в заданном диапазоне.

2. Вывести на экран наибольший и наименьший элементы массива.

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

4. Вывести на экран наибольший и наименьший элементы двумерного массива.

*5. Отсортировать одномерный массив по возрастанию и убыванию, вывести результаты на экран.

Задачи А. Одномерные массивы.

1. Даны натуральное число п, целые числа а₁,…,а_n Найти количество и сумму тех членов данной последовательности, которые делятся на 5 и не делятся на 7.

2. Даны натуральные числа n,р ,целые числа а₁,…,а_n . Получить произведение членов последовательности а₁,…,а_n , кратных р.

3. Даны натуральное число п, действительные числа ₁,…,_n Вычислить обратную величину произведения тех членов _i последовательности ₁,…,_n, для которых выполнено i+ 1 < _i< i!.

4. Даны натуральное число п, действительные числа х₁,…,х_n. В последовательности х₁,…,х_n все члены, меньшие двух, заменить нулями. Кроме того, получить сумму членов, принадлежащих отрезку [3, 7], а также число таких членов.

5. Даны натуральное число n, целые числа ₁,…,_n. Заменить все большие семи члены последовательности a₁, …, a_n числом 7. Вычислить количество таких членов.

6. Даны целые числа р, q,₁,…,₆₇.В последовательности ₁,…,₆₇ заменить нулями члены, модуль которые при делении на р дает в остатке q.

7. Даны натуральное число n, действительные числа ₁,…,_n. Получить удвоенную сумму всех положительных членов последовательности ₁,…,_n.

8. Даны целые числа а₁,…,а₅₀. Получить сумму тех чисел данной последовательности, которые кратны 5.

9. Даны целые числа а₁,…,а₅₀. Получить сумму тех чисел данной последовательности, которые нечетны и отрицательны.

10. Даны целые числа а₁,…,а₅₀. Получить сумму тех чисел данной последовательности, которые удовлетворяют условию |_i|<i²

11. Даны натуральное число n, действительные числа ₁,…,_n. В последовательности ₁,…,_n все отрицательные члены увеличить на 0.5, а все неотрицательные заменить на 0.1.

12. Даны натуральное число п, действительные числа ₁,…,_n. В последовательности ₁,…,_n все неотрицательные члены, не принадлежащие отрезку [1, 2], заменить на единицу. Кроме того, получить число отрицательных членов и число членов, принадлежащих отрезку [1, 2].

13. Даны натуральное число n, целые числа ₁,…,_n. Получить сумму положительных и число отрицательных членов последовательности ₁,…,_n.

14. Даны натуральное число n, действительные числа ₁,…,_n. Найти удвоенную сумму всех положительных членов последовательности ₁,…,_n.

15. Даны целые числа a₁, …, a₄₅. Получить число отрицательных членов последовательности a₁, …, a₃₅ и число нулевых членов всей последовательности a₁, …, a₄₅.

Задачи В. Двумерные массивы.

1. Даны натуральное число n, действительная матрица размера n 9. Найти среднее арифметическое каждого из столбцов.

2. Даны натуральное число n, действительная матрица размера n 9. Найти среднее арифметическое каждого из столбцов, имеющих четные номера.

3. В данной действительной матрице размера 6 9 поменять местами строку, содержащую элемент с наибольшим значением, со строкой, содержащей элемент с наименьшим значением. Предполагается, что эти элементы единственны.

4. Даны натуральное число n, действительная квадратная матрица порядка n, действительные a₁, ..., a_n+5. Элементы последовательности a₁, ..., a_n+5 домножить на 10, если наибольший элемент матрицы (в предположении, что такой элемент единственный) находится на главной диагонали, и на 0,5 в противном случае.

5. Дана действительная квадратная матрица размера n m, все элементы которой различны. В каждой строке выбирается элемент с наименьшим значением, затем среди этих чисел выбирается наибольшее. Указать индексы элемента с найденным значением.

6. Дана действительная квадратная матрица порядка n. Построить последовательность действительных чисел a₁, ..., a_n по правилу: если в i-й строке матрицы элемент, принадлежащий главной диагонали, отрицателен, то a_i равно сумме элементов i-й строки, предшествующих первому отрицательному элементу; в противном случае a_i равно сумме последних элементов i-й строки, начиная с первого по порядку неотрицательного элемента.

7. Дана действительная матрица размера n m, в которой не все элементы равны нулю. Получить новую матрицу путем деления всех элементов данной матрицы на ее наибольший по модулю элемент.

8. Дана действительная квадратная матрица порядка 12. Заменить нулями все ее элементы, расположенные на главной диагонали и выше нее.

9. Дана действительная матрица размера m n. Определить числа

b₁, ..., b_n, равные соответственно значениям средних арифметических элементов строк.

10. Дана действительная матрица размера m n. Определить числа

b₁, ..., b_n, равные соответственно разностям наибольших и наименьших значений элементов строк.

11. Дана действительная матрица размера 6 9. Найти среднее арифметическое наибольшего и наименьшего значений ее элементов.

12. Дана действительная матрица размера m n. Найти сумму наибольших значений элементов ее строк.

13. Дана действительная квадратная матрица порядка 10. В строках с отрицательным элементом на главной диагонали найти сумму всех элементов.

14. Дана действительная квадратная матрица порядка 10. В строках с отрицательным элементом на главной диагонали найти наибольший из всех элементов.

15. Дана действительная квадратная матрица порядка 9. Получить целочисленную квадратную матрицу того же порядка, в которой элемент равен единице, если соответствующий ему элемент исходной матрицы больше элемента, расположенного в его строке на главной диагонали, и равен нулю в противном случае.