- •Программирование на языках высокого уровня
- •1. Основные понятия
- •1.1. Алфавит и словарь языка
- •1.2. Скалярные, стандартные типы данных
- •1.3. Встроенные функции
- •1.4. Структура программы
- •2. Программирование вычислительных процессов
- •2.1. Линейные процессы вычислений
- •2.2. Разветвляющийся вычислительный процесс
- •2.3. Программирование циклов
- •3. Программирование данных
- •3.1. Конструирование простых пользовательских типов
- •3.2. Массивы. Регулярные типы
- •3.3. Сортировка одномерного массива
- •3.4. Многомерные массивы
3.2. Массивы. Регулярные типы
В простых типах данных каждое данное имеет свое название (идентификатор). В этом разделе вводится структурная взаимосвязь между данными, хранимыми в оперативной памяти путем организации массива, состоящего из непрерывно расположенных данных, не снабженных отдельными именами. Эти данные в свою очередь могут быть простыми или сложными и называются элементами массива.
Основное преимущество массива состоит в том, что его элементы не имеют отдельных имен, и нет необходимости описывать каждый элемент по отдельности. Достаточно описать весь массив. Объявление массива содержит следующее описание:
TYPE <имя типа> = ARRAY [тип индекса] OF <тип элементов массива>;
Каждый элемент именуется путем указания имени массива и порядкового номера, определяющего его позицию в массиве, то есть индекса. Если тип данных определен с помощью конструкции ARRAY ... OF то он называется регулярным типом.
Паскаль предоставляет пользователю широкие возможности по заданию типа индекса, которым может быть любой порядковый или интервальный типы данных, в том числе и определенные пользователем. Тип элемента массива иногда называется базовым. Он может быть как любым скалярным, так и структурированным типом данных. Правомерно существование массивов-массивов, записей, множеств. Однако не существует массивов файлов. Число компонентов массива неявно определяется через тип индекса при его объявлении и в дальнейшем не меняется.
Одномерные массивы. Вектора
Если в описании массива типом элемента является простой тип данных, то такой массив называется вектором. Поскольку в таком массиве для идентификации величины используется только один индекс, то он называется одномерным. Такие одномерные массивы представляют собой простейшие структурированные данные. Обращение к элементам одномерного массива осуществляется с помощью индексированных переменных, например X[i]. Здесь X – имя массива, a i — константа, переменная или выражение того же типа, что и тип индекса в объявлении массива.
Пример 28.
Определить частоту появления латинских прописных букв в тексте, вводимом с клавиатуры. Ввод данных завершить символом '*'.
Здесь, в качестве индекса удобно использовать ограниченный литерный тип 'А' .. 'Z', что обеспечивает с одной стороны - мнемонический смысл индекса, соответствующего счетчику частоты появления литеры в тексте, а с другой стороны – легкость перебора значений индекса.
В Паскале нет средств ввода, вывода массива целиком, поэтому эти действия приходится выполнять как циклические процессы над отдельными элементами массива, используя (в частности, в нашем примере) оператор FOR. В этом примере при выводе результатов с помощью форматного вывода реализован перевод целочисленного выражения COUNTER [СН] * 100 / N в вещественную форму числа с фиксированной десятичной точкой.
PROGRAM PR28;
VAR COUNTER: ARRAY ['A'.. 'Z'] OF INTEGER;
CH: CHAR;
N: INTEGER;
BEGIN
{ Инициализация массива счетчиков букв COUNTER, то есть — присвоение его элементам значения 0 }
FOR СН := 'А' ТО 'Z' DO COUNTER[CH] := 0; {Обнуление счетчиков литер}
N := 0; { Обнуление счетчика числа символов в тексте}
REPEAT { Повторять для каждой новой литеры}
READ(СН); { Ввод очередного символа с клавиатуры }
N := N + 1; { Увеличение счетчика символов на единицу }
IF (СН >= 'A') AND (СН <= 'Z')
THEN COUNTER[CH] := COUNTER[CH] + 1;
{Наращивается элемент массива с индексом, соответствующим коду вводимого символа}
UNTIL СН = '*'; { Если True, то прочитана * - признак конца текста}
WRITELN('Всегo прочитано символов:', N);
WRITELN('буквa:' :10, 'частота:' :10, 'процент:' :10);
FOR СН := 'А' ТО 'Z' { Вывод элементов массива на экран }
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.