Программирование на языках высокого уровня (стр. 8 )

DO WRITELN(CH:8,COUNTER[CH]:10,COUNTER[CH]*100/N:10:2)

END.

Инициализация одномерного массива

Отличительной особенностью Паскаля от большинства процедурных языков является то, что все переменные должны быть инициализированы. То есть в разделе VAR переменным отводится место, а начальное значение этих величин специально не устанавливается. Поэтому после объявления массива необходимо его элементам задать необходимые значения. Широко используется три способа инициализации одномерного массива.

• Если значения элементов массива определены до начала работы программы, то есть известны на этапе формулировки задания на программирование, то можно использовать следующий способ:

CONST A: ARRAY [1..10] OF REAL = (0.1, -15.3, 7, 0, -11.89, 4, -78,11.2, 1,0.01);

При таком объявлении массива в разделе констант вы заносите в одномерный массив А по порядку А[1] = 0.1, А[2] = -15.3,... А[10] = 0.01 вещественные числа, перечисленные в круглых скобках. При этом массив является массивом переменных, то есть в процессе работы программы можно менять содержимое любого разряда одномерного массива. Этот способ, конечно, является нарушением по стандарту Паскаля, однако очень часто используется на практике.

• Второй способ применяется в том случае, если исходные данные необходимо ввести с клавиатуры в процессе выполнения программы. Поскольку одномерный массив представляет собой конечный набор однотипных элементов, пронумерованных с помощью индекса (переменной перечисляемого типа), то удобно использовать арифметический цикл (оператор FOR) для ввода значений непосредственно с клавиатуры. При этом можно предложить два равноценных приема. Предположим, в вашей программе сделаны объявления:

CONST

M=1;

N=15;

VAR

A: ARRAY[M .. N] OF REAL;

где M – нижняя, a N верхняя границы индексов. Первый способ ввода будет иметь инструкцию:

WRITELN('Введите массив А, из 15 вещественных чисел');

FOR I := М ТО N DO READ(A[I]);

При таком способе оператор может ввести все 15 чисел через пробел в одну строку и только затем нажать на клавишу Enter. Если он считает нужным, то он может вводить группы чисел (например, по 3 числа, чтобы не ошибиться) через пробелы и нажимать Enter. А можно вводить на каждой строке только по одному числу.

Второй способ ввода имеет вид:

FOR I := M TO N

DO BEGIN

WRITE('A[', I:1,'] = ');

READLN(A[I])

END;

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

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

FOR I := М ТО N DO А[I] := 0;

Пример 29.

В результате измерения случайного параметра сформирован массив из N вещественных чисел.

Вычислить эмпирическую среднюю и среднее квадратическое отклонение

Обозначим М = и S = σ, тогда алгоритм программы будет иметь вид.

Как мы только что обсуждали, ввод массива — это инструкция, содержащая несколько операторов, в том числе оператор цикла FOR. Но здесь и во всех последующих примерах мы не будем уточнять способ ввода одномерного массива, оставляя выбор за программистом.

PROGRAM PR29;

CONST N=10;

VAR

X: ARRAY [1.. N] OF REAL;

I: INTEGER;

S, M: REAL;

BEGIN

WRITELN('Введите массив X, из', N:2,' вещественных чисел');

FOR I := 1 TO N DO READ(X[I]);

M:=0;

S:= 0;

FOR I := 1 TO N DO M := M + X[I];

M:=M/N;

FOR I := 1 TO N DO S := S + (X[I] - M) * (X[I] - M);

S := SQRT(S / (N - 1));

WRITELN('M - ', M :10:6,', S = ', S :9:6);

END.

Отображение на экране значений одномерного массива

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

CONST M = 1; N=15;

VAR A: ARRAY [M .. N] OF REAL;

Тогда первый способ вывода элементов массива в строку будет иметь инструкцию:

WRITELN('Элементы массива А имеют значения:');

FOR I := М ТО N DO WRITE(A[I]: С: D,'');

WRITELN;

В этой инструкции первый оператор WRITELN сообщает оператору, какую информацию он увидит на экране. Второй оператор сформирует цепочку вещественных чисел, разделенных пробелами в формате: С: D. Третий оператор WRITELN переведет курсор на новую строку.

