Алгоритмы - построение и анализ (1021735), страница 11
Текст из файла (страница 11)
на одну позицию вправо до тех пор, пока не освободится подходящее место для элемента А [7] (строки 4 — 7), куда он и помещается (строка 8). При более формальном подходе к рассмотрению второго свойства потребовалось бы сформулировать и обосновать инвариант для внутреннего цикла туЫ1е. Однако на данном этапе мы предпочитаем не вдаваться в такие формальные подробности, поэтому будем довольствоваться неформальным анализом, чтобы показать, что во внешнем цикле соблюдается второе свойство. Завершение. Наконец, посмотрим, что происходит по завершении работы цикла.
При сортировке методом включений внешний цикл гог завершается, когда 7' превышает и, т.е. когда з = гг + 1. Подставив в формулировку инварианта цикла значение и + 1, получим такое утверждение: в подмножестве элементов А [1..п] находятся те же элементы, которые были в нем до начала работы алгоритма, но расположенные в отсортированном порядке. Однако подмножество А [1..п] и есть сам массив А1 Таким образом, весь массив отсортирован, что и подтверждает корректность алгоритма. Метод инвариантов циклов будет применяться далее в данной главе, а также в последующих главах книги. Соглашения, принятые при составлении псевдокода При составлении псевдокода использовались следующие соглашения. 1. Структура блоков указывается с помощью отступов.
Например, тело цикла 1ог, начало которого — в строке 1, образовано строками 2 — 8, а тело цикла ттЫ)е, который начинается в строке 5, состоит из строк 6 и 7, а строка 8 в него не входит. Стиль отступов имеет силу также в инструкциях 1т"4Ьеп-е1ве. Использование отступов вместо общепринятых указателей блочной структуры, таких как инструкции Ьей1п и епй, значительно уменьшает громоздкость. При этом псевдокод не становится менее понятным, а даже наоборот'. цикла, но перел первой проверкой в заголовочной инструкции цикла.
В листинге 1изпптюи бовт зто момент, когда переменной у присвоено значение 2, но еще не выполнена проверка неравенства у ~ <меняй [А]. В реальных языках программирования, вообще говоря, не рекомендуется применять отступы для того, чтобы подчеркнуть структуру блоков, поскольку, если код разбит на несколько страниц, то сложно определить уровень вложенности блоков. Часть!. Основы Инструкции циклов иййе, аког и гереат, а также общепринятая конструкция 11'-Фел-е!ве интерпретируются аналогично одноименным инструкциям языка Равса1з. Что касается цикла 1ог, то здесь есть одно тонкое различие: в языке Рааса) после выхода из цикла значение переменной, выступающей в роли счетчика цикла, становится неопределенным, а в данной книге счетчик сохраняет свое значение после выхода из цикла.
Таким образом, сразу после завершения цикла 1ог значение счетчика равно значению, на единицу превышающему верхнюю границу цикла. Это свойство уже использова- лось для доказательства корректности алгоритма сортировки, работающего по методу вставок. Заголовок цикла Гог, заданный в строке 1, имеет вид 1ог з - 2 то 1епдй[А], поэтому по завершении цикла т' = 1епдй[А]+1 (или, что то же самое, д = и + 1). Символ "с " указывают, что оставшаяся часть строки — это комментарий. Множественное прнсваивание, имеющее вид т - д < — е, обозначает, что значение выражения е присваивается обеим переменным з' и д; оно аналогично двум последовательным инструкциям присваивания: д — е и з Переменные (такие как з, д и кеу) являются локальными по отношению к данной процедуре.
Глобальные переменные не применяются, если это не указано явным образом. 3. 4. 5. Доступ к элементам массива осуществляется путем указания имени массива, после которого в квадратных скобках следует индекс. Например, А [з]— это обозначение з-го элемента массива А. С помощью обозначения ".." указывается интервал значений, которые принимает индекс массива. Таким образом, обозначение А [1.. Я свидетельствует о том, что данное подмножество массива А состоит из д элементов А [1], А [2],..., А [у].
Сложные данные обычно представляются в виде объакагов, состоящих из аагрибуагов и налей. Доступ к определенному полю осуществляется с помощью имени поля, после которого в квадратных скобках указывается имя объекта. Например, массив трактуется как объект с атрибутом 1епдй, указывающим количество его элементов.
Чтобы указать количество элементов массива А, нужно написать 1епдй [А]. Несмотря на то, что квадратные скобки используются и для индексирования элементов массива, и в атрибутах объекта, их интерпретация будет понятна из контекста. Переменная, которая используется в качестве имени массива или объекта, б. 7. трактуется как указатель на данные, представляющие этот массив или объект. Для всех полей у" объекта х присваивание у ь- х приводит к тому, что у [у] = 7" [х]. Более того, если теперь выполнить присваивание 7" [х] — 3, 'Инструкннн, зквнвалентные перечнсленным, есть в болынннстве языков программирования с блочной структурой, однако нк синтаксис может немного отлнчатьсв от синтаксиса языка Разсай Глава 2. Приступаем к изучению 63 то впоследствии будет выполняться не только соотношение г (х) = 3, но и соотношение г (у) = 3.
Другими словами, после присваивания у — х переменные х и у указывают на один и тот же объект. Иногда указатель вообще не ссылается ни на какой объект. В таком случае он имеет специальное значение нц.. 8. Параметры передаются в процедуру ло значению: в вызывающей процедуре создается своя собственная копия параметров, и если в вызванной процедуре какому-то параметру присваивается значение, то в вызывающей процедуре не происходит никаких изменений. Если передаются объекты, то происходит копирование указателя на данные, представляющие этот объект, но поля объекта не копируются.
Например, если х — параметр вызванной процедуры, то присваивание х — у, выполненное в этой процедуре, невидимо для вызывающей процедуры. Однако присваивание г )х) - 3 будет видимым. 9. Логические операторы "и" и "или" вычисляются сокращенно (зЬоп с1гсцйшй). Это означает, что при вычислении выражения "х и у" сначала вычисляется значение выражения х. Если оно ложно, то все выражение не может быть истинным, и значение выражения у не вычисляется.
Если же выражение х истинно, то для определения значения всего выражения необходимо вычислить выражение у. Аналогично, в выражении "х или у" величина у вычисляется только в том случае, если выражение х ложно. Сокращенные операторы позволяют составлять такие логические выражения, как "х ф мп. и г" )х] = у", не беспокоясь о том, что произойдет при попытке вычислить выражение г (х), если х = мц..
Упражнения 2.1-1. Используя в качестве модели рис. 2.2, проиллюстрируйте работу алгоритма 1ыкктю1ч Бокт по упорядочению массива А = (31, 41, 59, 26, 41, 58). 2.1-2. Перепишите процедуру 1мзектюм Бокт так, чтобы она выполняла сортировку не в невозрастающем, а в неубывающем порядке. 2.1-3. Рассмотрим задачу поиска. Вход: последовательность и чисел А = (ам аз,...,о ) и величина и. Выход: индекс з, обладающий свойством о = А [з], или значение ьл[., если в массиве А отсутствует значение о. Составьте псевдокод лилейного поиска, при работе которого выполняется сканирование последовательности в поиске значения е.
Докажите корректность алгоритма с помощью инварианта цикла. Убедитесь, что 64 Часть 1. Основы выбранные инварианты цикла удовлетворяют трем необходимым условиям. 2.1-4. Рассмотрим задачу сложения двух двоичных целых чисел длиной и битов каждое, хранящихся в массивах А и В, которые состоят из п элементов. Сумму этих двух чисел необходимо занести в двоичной форме в массив С, состоящий из и + 1 элемента. Приведите строгую формулировку задачи и составьте псевдокод для сложения этих двух чисел.
2.2 Анализ алгоритмов Анализ алгоритма заключается в том, чтобы предсказать требуемые для его выполнения ресурсы. Иногда оценивается потребность в таких ресурсах, как память, пропускная способность сети или необходимое аппаратное обеспечение, но чаще всего определяется время вычисления. Путем анализа нескольких алгоритмов, предназначенных для решения одной и той же задачи, можно без труда выбрать наиболее эффективный.
В процессе такого анализа может также оказаться, что несколько алгоритмов примерно равноценны, а все остальные нужно отбросить. Прежде чем мы научимся анализировать алгоритмы, необходимо разработать технологию, которая будет для этого использоваться. В эту технологию нужно будет включить модель ресурсов и величины их измерения. С учетом того, что алгоритмы реализуются в виде компьютерных программ, в этой книге в большинстве случаев в качестве технологии реализации принята модель обобщенной однопроцессорной машины с памятью с лроизвольным достуном (йапдош-Ассезз Мас)ппе — ВАМ).
В этой модели команды процессора выполняются последовательно; одновременно выполняемые операции отсутствуют. Строго говоря, в модели ВАМ следует точно определить набор инструкций и время их выполнения, однако это утомительно и мало способствует пониманию принципов разработки и анализа алгоритмов. С другой стороны, нужно соблюдать осторожность, чтобы не исказить модель ВАМ. Например, что будет, если в ВАМ встроена команда сортировки? В этом случае сортировку можно выполнять с помощью всего одной команды процессора. Такая модель нереалистична, поскольку настоящие компьютеры не имеют подобных встроенных команд, а мы ориентируемся именно на их устройство.
В рассматриваемую модель входят те команды, которые обычно можно найти в реальных компьютерах: арифметические (сложение, вычитание, умножение, деление, вычисление остатка деления, приближение действительного числа ближайшим меньшим или ближайшим большим целым), операции перемещения данных (загрузка, занесение в память, копирование) и управляющие (условное и безусловное ветвление, вызов подпрограммы и воз- Глава 2. Приступаем к изучению 65 врат из нее). Для выполнения каждой такой инструкции требуется определенный фиксированный промежуток времени. В модели ВАМ есть целочисленный тип данных и тип чисел с плавающей точкой. Несмотря на то, что обычно в этой книге точность не рассматривается, в некоторых приложениях она играет важную роль.
Также предполагается, что существует верхний предел размера слова данных. Например, если обрабатываются входные данные с максимальным значением п, обычно предполагается, что целые числа представлены с1кп битами, где с — некоторая константа, не меньшая единицы. Требование с > 1 обусловлено тем, что в каждом слове должно храниться одно из п значений, что позволит индексировать входные элементы. Кроме того, предполагается, что с — это конечная константа, поэтому объем слова не может увеличиваться до бесконечности. (Если бы это было возможно, в одном слове можно было бы хранить данные огромных объемов и осуществлять над ними операции в рамках одной элементарной команды, что нереально.) В реальных компьютерах содержатся команды, не упомянутые выше, которые представляют "серую область" модели ВАМ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
