Главная » Просмотр файлов » Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.)

Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 11

Файл №1123758 Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.)) 11 страницаТ. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758) страница 112019-05-10СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

Чтобы определить, куда нужно поместить очередную карту, ее масть и достоинство сравнивается с мастью и достоинством карт в руке. Допустим, сравнение проводится в направлении слева направо (рис. 2.1). В любой момент времени карты в левой руке будут рассортированы, и это будут те карты, которые первоначально лежали в стопке на столе. Глава 2. Приступаем к изучению 59 Псевдокод сортировки методом вставок представлен ниже под названием 1мзнкт)ом Яокт. На его вход подается массив А [1..],, содержащий последовательность из п сортируемых чисел (количество элементов массива А обозначено в этом коде как 1епдбй [А].) Входные числа сортируюпася без использования дополнительной памяти: их перестановка производится в пределах массива, и объем используемой при этом дополнительной памяти не превышает некоторую постоянную величину.

По окончании работы алгоритма 1мзвкт)ом Зонт входной массив содержит отсортированную последовательность: 1мзект)ом Болт(А) 1 1ог 2' — 2 2о 1епдгй[А] 2 йо кеу — А[7] 3 с Вставка элемента А[7] в отсортированную с последовательность А [1..7' — 1] 4 в -7 — 1 5 и)Н1е в > О и А[а] > кеу 6 41о А[в+ 1] — А[в] 7 — в — 1 8 А[в+ 1] — кеу Инварианты цикла и корректность сортировки вставкой На рис.

2.2 продемонстрировано, как этот алгоритм работает для массива А = (5,2,4,6, 1, 3). Элементы массива обозначены квадратиками, над которыми находятся индексы, а внутри — значения соответствую)цих элементов. Части а-д этого рисунка соответствуют итерациям цикла 1ог в строках 1-8 псевдокода. В каждой итерации черный квадратик содержит значение ключа, которое сравнивается со значениями серых квадратиков, расположенных слева от него (строка псевдокода 5). Серыми стрелками указаны те значения массива, которые сдвигаются на одну позицию вправо (строка 6), а черной стрелкой — перемещение ключа (строка 8).

В части е показано конечное состояние сортируемого массива. ! 2 3 4 5 6 а) 4 б ! 3 ! 2 3 4 5 б б) ' ' 6 ! 3 ! 2 3 4 5 6 в) 2 4'л ! 3 ! 2 3 4 5 6 ! 2 3 4 5 б )! 3 13 3 3 Д Рис. 2.2. Выполнение алгоритма 1мзвктюм Болт нал массивом А = (5,2,4,6,1,3) 60 Часть!. Основы Индекс т' указывает "текущую карту*', которая помещается в руку. В начале каждой итерации внешнего цикла 1ог с индексом у массив А состоит из двух частей.

Элементы А (1..у — 1] соответствуют отсортированным картам в руке, а элементы А [у + 1..п] — стопке карт, которые пока что остались на столе. Заметим, что элементы А [1..у — 1] изначально тоже находились на позициях от 1 до у — 1, но в другом порядке, а теперь они отсортированы. Назовем это свойство элементов А [1..) — 1] инвариантам цикла (1оор 1пчаг)апт) и сформулируем его еще раз. В начале каждой итерации цикла 1ог из строк 1-8 подмассив А [1.. у — 1] содержит те же элементы, которые были в нем с самого начала, но расположенные в отсортированном порядке. Инварианты цикла позволяют понять, корректно ли работает алгоритм.

Необходимо показать, что инварианты циклов обладают следующими тремя свойствамн. Инициализация. Они справедливы перед первой инициализацией цикла. Сохранение. Если онн истинны перед очередной итерацией цикла, то остаются истинны и после нее.

Завершение. По завершении цикла инварианты позволяют убедиться в правильности алгоритма. Если выполняются первые два свойства, инварианты цикла остаются истинными перед каждой очередной итерацией цикла. Обратите внимание на сходство с математической индукцией, когда для доказательства определенного свойства для всех элементов упорядоченной последовательности нужно доказать его справедливость для начального элемента этой последовательности, а затем обосновать шаг индукции. В данном случае первой части доказательства соответствует обоснование того, что инвариант цикла выполняется перед первой итерацией, а второй части — доказательство того, что инвариант цикла выполняется после очередной итерации (шаг индукции).

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

В данном случае по окончании цикла "индукция" завершается. Рассмотрим, соблюдаются ли эти свойства для сортировки методом включений. Инициализация. Начнем с того, что покажем справедливость инварианта цикла перед первой итерацией, т.е. при у' = 2'. Таким образом, подмножество элементов А [1..у — 1] состоит только из одного элемента А [1], сохраняющего ' Если рассматривается цикл Гог, момент времени, когда проверяется справедливость инварианта цикла перел первой итерацией, наступает сразу после начального присваивания значения индексу Глава 2. Приступаем к изучению 61 исходное значение.

Более того, в этом подмножестве элементы рассортированы (тривиальное утверждение). Все вышесказанное подтверждает, что инвариант цикла соблюдается перед первой итерацией цикла. Сохранение. Далее, обоснуем второе свойство: покажем, что инвариант цикла сохраняется после каждой итерации. Выражаясь неформально, можно сказать, что в теле внешнего цикла Гог происходит сдвиг элементов А [у — Ц, А [7' — 2], А [7' — 3], ...

на одну позицию вправо до тех пор, пока не освободится подходящее место для элемента А [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.

Характеристики

Список файлов книги

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6553
Авторов
на СтудИзбе
299
Средний доход
с одного платного файла
Обучение Подробнее