Второй способ обеспечивает вывод значений элементов массива в столбец, причем каждый из элементов будет идентифицирован:

FOR I := М ТО N DO WRITELN('A[', I:2,'] - ', А[I]: С: D);

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

Существует класс задач, в которых индекс массива используется для формализации вычислительного процесса путем сведения исходных формул к конечным суммам и произведениям. Преобразованные таким образом формулы программируются с помощью арифметических циклов. При обращении к элементам массива в качестве индексов можно использовать выражения перечисляемого типа.

Пример 30.

Дана последовательность вещественных чисел X1, Х2, X3,..., Х24. Требуется вычислить U = X1 • Х2 • Х3 • X4 + X4 • Х6 • Х7 • Х8 + ... + Х21 • Х22 • X23 • Х24

Для программирования необходимо линейную формулу U преобразовать к следующему виду:

Нетрудно заметить, что задача сведена к двойному арифметическому циклу.

Для накопления суммы по I используется переменная U, исходное состояние которой равно 0. Для накопления произведения используется рабочая переменная Р, которая рассчитывается шесть раз для значений индекса I=1,2,…,6. Для накопления произведения начальное значение J принимается равным 1.

PROGRAM PR30;

VAR

X: ARRAY [1.. 24] OF REAL;

I, J: INTEGER;

U, P: REAL;

BEGIN

WRITELN('Введите массив X, из 24 вещественных чисел');

FOR I := 1 ТО 24 DO READ(X[I]);

U := 0;

FOR I := 1 TO 6

DO BEGIN

P := 1;

FOR J := 1 TO 4

DO P:=P*X[4*(I-1)+J];

U := U + P

END;

WRITELN('U =', U:10:2)

END.

Нахождение минимального и максимального элементов массива

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

Пример 31.

В массиве X из 20 вещественных чисел поменять местами наибольшие и наименьшие элементы.

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

Идентификатор	Содержательный смысл	Тип
Х[I]	Элемент с индексом I массива X	REAL
MIN	Значение наименьшего элемента из X	REAL
МАХ	Значение наибольшего элемента из X	REAL

Эту задачу нужно решать с помощью двух последовательных просмотров массива X. Целью первого просмотра является вычисление наибольшего МАХ и наименьшего МIN значений элементов массива X. В начале просмотра значение первого элемента Х[1] считается одновременно наибольшим и наименьшим, что справедливо в том случае, если в массиве всего один элемент. Далее со второго элемента Х[2] и до последнего Х[20] сравниваются значение текущего элемента с MIN. Если значение текущего элемента меньше, то оно с этого момента считается минимальным. По окончании цикла в рабочей ячейке MIN окажется число, равное значению
наименьшего элемента. Аналогично поступаем для нахождения МАХ.

Далее нужно сравнить между собой MIN и МАХ. Если эти величины равны между собой, то массив состоит из 20 равнозначных элементов. Следовательно, переставлять их местами нет необходимости. Если MIN≠МАХ, то нужно наименьшим элементам присвоить значение МАХ, а наибольшим элементам присвоить значение MIN. Эти действия являются основой для второго просмотра массива X.

PROGRAM PR31;

VAR

X: ARRAY [ 1.. 20] OF REAL;

I: INTEGER;

MIN, MAX: REAL;

BEGIN

WRITELN('Введите массив X, из 20 вещественных чисел');

FOR I := 1 ТО 20 DO READ(X[I]);

MIN :=Х[1];

МАХ :=Х[1];

FOR I := 2 ТО 20

DO BEGIN

IF MIN>X[I]

THEN MIN := X[I];

IF MAX<X[I]

THEN MAX := X[I];

END;

IF MIN <> MAX

THEN FOR I := 1 TO 20

DO BEGIN

IF MAX = X[I]

THEN X[I] := MIN

ELSE IF MIN = X[I]

THEN X[I]:=MAX;

END;

WRITELN('Элементы массива X имеют значения:');

FOR I := 1 TO 20 DO WRITE(X[I]: 4:1,' ');

WRITELN

END.

3.3. Сортировка одномерного массива

Сортировка — перестановка местами объектов в определенном порядке. Известно несколько сотен алгоритмов сортировки и их модификаций.

