Массив описывается в программе так, как показано на Рис. 2.5.
Рис. 5.5. Описание массива.
Например, в описании TA=ARRAY[1..10] OF REAL явно присутствуют два типа данных: REAL – тип элементов массив и тип диапазон 1..10, задающий число этих элементов.
Элементы массива располагаются в памяти непрерывно, один за другим (Рис. 2.6).
Рис. 5.6. Размещение массива в памяти.
Это сделано для того, чтобы быстро и просто вычислять адрес элемента с заданным индексом. На суммарный размер всех элементов массива наложено ограничение – он не может превышать 64Кб. Дело в том, что память компьютеров типа IBM PC делится на сегменты размером по 64Кб. Программа одновременно работает с одним из многих сегментов памяти, поэтому все переменные должны занимать не более 65Кб. При попытке объявить слишком большой массив мы получим сообщение об ошибке:
TYPE TA=ARRAY[1..50000] OF REAL;
Как убедиться, что наш массив вылез из 64Кб? Давайте посчитаем. Из документации известно, что переменная типа REAL занимает 6 байт. 6´50000= 300000 байт или 300000/1024=292Кб. Кстати, определить размер в байтах любого типа данных поможет функция SizeOf. Например, SizeOf(REAL) вернет шесть.
Нельзя сразу присвоить какое-то значение всем элементам массива. Вот как выглядит очень распространенная ошибка начинающих программистов:
TYPE TA=ARRAY[1..10] OF REAL;
VAR A:TA;
…
A:=0;
Так делать нельзя! Переменной A как таковой нет – есть только переменные A[1], A[2], .. A[10].
Следует признать, что существует "обходной маневр", позволяющий одной командной обнулить все элементы массива:
TYPE TA:ARRAY[1..1000] OF REAL;
VAR a:TA;
…
FILLCHAR(a,1000,0);
Малоизвестная процедура Паскаля FillChar(adr,n,v) заносит в память один за другим n штук значений v, начиная с адреса adr. Для массива это как раз подходит. Но так можно делать именно обнуление. При размере элемента массива, превышающем один байт, занесение ненулевых значений в несколько последовательных байт приведет к неожиданному результату. Так, переменная типа WORD занимает два байта. Если в оба из них занести значение 1, то значение всей переменной станет вовсе не 1, а 00000001000000012=257. Если во все элементы нужно занести ненулевое значение, придется писать цикл.
Как отмечалось выше, обращение к отдельному элементу массива происходит по его индексу (порядковому номеру). При этом индексы можно вычислять. Фактически рассчитывается адрес ячейки памяти, начиная с которой лежит элемент массива с затребованным индексом. В массиве адрес к-го элемента=адрес 1 элемента+(к ´ размер элемента в байтах).
Базовым типом массива может являться другой массив. Так образуются многомерные массивы:
TYPE TA1=ARRAY[1..20] OF REAL;
TA2=ARRAY[1..10] OF TA1;
В памяти все ячейки многомерного массива все равно хранятся последовательно, никаких строк и столбцов при этом не образуется. Поэтому вопрос "а какой индекс – это строки, а какой – столбцы?" – не имеет смысла. Размерностей может быть и более двух (теоретически – аж до 255).
Все обычные массивы в Паскале являются статическими. Число элементов в них должно известно на этапе разработки программы. Следующая операция невозможна:
VAR a:WORD;
TYPE ta:ARRAY[1..a] OF REAL;
Однако вполне допустим вариант
CONST Nmax=20;
TYPE ta:ARRAY[1..Nmax] OF REAL;
Константу Nmax будет удобно использовать при организации циклов по массиву:
FOR I:=1 TO Nmax DO
Тогда при изменении размеров массива придется менять лишь одну константу, а не исправлять все циклы в программе.
5. Индуктивные функции на последовательностях
(файлах, массивах)
Как правило, компьютеры прежде всего используются для обработки значительных объемов информации. В большинстве алгоритмов информация читается последовательно, от начала к концу. Поэтому в программах очень часто встречаются фрагменты кода, вычисляющие некоторую функцию на последовательности элементов.
Предположим для простоты, что последовательность элементов находится в массиве. В реальных программах она также может читаться из файла или из более сложных структур данных - например, из списка. В любом случае можно встать в начало последовательности, прочесть ее очередной элемент, а также определить, есть ли еще непрочитанные элементы.
Рассмотрим пример: дана последовательность вещественных чисел, требуется вычислить сумму ее элементов. Запишем алгоритм в самом общем виде:
вещ алгоритм сумма последовательности
| дано: последовательность вещественных чисел
| надо: вернуть сумму ее элементов
начало алгоритма
| вещ s, x;
| s := 0.0;
| встать в начало последовательности
| цикл пока есть непрочитанные элементы
| | прочесть очередной элемент последовательности в (вых:x)
| | s := s + x;
| конец цикла
| ответ := s;
конец алгоритма
Здесь перед словом "алгоритм" записывается тип возвращаемого значения, т.е. "вещ" для вещественного числа. Это означает, что алгоритм можно использовать как функцию. Например, для функции "sin" можно записать выражение
y = sin(x)
При вычислении выражения сначала вызывается алгоритм (функция), вычисляющий sin, затем значение, которое возвращается этим алгоритмом, присваивается переменной y. В нашем случае можно использовать выражение
y := сумма последовательности;
для вызова алгоритма и записи возвращаемого значения в переменную y.
В случае, когда последовательность чисел находится в массиве, алгоритм выглядит следующим образом:
вещ алгоритм сумма последовательности(вх: цел n, вещ a[n])
| дано: n -- число элементов последовательности,
| a[n] -- массив элементов последовательности
| надо: вернуть сумму элементов последовательности
начало алгоритма
| вещ s; цел i;
| s := 0.0; // Инициализация значения ф-ции
| i := 0
| цикл пока i < n
| | s := s + a[i]; // Вычисление нового значения по
// старому
| | // значению и очередному элементу
| | i := i + 1; // Переходим к следующему элементу
| конец цикла
| ответ := s;
конец алгоритма
Здесь целочисленная переменная i используется в качестве индекса элемента массива. Она последовательно принимает значения от 0 до n-1. Очередной элемент последовательности записывается как a[i].
Отметим следующие составные части алгоритма, вычисляющего функцию на последовательности элементов:
инициализация значения функции для пустой последовательности - в данном случае
s := 0.0;
вычисление нового значения функции по прочтению очередного элемента последовательности. Новое значение вычисляется по старому значению и очередному прочитанному элементу. В данном случае это суммирование
s : = s+a[i]
Эти две части присутствуют в любом алгоритме, вычисляющем функцию на последовательности.
Рассмотрим еще один важный пример: вычисление максимального элемента последовательности. В отличие от суммы элементов, здесь не вполне ясно, каким значением надо инициализировать максимум, то есть чему равен максимум пустой последовательности. Для того, чтобы максимум одноэлементной последовательности вычислялся правильно, надо, чтобы максимум пустой последовательности был меньше любого числа. Поэтому максимум пустой последовательности не может быть обычным числом. В математике и в программировании очень полезен следующий прием: к обычным элементам добавляется специальный воображаемый элемент с заданными свойствами. Так были изобретены ноль, отрицательные числа, иррациональные и комплексные числа и т.п. В данном случае, таким воображаемым элементом является "минус бесконечность".
вещ алгоритм максимум последовательности(вх: цел n, вещ a[n])
| дано: n -- число элементов последовательности,
| a[n] -- массив элементов последовательности
| надо: вернуть максимум элементов последовательности
начало алгоритма
| вещ m; цел i;
| m := минус бесконечность; // Инициализация значения ф-ции
| i := 0;
| цикл пока i < n
| | если a[i] > m // Вычисление нового значения по
| | | то m := a[i]; // старому значению и очередному эл-ту
| | конец если
| | i := i + 1;
| конец цикла
| ответ := m;
конец алгоритма
Здесь переменная m на любом шаге содержит максимальное значение для просмотренного начального отрезка последовательности, т.е. кандидата на максимум. Если очередной элемент больше, чем m, то он запоминается в переменной m и становится новым кандидатом на максимум.
Значение "минус бесконечность" в случае операции взятия максимума двух чисел обладает следующим замечательным свойством: для всякого числа x выполняется равенство
max(минус бесконечность,x) = x
Можно сравнить с операцией сложения:
0+x = x
Таким образом, значение "минус бесконечность" играет роль нуля для операции взятия максимума двух чисел. Ноль - это нейтральный элемент для операции сложения: будучи прибавленным слева к произвольному числу x, он не изменяет числа x. Точно так же значение "минус бесконечность" является нейтральным для операции взятия максимума.
Для операции "минимум" нейтральным элементом является "плюс бесконечность". Таким образом, алгоритм нахождения минимума последовательности выглядит следующим образом:
вещ алгоритм минимум последовательности(вх: цел n, вещ a[n])
| дано: n -- число элементов последовательности,
| a[n] -- массив элементов последовательности
| надо: вычислить минимум элементов последовательности
начало алгоритма
| вещ m; цел i;
| m := плюс бесконечность; // Инициализация значения ф-ции
| i := 0;
| цикл пока i < n
| | если a[i] < m // Вычисление нового знач. по старому
| | | то m := a[i]; // значению и очередному элементу
| | конец если
| | i := i + 1;
| конец цикла
| ответ := m;
конец алгоритма
Как реализовать воображаемые элементы "минус бесконечность" и "плюс бесконечность" при программировании на конкретных алгоритмических языках, а не на псевдокоде? В качестве значения "минус бесконечность" всегда можно использовать произвольное значение, заведомо меньшее, чем любое конкретное число, которое может встретиться в программе. Например, если известно, что программа работает только с неотрицательными числами, то в качестве значения "минус бесконечность" можно использовать произвольное отрицательное число, например, минус единицу. Аналогично, в качестве значения "плюс бесконечность" можно применять любое достаточно большое число. Оно должно быть заведомо больше, чем все конкретные числа, которые могут встретиться в алгоритме. Пусть, например, известно, что в программе могут встретиться вещественные числа не больше миллиона. Тогда в качестве значения "плюс бесконечность" можно использовать константу
1.0e+30
т.е. десять в тридцатой степени. (Можно даже использовать 1.0e+7, т.е. десять миллионов, но не стоит мелочиться.)
