Читаем Язык программирования ABC PASCAL полностью

Язык программирования ABC PASCAL

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

Таким образом, когда мы просмотрим весь массив, окажется, что наша переменная содержит искомое значение:

{определение максимального значения}

max:=A[1];

for i:=2 to N do if A[i]>max then max:=A[i]; writeln('Maximum=',max);

Напишем теперь целиком программу, использовав полученные знания:

Program Massiv;

Const N = 10;

Var A : array [1..N] of integer;

i, max : integer;

begin

for i:=1 to N do // Ввод массива

begin

write( 'Ввeдите ',i,'-й элемент: ');

readln(A[i])

end;

max:=A[1]; // Поиск максимального значения

for

i:=2 to N do

if A[i]>max then

max:=A[i];

writeln( 'Maximum=',max);

end.

- 35 -

Задание 12

1. Внимательно прочитать текст. Знать определение массива и способы его описания. (2 балла)

2. Напишите программу, которая вводит с клавиатуры значения массива, состоящего из 10 элементов, а затем выводит его. (2 балла)

3. Модифицируйте предыдущую программу, так чтобы она выводила элементы массива в обратном порядке (используйте цикл for i:=N downto 1 do). (1 балл)

4. По аналогии с примером на стр. 35 напишите программу, находящую минимальный элемент массива и выводящую его значение. (2 балла)

5. Модифицируйте предыдущий пример, так чтобы программа определяла максимальный и минимальный элемент массива. (1 балл)

6. * Напишите программу, которая бы определяла среднее арифметическое значение элементов массива (конечно, это будет вещественная величина типа real) (* 3 балла)

7. * Напишите программу, которая бы вводила значения элементов целочисленного массива, а затем рисовала бы N окружностей, радиусы которых бы равнялись введенным значениям.

(* 3 балла)

Задачи, отмеченные *, являются необязательными и их баллы – дополнительными.

- 36 -

Тема №13. Сортировка массивов

Тема имеет исключительно важное значение

Первой серьезной задачей программирования, с которой сталкивается начинающий программист – это задача сортировки массива. Под сортировкой понимается упорядочивание элементов массива по возрастанию (или по убыванию) без создания копии массива (т.е. «на месте»).

Самый простой алгоритм – это линейная сортировка. Рассмотрим рис. 13.1.

Проведем последовательно сравнение первого элемента со всеми последующими, при если при очередном сравнении (например сразу 4 и 2) выяснится, что элементы стоят в «неправильном» порядке – переставим их местами, затем продолжим сравнение

(рис. 13.2). По окончании одного прохода, можно сказать, что в первом элементе массива находится минимальный элемент (Рис. 13.4).


Рис 13.1		Рис 13.2

Рис 13.3		Рис 13.4

Далее применим указанную процедуру к неотсортированному «остатку» массива (рис. 13.5) до тех пор, пока не переставим два последних элемента (рис. 13.6-13.7).


Рис 13.5		Рис 13.6

Рис 13.7		Рис 13.8

Алгоритм линейной сортировки очень прост, но не экономичен, среднее число просмотров и перестановок пропорционально квадрату числа элементов (точнее -N² /2 ).

- 37 -

Приведем программу сортировки. Обратите внимание, что мы использовали массив в качестве параметра процедуры. Для этого необходимо создать тип Massiv (стр. 34). Часто для экономии памяти массив передают через var-параметр (стр. 32), даже если не предполагается его модифицировать в подпрограмме. Т.е. заголовок процедуры print мог бы выглядеть следующим образом:

procedure print (var m : Massiv); .

Program LinerSort;

Const N = 10; // Число элементов массива

Type Massiv = array [1..N] of integer; // Определение типа Massiv

procedure swap(var x,y: integer); // Перестановка элементов местами

var z : integer;

begin

z:=x; x:=y; y:=z;

end;

procedure print(m : Massiv); // Вывод массива

var i : integer;

begin