Пусть дана последовательность элементов – A1, А2, …, Аn. Сортировка означает перестановку этих элементов в новом порядке Аk1 , Аk2, …, Akn. Этот порядок соответствует значениям некоторой функции F, такой, что справедливо отношение F(Ak1) < F(Ak2)< ... <F(Akn).

Как у любого вычислительного процесса у сортировки есть свои критерии для сравнительной оценки качества программы и соответствующего ей алгоритма. Такими критериями являются: объем используемой памяти и время работы программы.

Хорошей по критерию памяти считается такая сортировка, при которой данные сортируются в том же самом массиве, где находились исходные данные.

При оценке времени сортировки используют два показателя: число сравнений ключей (С), число пересылок данных (М). Хорошими по времени считаются сортировки, в которых число сравнений С=N*Ln(N). К простым, то есть не очень хорошим, относятся такие сортировки, в которых число сравнений пропорционально квадрату размерности N исходного массива С≈N2. Следует отметить, что показатели С и М существенно зависят от первоначальной упорядоченности сортируемого массива. Наиболее тяжелым (Мах) считается случай, когда массив упорядочен в обратном порядке. Ниже мы рассмотрим три наиболее известных способа сортировки одномерного массива. Сравнительные временные характеристики этих способов приведены в следующей таблице:

Способ	Min	Средний	Max
Метод Пузырька	C = (N2 - N)/2, М = 0	C = (N2 - N)/2, M = 0.75·(N2-N)	C = (N2 - N)/2, M = 1.5· (N2-N)
Простой выбор	C = (N2-N)/2, M = 3· (N-1)	C = (N2 - N)/2, M = N· (Ln(N) + 0.57)	C = (N2-N)/2, M = N2/4 + 3· (N-l)
Простое включение	C = N-1, M = 2· (N-1)	C = (N2+N-2)/4, M = (N2-9N-10)/4	C = (N2 - N)/2-l, M = (N2 +3N-4)/2

Сортировка простым обменом. Метод пузырька

Пример 32.

Методом пузырька упорядочить (отсортировать) в порядке возрастания массив из 8 целых чисел (44, 55, 12, 42, 94, 18, 06, 67).

Концептуальную модель сортировки рассмотрим на примере восьми целых чисел, которые расположим в первом вертикальном столбце. Вертикальное расположение сортируемого массива наглядно иллюстрирует «всплывание легких элементов (чисел) вверх к поверхности» по мере сортировки массива.

Элементы массива рассматриваются попарно снизу-вверх. Если нижний элемент меньше, то они меняются местами. При первом просмотре (проходе) самый «легкий» элемент оказывается самым верхним. Поэтому при втором просмотре его можно уже не рассматривать. В таблице стрелками показаны перемещения элементов массива после каждого прохода.

Индекс элемента массива	Номер прохода сортировки (I)
1	2	3	4	5	6	7	8
J=1	44	06	06	06	06	06	06	06
2	55	44	12	12	12	12	12	12
3	12	55	44	18	18	18	18	18
4	42	12	55	44	42	42	42	42
5	94	42	18	55	44	44	44	44
6	18	94	42	42	55	55	55	55
7	06	18	94	67	67	67	67	67
8	67	67	67	94	94	94	94	94

Элементы всплывают вверх к поверхности в соответствии с их весами, пока не встретят элемент с более малым весом. С каждым проходом наиболее легкий элемент из оставшихся поднимается на свое место, показанное жирными цифрами. Таким образом, нет необходимости на каждом проходе проверять элементы, стоящие выше выделенных, поскольку они уже отсортированы ранее. Начиная с 6 прохода, состояние массива не изменяется, что объясняется начальной упорядоченностью элементов в исходном массиве.

Эта программа предназначена для изучения сортировки методом пузырька, поэтому взят массив из восьми целых чисел. Массив заранее известен, следовательно, инициализировать Х[1...8] проще всего в разделе констант. Ввод данных с клавиатуры в этой программе не требуется. Алгоритм программы представляет собой двойной вложенный цикл. Индекс I внешнего арифметического цикла соответствует номеру прохода сортировки. Индекс J это номер элемента в массиве. Для перестановки двух соседних элементов X[J-1] и X[J] местами используется промежуточная рабочая ячейка с идентификатором L.