Н. Джехани - Язык Ада (1988) (1160771), страница 15
Текст из файла (страница 15)
Метод Гаусса — Зайделя сходится вдвое быстрее метода Якоби, однако существуют ситуации, при которых метод Гаусса — Зайделя не сходится (ВАН741. Метод Гаусса — Зайделя требует меньше памяти, поскольку необходим только один массив значений. 1.10.2. Мода отсортированного массива Задача состоит в написании подпрограммы, определяющей наиболее часто встречающееся значениц называемое модой, в отсортированном массиве. Необходимо вычислить также и частоту моды. Алгоритм, использованный для вычисления моды, основан на следующем наблюдении, отмеченном Гриффитсом в (СК175) . Пусть А — это отсортированный массив с нижней границей 1.
и верхней границей Ы Частота моды МР отрезка А(Ь..1 — 1) будет отличаться от частоты моды отрезка А(Ь..1) только в случае, если А(1) = А(1 — 1) и все элементы отрезка А(1 — МЕЛ вЂ” 1) одинаковы. Из этого условия следует, что А(1) = А(1 — 1) = ... = А(1 — МР) и это отношение истинно тогда и только тогда, когда А(1) = А(1 — МР), поскольку А — отсортированный массив. Поэтому частота моды А(Ь..1) есть МР + 1, поскольку теперь в массиве А содержится МР + 1 одинаковых элементов. Мода отсортированного массива вычисляется процедурой МОВЕ, которая описывается как ргосевнге МОВЕ(А:1н 1ХТ ЧЕСТОК; МР, МЧ: ов( 1ХТЕСЕК) !я — предполагается, что А содержит хотя бы один — элемент, МЧ будет содержать моду А, — а МР будет содержать частоту МЧ при выходе из процедуры 1лсопягап! 1ХТЕСЕК:= А'Р)КЗТ; 13:сопя(ап! 1ХТЕСЕК:= А'ЬАЗТ; — границы массива не должны передаваться, — поскольку они определяются атрибутами 1:1ХТЕСЕК; Ьей!и МЧ:= А(Ь); МР:= 1; 1:=Ь+1; эгв!!е 1 < = () !вор Ы А(1) = А(1 — МР) (веп МР:= МР+ 1; Вее ение МА:= А(1); еп(1 11! 1:=1+ 1; епе( 1оор; епо МОРЕ; Тип 1ХТ ЧЕСТОК, используемый в процедуре МОРЕ, — это неограниченный регулярный тип: !уре 1ХТ ЧЕСТОК 1в аггау (1ХТЕОЕК гапйе ( >) о$' 1ХТЕСЕК; Данный алгоритм линейный, так как каждый элемент отсортированного массива просматривается в точности один раз при вычислении моды' ).
1.10.3. Ханойские башни Имеются три стержня Х, У, Х и Х дисков различных размеров. Эти диски поставлены в убывающем порядке их величин как башня на стержне Х. Задача заключается Рис. 1ЗК Ханойские башни. в переносе этих дисков со стержня Х на стержень У так, чтобы они располагались в том же убывающем порядке размеров на стержне У.
Стержень У, можно использовать как временное хранилище. За один раз можно перенести только один диск. Любой диск можно разместить на пустом стержне, и только диск меньшего размера можно поместить выше другого диска. (Диск нельзя размешать на площадке вне стержней.) Программа должна читать число дисков и печатать последовательность перестановок.
"Алгоритм вычисления моды можно сделать в среднем сублинейным, т.е. не все элементы массива необходимо просматривать при вычислении моды. Переменную! необходимо увеличить на МР, если А(1) Ф А(1 — МР), а затем просматривать массив А в обратном направлении от элемента А(1) для нахождения последовательности элементов, равных А(! — МР).
Вычисление новой моды возобновляется с этой точки. Такая реализапия была предложена дж.П. Линдерманом, моим коллегой из Ве!!-лаборатории, и др. Также были предложены модификапии, ведущие к улучшениям более быстрым, чем линейный обратный просмотр. 3' Глава 1 Алгоритм, генерируюший перестановки, следующий: Ро переместить Х вЂ” ! дисков с Х на г., используя У для временного хранения переместить Х-й диск непосредственно с Х на У переместить Х вЂ” 1 дисков с Е на У, используя Х для временного хранения.
Данный алгоритм рекурсивный, и для дальнейшей детализации необходимо включить условие останова и некоторые дополнительные детали. Рр ргосецпге Нано! (Х, Х, У, с) !в — переместить Х дисков с Х на У, — используя г, для временного хранения Ьей!п !1 ХУ = О !Ьеп — переместить Х вЂ” используя У Нано! (Х вЂ” 1, Х, 7., Переместить Х-й — переместить Х вЂ” используя Х Нано! (Х вЂ” 1, г., У, епц !1 епп — 1 дисков с Х на г., У) диск с Х на У вЂ” 1 дисков с Е на У, Х) Чтобы показать работоспособность данного алгоритма, воспользуемся принципом индукции.
Для того чтобы показать истинность утверждения Р для всех значений и > О согласно принципу индукции, необходимо показать, что 1. Р истинно для и = О. 2. Р истинно для и = Ь в предположении, что Р истинно для и = Ь вЂ” 1. зг!!Ь ТЕХТ 10; пзе ТЕХТ 10; ргосепнге ТОЪУЕКБ ОР НАХ01 !з расйайе 10 1ХТЕОЕК !з пезг 1ХТЕОЕК 10 (1ХТЕОЕК); нве 10 1ХТЕОЕК; Х1)МВЕК ОР П1БКВ:ХАТ()КА1.; — ХАТОКАЬ вЂ” это подтип типа 1ХТЕОЕК, — представляющий целые значения >О ргосейпге НАХ01 (Х:ХАТ()КА1.; Х, У, Х:СНАКАСТЕК) !з — переместить Х дисков с Х на У, — используя г.
для временного хранения Используя принцип индукции, очень просто показать, что процедура Напо! работоспособна для всех положительных значений Х. Ясно, что она работает для Х = О, потому что она ничего не делает. Предположим, что она правильно перемешает Ь вЂ” 1 дисков. Чтобы переместить Ь дисков с Х на У, процедура Нано! сначала перемещает )с — 1 дисков с Х на 7., затем она перемещает )с-й диск с Х на У. Наконец, процедура перемещает Ь вЂ” 1 дисков с Х на Х. Следовательно, )с дисков перемещаются правильно, и, согласно принципу индукции, мы заключаем„что процедура Нано! работает правильно для всех положительных Х. Полная программа (включая главную программу) имеет вид Влв вняв Ьея)п !1 Х/ = 0 ФЬеп — переместить верхние Х вЂ” 1 дисков на л., — используя У как временное хранилище НАХО! (Х вЂ” 1, Х, У„У) — выдать операторы перемещения Р()Т («Переместить диск»); Р()Т(Х); Р()Т («с»); Р(ЗТ(Х); Р()Т («на»); Р()Т(У); ХЕ% ЫХЕ; — переместить Х вЂ” 1 дисков с У.
на х', — используя на этот раз Х как временное — хранилище НАХ01 (Х вЂ” 1, У., У, Х); епй 11; епг) НАХ01; Ьей)п Р()Т («Сколько дисков необходимо переместить?»); ХЕ% ЫХЕ; ОЕТ (Х()МВЕК ОР 01ВКЕ); НАХ01 (Х(зМВЕК ОГ 01Я(б„'Х', 'У', 'У.'); епд Т0%ЕКБ ОР НАХО1; Программа разрабатывается следующим образом: Ро: Отсортировать массив А Используя рисунки, состояния массива А на различных этапах процессов сорти- ровки вставками можно изобразить так: Первоначальное состояние Г 1 Неотсортнрованная часть Отсортированная часть » третин том монографии д.кнута «искусство программирования для эвм» !кзч073! содержит исчерпываюшее обсуждение различных алгоритмов сортировки и их выполнения.
л ' Без требования перестановки достаточно изменения значения массива А„такого как присваивание 0.0 каждому элементу, поскольку условие упорядочения Аь > Аь)ь будет выполняться. 1.10.4. Сортировка вставками Используя сортировку вставками'7, необходимо написать процедуру сортировки непустого массива типа чесгог в неубывающем порядке.
Сортировка массива А с нижней границей Ь и верхней границей Щ1. < ()) приводит к получению новых значений массива Аь < Аь,з « ... Ао г < Ао в результате перестановки его старых значений~э. Тип ЧЕСТОК определяется как неограниченный индексируемый тип Гуре ЧЕСТОК !я япау (1ХТЕОЕК) гапке < >) о1 Н.ОАТ', то Глава 1 Заключительное состояние ц 1 ! ! .Э Неотсортировавная часть Отсортированная часть Некоторое промежуточное состояние [ Отсортированная часть Неотсортироааиная часть Абстрактно алгоритм сортировки вставками можно выразить так: Рз.' 1:= Ь; — А(Ь..1) уже отсортирована зтЫ!е 1/ = ()!оор Увеличить отсортированную часть, включив А(1+!) 1:=1+1; епо !оор; Т: = А(1 + 1); Сдвинуть все элементы А(1...1) > Т на одну позицию вправо так, чтобы А(Ь..
1 — 1) ( = Т и А(Х + 1..1 + 1) > Т А(Х):= Т; Второй оператор предыдушего шага Сдвинуть все элементы... детализируем так: 1:= 1+ 1; -А(1+ 1..1+ 1) > Т тгЫ!е А(Ю вЂ” 1) > Т !оор Сдвинуть А(Х вЂ” 1) вправо Л:= Л вЂ” 1; епг! 1оор; !! Инвариант цикла — зто свояство, истинное до входа в цикл, непосредственно перед и после каждого выполнения цикла, а также после завершения цикла. Правильно подобранные инварианты циклов можно использовать для доказательства правильности программ с циклами. Они также повышают гдобочитаемосгь и понимаемость программ.
А(1...1) отсортировано представляет собой инвариант цикла' !. Он истинен в начальный момент, поскольку 1 равно Ь и одноэлементная вырезка А(Ь..Ь) уже отсортирована. При завершении цикла 1 = (3 и подразумевается, что А(Ь. Ы), т. е. весь массив, отсортировано. Необходимо показать, что инвариант цикла остается неизменным при выполнении тела цикла; заинтересованного читателя отошлем к работам (ШЯ76! и [СОХ73!. Абстрактный оператор Увеличить отсортированную часть, включив А(1+ 1) шага Рз, детализируем так: 71 Вве ение Условие А(Я + 1)..1+ 1) > Т тождественно истинно до выполнения цикла, поскольку из 1 = 1 + 1 следует, что множество элементов, представляемых А(3 + 1..1+ 1), пусто.
По завершении цикла А(Я + 1..1+ 1) > Т и А(1 — 1) ( = Т. Это вместе с тем фактом, что в начале цикла А(Ь..Т) отсортировано, приводит к тому, что А(Ь..1 — 1) ( = Т. Логическое выражение в приведенном выше цикле вызывает ошибку выход за границы индекса при 3 = Ь. Когда Я = Ь, мы должны сдвинуть все элементы на одну позицию вправо и цикл должен завершиться. Поэтому логическое выражение в приведенном выше цикле модифицируется за счет использования сокращенного оператора апй !йеп, что приводит к оператору Ю/ = Ь апп !йеп А(Ю вЂ” 1) > Т Оператор Сдвинуть А(У вЂ” 1) вправо детализируется как А(1): А(Ю вЂ” 1); Собрав все детализации вместе и добавив соответствующий заголовок процедуры, переменные и константы, получаем окончательный вариант процедуры 1ХЯЕКТ1ОХ ЗОКТ: ргосеопге 1ХЯЕКТ1ОХ ЯОКТ (А:1п оп! ЧЕСТОК) !в 1, Я:А'КАХОЕ; Т:РЬОАТ; Ь:сопя!ап! 1ХТЕОЕК: = А'Е1КЯТ; (3:сопя(ап! 1ХТЕОЕК: = А'ЬАБТ; )гей!п 1:= 1.; иЫ1е 1/ = О 1оор Т:= А(1+ 1); 3:=1+ 1; и Ы)е 1/ = Ь апо Свеи А(1 — 1) > Т 1оор А(1):= А(1 — 1); Я:= 3 — 1; епй !оор; А(1): = Т', 1:=1+ 1; епо 1оор; епе) 1ХБЕКТ1ОХ БОКТ; 1.10.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
