Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 8
Текст из файла (страница 8)
п] — стопке карт, которые пока что остались на столе. Заметим, что элементы А[1..3 — 1] изначально также находились в позициях от 1 до у — 1, но в друтом порядке, однако теперь они отсортированы. Назовем зто свойство элементов А[1 .. у — 1] ннварнандван цикла ()оор гпчапап() и сформулируем его еше раз.
4! Лдааа 2. Лристулаеи к изучению Инварианты цикла позволяют понять, корректно ли работает алгоритм. Необходимо показать, что инварианты циклов обладают следующими тремя свойствами. Инициализация. Онн справедливы перед первой итерацией цикла. Сохранение. Если они истинны перед очередной итерацией цикла, то остаются истинны и после нее. Завершение.
По завершении цикла инварианты позволяют убедиться в правильности алгоритма. Если выполняются первые два свойства, инварианты цикла остаются истинными перед каждой очередной итерацией цикла. (Конечно, для доказательства того, что инвариант остается истинным перед каждой итерацией, можно использовать любые другие установленные факты, помимо самогб инварианта.) Обратите внимание на сходство с математической индукцией, когда для доказательства определенного свойства для всех элементов упорядоченной последовательности нужно доказать его справедливость для начального элемента этой последовательности, а затем обосновать шаг индукции. В данном случае первой части доказательства соответствует обоснование того, что инвариант цикла выполняется перед первой итерацией, а второй части — доказательство того, что инвариант цикла выполняется после очередной итерации (шаг индукции).
Для наших целей третье свойство, пожалуй, самое важное, так как нам нужно с помощью инварианта цикла продемонстрировать корректность алгоритма. Обычно инвариант цикла используется вместе с условием, заставляющим цикл завершиться. Свойство завершения отличает рассматриваемый нами метод от обычной математической индукции, в которой шаг индукции используется в бесконечных последовательностях. В данном случае по окончании цикла миндукция" останавливается. Рассмотрим, соблюдаются ли эти свойства для сортировки методом вставки. Инициализация.
Начнем с того, что покажем справедливость инварианта цикла перед первой итерацией, те. при!' = 2.' Таким образом, подмассив А[1..у в 1] состоит только из одного элемента А[1], сохраняющего исходное значение. Более того, в этом подмножестве элементы рассортированы (тривиальное утверждение).
Все вышесказанное подтверждает, что инвариант цикла соблюдается перед первой итерацией цикла. Сохранение. Далее обоснуем второе свойство: покажем, что инвариант цикла сохраняется после каждой итерации. Выражаясь неформально, можно сказать, что в теле внешнего цикла 1ог происходит сдвиг элементов А[у — 1], А[у — 2], 'Если рассматриваетс» цикл Гог, момент времени, югда проверлетс» справедливость ннварианта цикла перед первой итерацией, наступает сразу после начального присваивания значении индексу цикла, непосредственно перед первой проверюй в зыочовочной инструкции цикла.
В процедуре !изкктюи-Зокт зто момент, когда переменной З присвоено значение Х но еще не выполнена проверка неравенства З < А.!епд Ь. Часть й Основы А[у — 3],... на одну позицию вправо до тех пор, пока не освободится подходящее место для элемента АЦ (строки 4 — 7), куда и вставляется значение А[у] (строка 8). Подмассив А[1 .. Я после этого состоит из элементов, изначально находившихся в А[1 .. 7], но в отсортированном порядке.
Следующее за этим увеличение 7 для следующей итерации цикла Гог сохраняет инвариант цикла. При более формальном подходе к рассмотрению второго свойства потребовалось бы сформулировать и обосновать инвариант для внутреннего цикла ууЬйе в строках 5 — 7. Однако на данном этапе мы предпочитаем не вдаваться в такие формальные подробности, поэтому будем довольствоваться неформальным анализом, чтобы показать, что для внешнего цикла соблюдается второе свойство инварианта цикла. Завершенне. Наконец посмотрим, что происходит по завершении работы цикла.
Условие, приводящее к завершению цикла Гог, — 7' > А. 1епдй = и. Поскольку каждая итерация цикла увеличивает у на 1, мы должны в этот момент иметь 7' = и + 1, Подставив в формулировку инварианта цикла вместо 7' значение п+1, получим, что подмассив А[1 .. и] состоит из элементов, изначально находившихся в А[1 ., и], но расположенных в отсортированном порядке. Заметим, что подмассив А[1 .. и] и есть сам массив А, так что весь массив отсортирован, а следовательно, алгоритм корректен. Метод инвариантов циклов будет применяться далее в данной главе, а также в последующих щавах книги.
Соглашения, принятые при составлении псевдокода При составлении псевдокода используются следующие соглашения. Блочная структура указывается с помощью отступов. Например, тело цикла Гог, начинающегося в строке 1, состоит из строк 2-8, а тело цикла ууЬйе, начинающегося в строке 5, содержит строки б и 7, но не строку 8. Наш способ применения отступов применим и к инструкциям 1Г-е!ае~.
Применение отступов вместо явного указания блочной структуры, такого, как с использованием ключевых слов Ье81п и епд, существенно уменьшает зашумленность кода при сохранении или даже при повышении его понятностиз. Конструкции циклов ьчЬИе, Гог и гереа1-пп61, а также условная конструкция 1Г-е!ае интерпретируются, как в языках программирования С, С++, )ана, РутЬоп зв инструкции !Г-еае мы смешаем блок еье точно так же, как и соотвегствуюший ему блок И.
Хотя мы опускаем слово Гйеп, мы время ат времени ссылаемся на часть кода, выполняемую, когда проверка И оказывается истинной, как на дяак Гйел В случае тестов с ветвлением мы используем климевое слова е!веИ двя проверок, следуюших за первой. зв втой книге кюядвя процедура, записанная с применением псевдокода, располаается на одной странице, так чта у вас не будет проблем с угадыванием уровня отступа в коде, размешеннам на нескольких страницах. гнала 2. Приступаем к изучению 4з и Рааса!4.
В этой книге счетчик цикла сохраняет свое значение после выхода из цикла, в отличие от некоторых ситуаций, встречающихся в языках С-н., 1ауа и Рааса!. Таким образом, непосредственно после цикла Гог значение его счетчика представляет собой значение, которое впервые превышает границу цикла 1ог. Мы использовали это свойство в нашем доказательстве корректности сортировки вставкой. Заголовок цикла Гог в строке 1 имеет вид Гог д' = 2 яо А. 1епдй, так что, когда цикл завершает работу, у = А. 1епдй+ 1 (илн, что то же самое, д = и+ 1, поскольку и = А. 1епдй). Мы используем ключевое слово то, когда цикл Гог увеличивает значение счетчика цикла на каждой итерации, и слово боугппу, когда на каждой итерации цикла Гог значение счетчика уменьшается.
Когда значение счетчика цикла изменяется на значение, большее 1, это значение следует за необязательным ключевым словом Ьу, ° Символ "//" указывает, что остальная часть строки представляет собой комментарий. Множественное присваивание видав = у = е присваивает обеим переменным з и д значение выражения е; его следует рассматривать как эквивалентное присваиванию д = е, за жзторым следует присваивание 1 = р. ° Переменные Гтакне, как з, д или Ьед) являются локальными для данной процедуры. Мы не будем использовать глобальные переменные без явного указания этого факта.
Доступ к элементам массива осуществляется путем указания имени массива, за юторым в квадратных скобках следует индекс. Например, А[з] указывает з-й элемент массива А. Запись ".." используется для того, чтобы указать диапазон значений индексов массива. Так, А[1..Я определяет подмассив массива А, состоящий из д элементов А[1], А[2],..., А[д]. Составные данные мы обычно организуем в объеквуы, которые состоят из аязрибугвов. К определенному атрибуту объекта мы обращаемся с применением синтаксиса, имеющегося во многих объектно-ориентированньгх языках программирования: за именем объекта следует точка, за которой следует имя атрибута. Например, мы рассматриваем массив как объект с атрибутом 1елдй, указывающим количество содержащихся в нем элементов.
Чтобы указать количество элементов в массиве А, мы записываем А. 1епдй. Мы рассматриваем переменную, представляющую массив или обьект, как указатель на данные, представляющие этот массив или объект. Для всех атрибутов Г обьекта х присваивание д = х приводит к тому, что у.
Г становится равным х.1. Более того, если мы теперь установим х. Г = 3, то после этого не только х. Г будет равным 3, но и у. Г также станет равным 3. Другими словами, х и у после присваивания у = х указывают на один и тот же объект. Большинство яззпюв с блочной структурой имеют зквивалентные конструкции, котя точные ия синтыюисы могут различатъся. В языке рузьоп отсуитвукп циклы гереаг-нигв, а его циклы йгг работают немного не так, как циклы рог в ягой книге. Часть 1 Основы Запись атрибутов может быть "каскадной".
Например, предположим, что атрибут 1 сам по себе является указателем на объект некоторого типа, который имеет атрибут д. Тогда запись х.1.д неявно подразумевает наличие скобок (х.1).д. Другими словами, если мы присвоим у = х.1, то х.1. д будет тем же, что и у.д. Иногда указатель вообще не ссылается ни на какой объект. В таком случае он имеет специальное значение мп.. Параметры в процедуру передаются по значению: вызываемая процедура получает собственную копию параметров, и если она присваивает параметру зна- чение, то это изменение не будет видимым для вызывающей процедуры. При передаче объектов копируется указатель на представляюшие объект данные, но не атрибуты объекта. Например, если х представляет собой параметр вызываемой процедуры, присваивание х = у в вызываемой процедуре не будет видимым для вызывающей процедуры. Однако присваивание х.1 = 3 является видимым.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
