1611678431-0e68e83522cb9d960ac896aa5d90854d (Билеты - Ответы), страница 7

4.3. В ней штриховыми линиямивыделены все ее структурные операторы.Рис. 4.3. Блок-схема программы СуммаЭлементовПоследовательности1Теперь у нас имеется достаточно средств, чтобы записать на языке Zonnonалгоритм Евклида, рассмотренный п.1.1.3:module НаибольшийОбщийДелитель;var A,B,C : integer;beginread (A,B); (* {A>0, B>0} *)while A # B doif A < B then C := A; A := B; B := C end;A := A - Bend;write(A)end НаибольшийОбщийДелитель.19. Понятие полной правильности. Ограничивающие выражения для цикловИнвариант и ограничивающая функция циклаОсновная идея метода проектирования цикла при помощи инварианта -выражение взаимосвязи между меняющимися в теле цикла объектами в виденеизменного условия. Польза инварианта состоит в том, что такое описаниевзаимосвязи легко понимаемо и позволяет, зная, как меняются одниобъекты, выводить, как должны изменяться другие.

Тем самым инвариантпомогает сконструировать команды S0 и S.Определение 1.1 Инвариант цикла-- предикат, которыйистинен перед выполнением цикла и после каждой его итерации.Любая тавтология является инвариантом произвольного цикла, однако такиеинварианты бесполезны для целей проектирования программ.Вопросы построения инвариантов будут исследованы в следующем параграфе,а сейчас рассмотрим определение еще одного важнейшего понятия.Для построения корректного условия продолженияцикла e используется ограничивающая функция .

При каждом шаге циклазначениедолжно уменьшаться по крайней мере на единицу и оставатьсяположительным до завершения цикла. Ограничивающая функция позволяетгарантировать завершение цикла.Определение 1.2 Ограничивающая функция-- неотрицательнаяфункция, являющаяся верхней границей числа оставшихся итераций цикла.Схема проектирования цикла при помощи инварианта. На первом этапе выполняютсяпростые присваивания S0, делающие инвариантистинным, а в качествеусловия продолжения цикла e берется предикат. На втором этапеконструируется тело цикла S, реализующее преобразование : сначалаобеспечивается уменьшение ограничивающей функции , а затем -- сохранениеинварианта .Геометрическая интерпретация данной схемы приведена на рисунке 3, гдечерезобозначено множество, получающееся изсовокупности присваиваний S0.с помощьюРисунок 3: Проектирование цикла при помощи инвариантаРассмотрим применение этой схемы для решения следующей задачи.Решение. Для написания программы надо сконструировать S0 (совокупностьприсваиваний, осуществляющих начальную инициализацию), условиепродолжения e и тело цикла S.Начальные присваивания должны сделать истинным инвариант (в случаеистинности предусловия) и при этом быть максимально простыми и легконаходимыми.

В данном случае достаточно быстро можно обнаружить, чтохорошим кандидатом на роль S0 явлется следующая совокупностьприсваиваний "x=a;y=b;z=0;".Условие продолжения цикла e нам уже по-существу дано, так как очереднаяитерация цикла должна происходить только при. По этой причинелогично предположить, что наша программа должна содержатьоператор "while(y>0)S;", тело которого S пока неизвестно.Мы обязаны обеспечить завершение цикла, следовательно величинауменьшаться на каждой его итерации. Уменьшениедолжнакаждый раз на единицузаведомо не позволит получить достаточно эффективную программу. По этойпричине необходимо уменьшать величинуявляется попытка делить величинучетныхболее быстро. Хорошей мысльюпополам тогда, когда это можно (при). Легко оценить, что если бы деление пополам происходило накаждом шаге цикла, то количество его итераций было бы примерно равноЭто вполне согласуется с тем, что требуется в решаемой задаче..Так как после итерации цикла инвариант должен остаться истинным, то ужезная, как меняется , вычисляем, как следует изменять (ибо по условиюзадачи мы не можем изменять и).

В результате находим (либо в уме, либоформально вычисляя), что при четных величину следует удваивать, апри нечетных -- необходимо увеличивать значение переменной на .Программа написана!Текст программы.public class MulI {public static void main(String[] args) throws Exception {int a = Xterm.inputInt("a -> ");int b = Xterm.inputInt("b -> ");int x = a, y = b, z = 0;while (y > 0) {if ((y&1) == 0) {y >>>= 1; x += x;} else {y -= 1; z += x;}}Xterm.println("a * b = " + z);}}20.

Массивы в языке Паскаль, их представление на машинном уровне, упаковка и выравнивание,три вида массивов в языках программирования5.2.1 МассивыНаиболее распространенный в языках программирования способ образованиясоставных объектов -- это объединение некоторого фиксированного числаоднотипных объектов в новый объект, называемый массивом. Объединяемыеобъекты -- элементы массива -- снабжаются так называемыми индексами,различающими элементы массива между собой и позволяющими выбиратьпроизвольный элемент массива по его индексу. Массивы могутиндексироваться либо положительным целым числом, либо значениемперечисляемого типа.

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

