Проектирование программ в O Pascal

Расширенные возможности O (Optimization) Pascal позволяют произвольный доступ к данным и управление выполнением. Два новых типа данных в O Pascal, массивы и указатели, позволяют произвольный доступ к данным. Переменная типа:

ARRAY [j] OF T

Является ограниченным списком элементов типа T, чьи элементы индексированы значениями порядкового типа J. Для любого типа T, также существует предопределенный, неограниченный список элементов типа T, индексированный значениями неупорядоченного типа “указатель”.

Части программ с массивами и указателями имеют частные функции значения, но формальный вывод функций из текста программ рассматриваться не будет. Использование указателей и массивов может обеспечить значительный выигрыш в скорости программ, но они должны использоваться с большой осторожностью, например, только тогда, когда функция части программы может быть определена и верифицирована как минимум неформально. Мы уже видели подобную ситуацию с итерационными операторами. После завершения оператора WHILE он может быть заменен группой вложенных операторов IF. Но оператор WHILE настолько эффективен (в терминах количества строк), что стоят дополнительных усилий, требуемых для вычисления функции их частного значения. На самом деле, не существует механического способа доказательства завершимости цикла и следовательно, механического способа верификации функции частного значения для оператора WHILE. Тем не менее, мы можем ограничить себя написанием операторов WHILE, чье завершение может быть доказано специальным образом (ad hoc proof).

Аналогично, хотя механический вывод функций частного значения может быть невозможен для случаев, когда используются массивы и указатели, мы можем ограничить себя до случаев, когда возможны специальные (ad hoc) способы вывода и верификации.

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

O Pascal содержит новый тип данных, REAL, который обладает свойствами действительных чисел. Его преимущество в том, что в довольно широких пределах, числа любого размера могут обрабатываться одинаково. Его недостаток в том, что числа округляются в процессе вычисления и ошибки округления могут накапливаться и вести к неверным результатам.

19. Составные типы данных в O Pascal.

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

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

19.1. Массивы.

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

В Паскале тип данных массив описывается следующим оператором.

TYPE

ArrType = ARRAY [IndexType] OF ComponentType;

Область определения для данного массива это IndexType, а область значений – это подмножество ComponentType. В Паскале IndexType ограничен порядковыми типами иными, исключая INTEGER, так что количество значений в области определения ограничено объявлением. Переменная массива, скажем ArrVar1 или ArrVar2 может быть объявлена с данным типом, и также будет полезна переменная с типом индекса.

VAR

Index: IndexType;

ArrVar1, ArrVar2: ArrType;

Переменные массивов ставят в соответствие значениям типа IndexType значения типа ComponentType. Это соответствие достигается указанием индекса для переменной массива. Операция указания индекса в Паскале обозначается квадратными скобками, например:

ArrVar1[Index]

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

ArrVar1[Index] := CTypeValue

изменяет значение соответствия, представленного ArrVar1 в точке области определения, заданной Index на значение CTypeValue, но оставляет соответствие в остальном неизменным.

Оператор:

ArrVar1 := ArrVar2

изменяет все соответствие присваиванием всех компонентов ArrVar2 соответствующим компонентам ArrVar1.

В следующем примере, и тип и индексы массива Arr являются поддиапазоном INTEGER и оператор FOR присваивает каждому элементу в массиве значение равное его позиции. То есть этому массиву присваивается функция эквивалентности (identity function) на области определения {1, 2, 3, 4, 5}.

TYPE

Both = 1 .. 5;

VAR

I: Both;

Arr: ARRAY [Both] OF Both;

BEGIN

FOR I := 1 TO 5

DO

Arr[I] := I

END

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

CONST

Len = 20;

TYPE

Str = ARRAY [1 .. Len] OF ‘A’ .. ‘Z’;

VAR

Msg: Str;

Другой массив символов может хранить символы шифра (не только буквы) значениями индексов которого являются буквы, которые встречаются в исходном сообщении.

TYPE

Chiper = ARRAY [‘A’ .. ‘Z’] OF CHAR;

VAR

Code: Chiper;

Символы в сообщении, которые не являются большими буквами, воспроизводятся без замен.

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

Дата добавления: 2014-11-01; просмотров: 125; Нарушение авторских прав

Мы поможем в написании ваших работ!