Тип массивов определяется синтаксическими правилами,приведенными на рис. 5.5.ArrayType = array (Expression | NameType) of Type.Рис. 5.5. Синтаксис типов массивовНапример, можно определить:type СЛОВО = array100 of char;var А,AA:СЛОВО;где тип СЛОВО -- это все возможные последовательности литер длины 100,элементы каждой из которых занумерованы числами от 0 до 99. ДопустимыоператорыA:=AA; D:=(B=BB)&(C#CC);в которых значения массивов обрабатываются целиком. Помимо этого, любаяпеременная типа массивов рассматривается как совокупность переменных,носящих общее имя и различающихся индексами -- так называемых переменныхс индексами.

Например, массив А состоит из 100 элементов -- переменных А[0],A[1],,A[99], каждая из которых имеет тип char. При этом допускаетсяприсваивание значения отдельным переменным с индексами (элементаммассива, например, A[2]). В частности, оператор присваиванияA[2] := 'A'заменяет в переменной A текущее значение 2-го элемента (т.е. элемента синдексом 2) на значение 'A'.ArrayName "[" Expression { "," Expression } "]"Рис. 5.6.

Синтаксис переменной с индексамиТо, что индексы массива, т.е. "имена" его элементов, образуют некоторыйотрезок целого типа, имеет весьма важные следствия. Индексы могутвычисляться, допускается использование вместо индексных константиндексных выражений. Значение такого выражения и определяет выбираемыйэлемент. Синтаксис переменной с индексами задает синтаксическая диаграммарис.

5.6. Например, операторA[K] := 'В'присваивает 'В' элементу массива А с индексом 1, если К = 1, элементу массиваА с индексом 2, если К = 2, и т.д.Возможность вычисления индекса элемента массива является одним изважнейших и мощных средств программирования (заметим, что памятьбольшинства существующих ЭВМ -- это массив ячеек памяти, в котором рольиндексов играют адреса ячеек памяти), но очень часто приводит к ошибкам впрограмме, связанным с ошибочными обращениями к несуществующимэлементам массива.В качестве примера использования массива рассмотрим программу обращениязаданного слова длины 1000 (т.е. выписывания в обратном порядке 1000символов, составляющих входное слово).module ОБРАЩЕНИЕ;const ДЛИНА = 1000;type СЛОВО = array ДЛИНА of char;var A:СЛОВО; К:НОМЕР ;beginfor K := 0 to ДЛИНА-1 do read(A[K]) end;for K := ДЛИНА-1 to 0 by -1 do write(A[K]) endend.3 типа массивов:1.

Статические массивыТип статического массива конструируется следующим образом:array [тип индекса1, ..., тип индексаN] of базовый типТип индекса должен быть порядковым. Обычно тип индекса является диапазонным и представляется ввиде a..b, где a и b - константные выражения целого, символьного или перечислимого типа. Например:typeMyEnum = (w1,w2,w3,w4,w5);Arr = array [1..10] of integer;vara1,a2: Arr;b: array ['a'..'z',w2..w4] of string;c: array [1..3] of array [1..4] of real;При описании можно также задавать инициализацию массива значениями:vara: Arr := (1,2,3,4,5,6,7,8,9,0);cc: array [1..3,1..4] of real := ((1,2,3,4), (5,6,7,8), (9,0,1,2));Статические массивы одного типа можно присваивать друг другу, при этом будет производиться копированиесодержимого одного массива в другой:a1:=a2;При передаче статического массива в подпрограмму по значению также производится копированиесодержимого массива - фактического параметра в массив - формальный параметр:procedure p(a: Arr);...p(a1);Как правило, в этой ситуации копирование не требуется, поэтому статический массив рекомендуетсяпередавать по ссылке:procedure p1(var a: Arr);...r(a1);2.

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

Динамические массивы дают возможность более гибкой работы с данными, таккак позволяют не прогнозировать хранимые объёмы данных, а регулировать размермассива в соответствии с реально необходимыми объёмами. Обычные, не динамическиемассивы называют ещё статическими.Пример динамического массива на ПаскалеbyteArray : Array of Byte; // Одномерный массивmultiArray : Array of Array of string; // Многомерный массивДинамические массивыВо FreePascal, Delphi добавлена интересная возможность описания массивов без указанияразмерностей и, соответственно, пределов изменения индексов:varIntArray: array of integer;Такие массивы являются динамическими и изначально имеют нулевую длину. Установка размерамассива и определение его во время выполнения программы производится так же как и для строк,с помощью функций SetLength и Length, соответственно.

Элементы в данном случае нумеруютсяот нуля.program UsingDynamicArrays1;varА, В: Array of Integer;{Описание двух переменных — динамическихмассивов целочисленных элементов}beginSetLength(A, 5);{Установка размера массива А(5 элементов) }А[0] := 1;{Присвоение значения 1 элементумассива А с номером 0 }end.Переменные-динамические массивы являются указателями и операции с ними производятся как суказателями. Например, при присвоении одного массива другому элементы одного массива некопируются во второй, а копируется адрес массива.