Файл: Алгоритмы и структуры данныхНовая версия для Оберона cdмосква, 2010Никлаус ВиртПеревод с английского под редакцией.pdf

Скачать файл (2,67Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 30.11.2023

Просмотров: 228

Скачиваний: 3

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

СОДЕРЖАНИЕ

1.7.2. Буферизация последовательностейКогда данные пересылаются со внешнего устройства хранения или на него, от%дельные биты передаются потоком. Обычно устройство налагает строгие времен%ные ограничения на пересылку данных. Например, если данные записываются на ленту, лента движется с фиксированной скоростью, и нужно, чтобы данные пере%давались ей тоже с фиксированной скоростью. Когда источник данных исчерпан,Файлы или последовательности Фундаментальные структуры данных42движение ленты прекращается, и ее скорость падает быстро, но не мгновенно.Поэтому на ленте остается промежуток между уже записанными данными и дан%ными, которые поступят позже. Чтобы добиться высокой плотности данных, нуж%но, чтобы число промежутков было мало, и для этого данные передают относи%тельно большими блоками, чтобы не прерывать движения ленты. Похожие требования имеют место при работе с магнитными дисками, где данные размеща%ются на дорожках с фиксированным числом блоков фиксированного размера. На самом деле диск следует рассматривать как массив блоков, причем каждый блок читается или записывается целиком и обычно содержит 2k байтов с k = 8, 9, … 12Однако в наших программах не соблюдается никаких временных ограничений.Чтобы обеспечить такую возможность, передаваемые данные буферизуются. Они накапливаются в переменной%буфере (в оперативной памяти) и пересылаются, ког%да накапливается достаточно данных, чтобы собрать блок нужного размера. Клиент буфера имеет к нему доступ только посредством двух процедур deposit и fetch:DEFINITION Buffer;PROCEDURE deposit (x: CHAR);PROCEDURE fetch (VAR x: CHAR);END Buffer.Буферизация обладает тем дополнительным преимуществом, что она позволя%ет процессу, который порождает/получает данные, выполняться одновременно с устройством, которое пишет/читает данные в/из буфера. На самом деле удобно рассматривать само устройство как процесс, который просто копирует потоки данных. Назначение буфера – в какой%то степени ослабить связь между двумя процессами, которые будем называть производителем (producer) и потребителем(consumer). Например, если потребитель в какой%то момент замедляет работу, он может нагнать производителя позднее. Без такой развязки часто нельзя обеспе%чить полноценное использование внешних устройств, но она работает, только если скорость работы производителя и потребителя примерно равны в среднем,хотя иногда и флуктуируют. Степень развязки растет с ростом размера буфера.Обратимся теперь к вопросу представле%ния буфера и для простоты предположим по%ка, что элементы данных записываются в него(deposited) и считываются из него (fetched)индивидуально, а не поблочно. В сущности,буфер представляет собой очередь, организо%ванную по принципу «первым пришел – пер%вым ушел» (first%in%first%out, или fifo). Если он объявлен как массив, то две индексные пере%менные (скажем, in и out) отмечают те пози%ции, куда должны писаться и откуда должны считываться данные. В идеале такой массив должен быть бесконечным. Однако вполне до%Рис. 1.8. Кольцевой буфер с индексами in и out 43статочно иметь конечный массив, учитывая, что прочитанные элементы больше не нужны. Занимаемое ими место может быть использовано повторно. Это приво%дит к идее кольцевого буфера.Операции записи и считывания элемента реализуются в следующем модуле,который экспортирует эти операции как процедуры, но скрывает буфер и его ин%дексные переменные – и тем самым механизм буферизации – от процесса%потреби%теля. В таком механизме еще нужна переменная n для подсчета количества элемен%тов в буфере в данный момент. Если N обозначает размер буфера, то очевидным инвариантом является условие 0≤n≤N. Поэтому операция считывания (проце%дура fetch) должна охраняться условием n>0 (буфер не пуст), а операция записи(процедура deposit) – условием n<N (буфер не полон). Невыполнение первого условия должно считаться ошибкой программирования, а нарушение второго –недостатком предложенной реализации (буфер слишком мал).MODULE Buffer; (* ! *)CONST N = 1024; (* ! *)VAR n, in, out: INTEGER;buf: ARRAY N OF CHAR;PROCEDURE deposit deposit deposit deposit deposit (x: CHAR);BEGINIF n = N THEN HALT END;INC(n); buf[in] := x; in := (in + 1) MOD NEND deposit;PROCEDURE fetch fetch fetch fetch fetch (VAR x: CHAR);BEGINIF n = 0 THEN HALT END;DEC(n); x := buf[out]; out := (out + 1) MOD NEND fetch;BEGIN n := 0; in := 0; out := 0END Buffer.Столь простая реализация буфера приемлема, только если процедуры deposit и fetch вызываются единственным агентом (действующим то как производитель, то как потребитель). Но если они вызываются независимыми процессами, работаю%щими одновременно, то такая схема оказывается слишком примитивной. Ведь тог%да попытку записи в полный буфер или попытку чтения из пустого буфера следует рассматривать как вполне законные. Просто выполнение таких действий должно быть отложено до того момента, когда снова будут выполнены соответствующиеохраны (guarding conditions). В сущности, такие задержки и представляют собой необходимый механизм синхронизации между параллельными (concurrent) про%цессами. Можно представить эти задержки следующими операторами:REPEAT UNTIL n < NREPEAT UNTIL n > 0которые нужно подставить вместо соответствующих двух условных операторов,содержащих оператор HALTФайлы или последовательности Фундаментальные структуры данных441.7.3. Буферизация обмена междупараллельными процессамиОднако представленное решение нельзя рекомендовать, даже если известно, что два процесса исполняются двумя независимыми агентами. Причина в том, что два процесса должны обращаться к одной и той же переменной n и, следовательно,к одной области оперативной памяти. Ожидающий процесс, постоянно проверяя значение n, мешает своему партнеру, так как в любой момент времени к памяти может обратиться только один процесс. Такого рода ожиданий следует избегать, и поэтому мы постулируем наличие средства, которое, в сущности, скрывает в себе механизм синхронизации. Будем называть это средство сигналом (signal) и при%мем, что оно предоставляется в служебном модуле Signals вместе с набором при%митивных операций для сигналов.Каждый сигнал s связан с охраной (условием) Ps. Если процесс нужно приостановить, пока не будет обеспечена истинность Ps (другим процессом), то он должен, прежде чем продолжить свою работу, дождаться сигнала s. Это выража%ется оператором Wait(s). С другой стороны, если процесс обеспечивает истинностьPs, то после этого он сигнализирует об этом оператором Send(s). Если для каждого оператора Send(s) обеспечивается истинность предусловия Ps, то Ps можно рас%сматривать как постусловие для Wait(s)DEFINITION Signals;TYPE Signal;PROCEDURE Wait (VAR s: Signal);PROCEDURE Send (VAR s: Signal);PROCEDURE Init (VAR s: Signal);END Signals.Теперь мы можем реализовать буфер в виде следующего модуля, который дол%жен правильно работать, когда он используется независимыми параллельными процессами:MODULE Buffer;IMPORT Signals;CONST N = 1024; (* ! *)VAR n, in, out: INTEGER;nonfull: Signals.Signal; (*n < N*)nonempty: Signals.Signal; (*n > 0*)buf: ARRAY N OF CHAR;PROCEDURE deposit deposit deposit deposit deposit (x: CHAR);BEGINIF n = N THEN Signals.Wait(nonfull) END;INC(n); buf[in] := x; in := (in + 1) MOD N;IF n = 1 THEN Signals.Send(nonempty) ENDEND deposit; 45PROCEDURE fetch fetch fetch fetch fetch (VAR x: CHAR);BEGINIF n = 0 THEN Signals.Wait(nonempty) END;DEC(n); x := buf[out]; out := (out + 1) MOD N;IF n = N–1 THEN Signals.Send(nonfull) ENDEND fetch;BEGIN n := 0; in := 0; out := 0; Signals.Init(nonfull); Signals.Init(nonempty)END Buffer.Однако нужно сделать еще одну оговорку. Данная схема разрушается, если по случайному совпадению как производитель, так и потребитель (или два произво%дителя либо два потребителя) одновременно обращаются к переменной n, чтобы изменить ее значение. Непредсказуемым образом получится либо значение n+1,либо n–1, но не n. Так что нужно защищать процессы от опасных взаимных помех.Вообще говоря, все операции, которые изменяют значения общих (shared) пере%менных, представляют собой потенциальные ловушки.Достаточным (но не всегда необходимым) условием является требование, что%бы все общие переменные объявлялись локальными в таком модуле, для проце%дур которого гарантируется, что они взаимно исключают исполнение друг друга.Такой модуль называют монитором (monitor) [1.7]. Условие взаимного исключе%ния (mutual exclusion) гарантирует, что в любой момент времени только один про%цесс сможет активно выполнять какую%либо процедуру монитора. Если другой процесс попытается вызвать некую процедуру того же монитора, его выполнение будет автоматически задержано до того момента, когда первый процесс завершит выполнение своей процедуры.Замечание. Слова «активно выполнять» означают, что процесс выполняет лю%бой оператор, кроме оператора ожидания.Наконец, вернемся к задаче, в которой производитель или потребитель (или оба) требует, чтобы данные к ним поступали блоками определенного размера.Показанный ниже модуль является вариантом предыдущего, причем предполага%ется, что размер блоков данных равен Np элементов для производителя и Nc эле%ментов для потребителя. В этом случае обычно выбирают размер буфера N так,чтобы он делился на Np и Nc. Чтобы подчеркнуть симметрию между операциями записи и считывания данных, вместо единственного счетчика n теперь исполь%зуются два счетчика, ne и nf. Они показывают соответственно число пустых и за%полненных ячеек буфера. Когда потребитель находится в состоянии ожидания, nf показывает число элементов, нужных для продолжения работы потребителя; а когда производитель находится в состоянии ожидания, то ne показывает число элементов, необходимых для продолжения работы производителя. (Поэтому ус%ловие ne + nf = N выполняется не всегда.)MODULE Buffer;IMPORT Signals;CONST Np = 16; (* *)Nc = 128; (* *)Файлы или последовательности Фундаментальные структуры данных46N = 1024; (* ! , Np Nc*)VAR ne, nf: INTEGER;in, out: INTEGER;nonfull: Signals.Signal; (*ne >= 0*)nonempty: Signals.Signal; (*nf >= 0*)buf: ARRAY N OF CHAR;PROCEDURE deposit deposit deposit deposit deposit (VAR x: ARRAY OF CHAR);BEGINne := ne – Np;IF ne < 0 THEN Signals.Wait(nonfull) END;FOR i := 0 TO Np–1 DO buf[in] := x[i]; INC(in) END;IF in = N THEN in := 0 END;nf := nf + Np;IF nf >= 0 THEN Signals.Send(nonempty) ENDEND deposit;PROCEDURE fetch fetch fetch fetch fetch (VAR x: ARRAY OF CHAR);BEGINnf := nf – Nc;IF nf < 0 THEN Signals.Wait(nonempty) END;FOR i := 0 TO Nc–1 DO x[i] := buf[out]; INC(out) END;IF out = N THEN out := 0 END;ne := ne + Nc;IF ne >= 0 THEN Signals.Send(nonfull) ENDEND fetch;BEGINne := N; nf := 0; in := 0; out := 0;Signals.Init(nonfull); Signals.Init(nonempty)END Buffer.1.7.4. Ввод и вывод текстаПод стандартным вводом и выводом мы понимаем передачу данных в ту или иную сторону между вычислительной системой и внешними агентами, например чело%веком%оператором. Достаточно типично, что ввод производится с клавиатуры,а вывод – на экран дисплея. Для таких ситуаций характерно, что информация представляется в форме, понятной человеку, и обычно состоит из последователь%ности литер. То есть речь идет о тексте. Отсюда еще одно усложнение, характерное для реальных операций ввода и вывода. Кроме передачи данных, в них выполняет%ся еще и преобразование представления. Например, числа, обычно рассматривае%мые как неделимые сущности и представленные в двоичном виде, должны быть преобразованы в удобную для чтения десятичную форму. Структуры должны представляться так, чтобы их элементы располагались определенным образом, то есть форматироваться.Независимо от того, что это за преобразование, задача заметно упрощается,если снова привлечь понятие последовательности. Решающим является наблюде% 47ние, что если набор данных можно рассматривать как последовательность литер,то преобразование последовательности может быть реализовано как последова%тельность (одинаковых) преобразований элементов:T(0, s1, ... , s n–1>) = 0), T(s1), ... , T(s n–1)>Исследуем вкратце действия, необходимые для преобразования представле%ний натуральных чисел для ввода и вывода. Математическим основанием послу%жит тот факт, что число x, представленное последовательностью десятичных цифр d = , ... , d1, d0>, имеет значение x = SSSSSi: i = 0 .. n–1: d i * 10i x = d n–1× 10n–1 + d n–2× 10n–2 + … + d1× 10 + d0x = (… (d n–1× 10 + d n–2) × 10 + … + d1) × 10 + d0Пусть теперь нужно прочесть и преобразовать последовательность d,а получившееся числовое значение присвоить переменной x. Следующий простой алгоритм останавливается при считывании первой литеры, не являющейся циф%рой (арифметическое переполнение не рассматривается):x := 0; Read(ch);(* ADruS174.% '- *)WHILE ("0" <= ch) & (ch <= "9") DOx := 10*x + (ORD(ch) – ORD("0")); Read(ch)ENDВ случае вывода преобразование усложняется тем, что разложение значения xв набор десятичных цифр дает их в обратном порядке. Младшая значащая цифра порождается первой при вычислении x MOD 10. Поэтому требуется промежуточ%ный буфер в виде очереди типа «первым пришел – последним вышел» (то есть стека). Будем представлять ее массивом d с индексом i и получим следующую программу:i := 0;(* ADruS174.-'% *)REPEAT d[i] := x MOD 10; x := x DIV 10; INC(i)UNTIL x = 0;REPEAT DEC(i); Write(CHR(d[i] + ORD("0")))UNTIL i = 0Замечание. Систематическая замена константы 10 в этих алгоритмах на поло%жительное целое B даст процедуры преобразования для представления по основа%нию B. Часто используется случай B = 16 (шестнадцатеричное представление),тогда соответствующие умножения и деления можно реализовать простыми сдвигами двоичных цифр.Очевидно, было бы неразумным детально описывать в каждой программе та%кие часто встречающиеся операции. Поэтому постулируем наличие вспомога%тельного модуля, который обеспечивает чаще всего встречающиеся, стандартные операции ввода и вывода для чисел и цепочек литер. Этот модуль используется в большинстве программ в этой книге, и мы назовем его Texts. В нем определенФайлы или последовательности Фундаментальные структуры данных48тип Text, а также типы объектов%бегунков для чтения (Reader) и записи (Writer)в переменные типа Text, а также процедуры для чтения и записи литеры, целого числа и цепочки литер.Прежде чем дать определение модуля Texts, подчеркнем существенную асим%метрию между вводом и выводом текстов. Хотя текст порождается последова%тельностью вызовов процедур вывода целых и вещественных чисел, цепочек ли%тер и т. д., ввод текста посредством вызова процедур чтения представляется сомнительной практикой. Дело здесь в том, что хотелось бы читать следующий элемент, не зная его типа, и определять его тип после чтения. Это приводит к поня%тию сканера (scanner), который после каждой попытки чтения позволяет прове%рить тип и значение прочитанного элемента. Сканер играет роль бегунка для фай%лов. Однако тогда нужно наложить ограничения на синтаксическую структуру считываемых текстов. Мы определим сканер для текстов, состоящих из последо%вательности целых и вещественных чисел, цепочек литер, имен, а также специаль%ных литер. Синтаксис этих элементов задается следующими правилами так назы%ваемой расширенной нотации Бэкуса–Наура (EBNF, Extended Backus Naur Form;чтобы точнее отразить вклад авторов нотации в ее создание, аббревиатуру еще раскрывают как Extended Backus Normal Form, то есть «расширенная нормальная нотация Бэкуса» – прим. перев.):item =integer | RealNumber | identifier | string | SpecialChar.integer =[“–”] digit {digit}.RealNumber = [“–”] digit {digit} “.” digit {digit} [(“E” | “D”)[“+” |“–” digit {digit}].identifier =letter {letter | digit}.string =‘”’ {any character except quote} ‘”’.SpecialChar =“!” | “?” | “@” | “#” | “$” | “%” | “^” | “&” | “+” | “–” |“*” | “/” | “\” | “|” | “(” | “)” | “[” | “]” | “{” | “}” |“<” | “>” | “.” | “,” | “:” | “;” | “”.Элементы разделяются пробелами и/или символами конца строк.DEFINITION Texts; (* ADruS174_Texts *)CONST Int = 1; Real = 2; Name = 3; Char = 4;TYPE Text, Writer;Reader = RECORD eot: BOOLEAN END;Scanner = RECORD class: INTEGER;i: INTEGER;x: REAL;s: ARRAY 32 OF CHAR;ch: CHAR;nextCh: CHAREND;PROCEDURE OpenReader (VAR r: Reader; t: Text; pos: INTEGER);PROCEDURE OpenWriter (VAR w: Writer; t: Text; pos: INTEGER);PROCEDURE OpenScanner (VAR s: Scanner; t: Text; pos: INTEGER);PROCEDURE Read (VAR r: Reader; VAR ch: CHAR); 49PROCEDURE ReadInt (VAR r: Reader; VAR n: INTEGER);PROCEDURE Scan (VAR s: Scanner);PROCEDURE Write (VAR w: Writer; ch: CHAR);PROCEDURE WriteLn (VAR w: Writer); (* v *)PROCEDURE WriteString (VAR w: Writer; s: ARRAY OF CHAR);PROCEDURE WriteInt (VAR w: Writer; x, n: INTEGER); (* x n . n v , , *)PROCEDURE WriteReal (VAR w: Writer; x: REAL);PROCEDURE Close (VAR w: Writer);END Texts.(Выше добавлена отсутствующая в английском оригинале процедура ReadInt, ис%пользуемая в примерах программ – прим. перев.)Мы требуем, чтобы после вызова процедуры Scan(S) для полей записи S выпол%нялось следующее:S.class = Int означает, что прочитано целое число, его значение содержится в S.i;S.class = Real означает, что прочитано вещественное число, его значение со%держится в S.x;S.class = Name означает, что прочитана цепочка литер, она содержится в S.s;S.class = Char означает, что прочитана специальная литера, она содержится в S.ch;S.nextCh содержит литеру, непосредственно следующую за прочитан%ным элементом, которая может быть пробелом.1 2 3 4 5 6 7 8 9 ... 22

Глава 3Рекурсивные алгоритмы3.1. Введение .......................... 132 3.2. Когда не следует использовать рекурсию ........... 134 3.3. Два примера рекурсивных программ ............ 137 3.4. Алгоритмы с возвратом .... 143 3.5. Задача о восьми ферзях ... 149 3.6. Задача о стабильных браках ...................................... 154 3.7. Задача оптимального выбора ..................................... 160Упражнения ............................. 164Литература .............................. 166 Рекурсивные алгоритмы1323.1. ВведениеОбъект называется рекурсивным, если его части определены через него самого.Рекурсия встречается не только в математике, но и в обычной жизни. Кто не видел рекламной картинки, которая содержит саму себя?Рис. 3.1. Рекурсивное изображениеРекурсия особенно хорошо являет свою мощь в математических определени%ях. Знакомые примеры – натуральные числа, древесные структуры и некоторые функции:1. Натуральные числа:(a) 0 является натуральным числом.(b) Число, следующее за натуральным, является натуральным.2. Древесные структуры:(a)∅ является деревом (и называется «пустым деревом»).(b) Если t1 и t2 – деревья, то конструкция, состоящая из узла с двумя по%томками t1 и t2, тоже является деревом (двоичным или бинарным).3. Факториальная функция f(n):f(0) = 1f(n) = n × f(n – 1) для n > 0Очевидно, мощь рекурсии заключается в возможности определить бесконеч%ное множество объектов с помощью конечного утверждения. Подобным же обра%зом бесконечное число расчетов может быть описано конечной рекурсивной программой, даже если программа не содержит явных циклов. Однако рекур%сивные алгоритмы уместны прежде всего тогда, когда решаемая проблема, вычис%ляемая функция или обрабатываемая структура данных заданы рекурсивным образом. В общем случае рекурсивная программа P может быть выражена как композиция PPPPP последовательности инструкций S (не содержащей P) и самой P:P ≡ PPPPP[S, P] 133Необходимое и достаточное средство для рекурсивной формулировки про%грамм – процедура, так как она позволяет дать набору инструкций имя, с помо%щью которого эти инструкции могут быть вызваны. Если процедура P содержит явную ссылку на саму себя, то говорят, что она явно рекурсивна; если P содержит ссылку на другую процедуру Q, которая содержит (прямую или косвенную) ссыл%ку на P, то говорят, что P косвенно рекурсивна. Последнее означает, что наличие рекурсии может быть не очевидно из текста программы.С процедурой обычно ассоциируется набор локальных переменных, констант,типов и процедур, которые определены как локальные в данной процедуре и не существуют и не имеют смысла вне ее. При каждой рекурсивной активации про%цедуры создается новый набор локальных переменных. Хотя у них те же имена,что и у переменных в предыдущей активации процедуры, их значения другие,и любая возможность конфликта устраняется правилами видимости идентифика%торов: идентификаторы всегда ссылаются на набор переменных, созданный по%следним. Такое же правило действует для параметров процедуры, которые по оп%ределению связаны с ней.Как и в случае операторов цикла, рекурсивные процедуры открывают возмож%ность бесконечных вычислений. Следовательно, необходимо рассматривать про%блему остановки. Очевидное фундаментальное требование состоит в том, чтобы рекурсивные вызовы процедуры P имели место лишь при выполнении условия B,которое в какой%то момент перестает выполняться. Поэтому схема рекурсивных алгоритмов точнее выражается одной из следующих форм:P ≡ IF B THEN PPPPP[S, P] ENDP ≡ PPPPP[S, IF B THEN P END]Основной метод доказательства остановки повторяющихся процессов состоит из следующих шагов:1) определяется целочисленная функция f(x) (где x – набор переменных) –такая, что из f(x) < 0 следует условие остановки (фигурирующее в операто%ре while или repeat);2) доказывается, что f(x) уменьшается на каждом шаге процесса.Аналогично доказывают прекращение рекурсии: достаточно показать, что каж%дая активация P уменьшает некоторую целочисленную функцию f(x) и что f(x) < 0влечет B. Особенно ясный способ гарантировать остановку состоит в том, чтобы ассоциировать передаваемый по значению параметр (назовем его n) с процедуройP, и рекурсивно вызывать P с n–1 в качестве значения этого параметра. Тогда, под%ставляя n > 0 вместо B, получаем гарантию прекращения. Это можно выразить следующими схемами:P(n) ≡ IF n > 0 THEN PPPPP[S, P(n–1)] ENDP(n) ≡ PPPPP[S, IF n > 0 THEN P(n–1) END]В практических приложениях нужно доказывать не только конечность глуби%ны рекурсии, но и что эта глубина достаточно мала. Причина в том, что при каж%дой рекурсивной активации процедуры P используется некоторый объем опера%Введение Рекурсивные алгоритмы134тивной памяти для размещения ее локальных переменных. Кроме того, нужно за%помнить текущее состояние вычислительного процесса, чтобы после окончания новой активации P могла быть возобновлена предыдущая. Мы уже встречали та%кую ситуацию в процедуре QuickSort в главе 2. Там было обнаружено, что при наивном построении программы из операции, которая разбивает n элементов на две части, и двух рекурсивных вызовов сортировки для двух частей глубина ре%курсии может в худшем случае приближаться к n. Внимательный анализ позво%лил ограничить глубину величиной порядка l og(n). Разница между n и log(n) дос%таточно существенна, чтобы превратить ситуацию, в которой рекурсия в высшей степени неуместна, в такую, где рекурсия становится вполне практичной.3.2. Когда не следует использоватьрекурсиюРекурсивные алгоритмы особенно хорошо подходят для тех ситуаций, когда ре%шаемая задача или обрабатываемые данные определены рекурсивно. Однако на%личие рекурсивного определения еще не означает, что рекурсивный алгоритм даст наилучшее решение. Именно попытки объяснять понятие рекурсивного ал%горитма с помощью неподходящих примеров стали главной причиной широко распространенного предубеждения против использования рекурсии в програм%мировании, а также мнения о неэффективности рекурсии.Программы, в которых следует избегать использования алгоритмической рекурсии, характеризуются определенной структурой. Для них характерно нали%чие единственного вызова P в конце (или в начале) композиции (так называемаяконцевая рекурсия):P ≡ IF B THEN S; P ENDP ≡ S; IF B THEN P ENDТакие схемы естественно возникают в тех случаях, когда вычисляемые значе%ния определяются простыми рекуррентными соотношениями. Возьмем извест%ный пример факториала fi = i!:i= 0, 1, 2, 3, 4, 5, ...f i= 1, 1, 2, 6, 24, 120, ...Первое значение определено явно: f0 = 1, а последующие – рекурсивно через предшествующие:f i+1 = (i+1) * f iЭто рекуррентное соотношение наводит на мысль использовать рекурсивный алгоритм для вычисления n%го факториала. Если ввести две переменные I и F для обозначения значений i и fi на i%м уровне рекурсии, то переход к следующим чле%нам пары последовательностей для i и fi требует такого вычисления:I := I + 1; F := I * F 135Подставляя эту пару инструкций вместо S, получаем рекурсивную программуP ≡ IF I < n THEN I := I + 1; F := I * F; P ENDI := 0; F := 1; PВ принятой нами нотации первая строка выражается следующим образом:PROCEDURE P;BEGINIF I < n THEN I := I + 1; F := I*F; P ENDEND PЧаще используется эквивалентная форма, данная ниже. P заменяется процеду%рой%функцией F, то есть процедурой, с которой явно ассоциируется вычисляемое значение и которая может поэтому быть использована как непосредственная со%ставная часть выражений. Тогда переменная F становится лишней, а роль I берет на себя явно задаваемый параметр процедуры:PROCEDURE F(I: INTEGER): INTEGER;BEGINIF I > 0 THEN RETURN I * F(I – 1) ELSE RETURN 1 ENDEND FЯсно, что в этом примере рекурсия может быть довольно легко заменена итера%цией. Это выражается следующей программой:I := 0; F := 1;WHILE I < n DO I := I + 1; F := I*F ENDВ общем случае программы, построенные по обсуждаемым частным рекурсив%ным схемам, следует переписывать в соответствии со следующим образцом:P ≡ [x := x0; WHILE B DO S END]Существуют и более сложные рекурсивные композиционные схемы, которые могут и должны приводиться к итеративному виду. Пример – вычисление чиселФибоначчи, определенных рекуррентным соотношением fib n+1 = fib n + fib n–1для n > 0и соотношениями fib1 = 1, fib0 = 0. Непосредственный наивный перевод на язык программирования дает следующую рекурсивную программу:PROCEDURE Fib (n: INTEGER): INTEGER;VAR res: INTEGER;BEGINIF n = 0 THEN res := 0ELSIF n = 1 THEN res := 1ELSE res := Fib(n–1) + Fib(n–2)END;RETURN resEND FibКогда не следует использовать рекурсию Рекурсивные алгоритмы136Вычисление fib n с помощью вызова Fib(n) вызывает рекурсивные активации этой процедуры%функции. Сколько происходит таких активаций? Очевидно, каж%дый вызов с n > 1 приводит к двум дальнейшим вызовам, то есть полное число вы%зовов растет экспоненциально (см. рис. 3.2). Такая программа явно непрактична.Рис. 3.2. Пятнадцать активаций при вызове Fib(5)К счастью, числа Фибоначчи можно вычислять по итерационной схеме без многократного вычисления одних и тех же значений благодаря использованию вспомогательных переменных – таких, что x = fib i и y = fib i–1i := 1; x := 1; y := 0;WHILE i < n DO z := x; x := x + y; y := z; i := i + 1 ENDОтметим, что три присваивания переменным x, y, z можно заменить всего лишь двумя присваиваниями без привлечения вспомогательной переменной z: x := x + y;y := x – yОтсюда мораль: следует избегать рекурсии, когда есть очевидное решение,использующее итерацию. Но это не значит, что от рекурсии нужно избавляться любой ценой. Как будет показано в последующих разделах и главах, существует много хороших применений рекурсии. Тот факт, что имеются реализации рекур%сивных процедур на принципиально нерекурсивных машинах, доказывает, что любая рекурсивная программа действительно может быть преобразована в чисто итерационную. Но тогда требуется явно управлять стеком рекурсии, и это часто затемняет сущность программы до такой степени, что понять ее становится весь%ма трудно. Отсюда вывод: алгоритмы, которые по своей природе являются рекур%сивными, а не итерационными, должны программироваться в виде рекурсивных процедур. Чтобы оценить это обстоятельство, полезно сравнить два варианта ал%горитма быстрой сортировки в разделе 2.3.3: рекурсивный (QuickSort) и нерекур%сивный (NonRecursiveQuickSort).Оставшаяся часть главы посвящена разработке некоторых рекурсивных про%грамм в ситуациях, когда применение рекурсии оправдано. Кроме того, в главе 4рекурсия широко используется в тех случаях, когда соответствующие структуры данных делают выбор рекурсивных решений очевидным и естественным. 1373.3. Два примера рекурсивных программСимпатичный узор на рис. 3.4 представляет собой суперпозицию пяти кривых.Эти кривые являют регулярность структуры, так что их, вероятно, можно изобра%зить на дисплее или графопостроителе под управлением компьютера. Наша цель –выявить рекурсивную схему, с помощью которой можно написать программу для рисования этих кривых. Можно видеть, что три из пяти кривых имеют вид, пока%занный на рис. 3.3; обозначим их как H1, H2 и H3. Кривая Hi называется гильбертовой кривой порядка i в честь математика Гильберта (D. Hilbert, 1891).Рис. 3.3. Гильбертовы кривые порядков 1, 2 и 3Каждая кривая Hi состоит из четырех копий кривой Hi–1 половинного размера,поэтому мы выразим процедуру рисования Hi в виде композиции четырех вызовов для рисования Hi–1 половинного размера и с соответствующими поворотами. Для целей иллюстрации обозначим четыре по%разному повернутых варианта базовой кривой как A, B, C и D, а шаги рисования соединительных линий обозначим стрел%ками, направленными соответственно. Тогда возникает следующая рекурсивная схема (ср. рис. 3.3):A:D←A↓A→BB:C↑B→B↓AC:B→C↑C←DD:A↓D←D↑CПредположим, что для рисования отрезков прямых в нашем распоряжении есть процедура line, которая передвигает чертящее перо в заданном направлении на заданное расстояние. Для удобства примем, что направление указывается целочисленным параметром i, так что в градусах оно равно 45 × i. Если длину от%резков, из которых составляется кривая, обозначить как u, то процедуру, соответ%ствующую схеме A, можно сразу выразить через рекурсивные вызовы аналогич%ных процедур B и D и ее самой:PROCEDURE A (i: INTEGER);BEGINIF i > 0 THEND(i–1); line(4, u);A(i–1); line(6, u);Два примера рекурсивных программ Рекурсивные алгоритмы138A(i–1); line(0, u);B(i–1)ENDEND AЭта процедура вызывается в главной программе один раз для каждой гильбер%товой кривой, добавляемой в рисунок. Главная программа определяет начальную точку кривой, то есть начальные координаты пера, обозначенные как x0 и y0,а также длину базового отрезка u. Квадрат, в котором рисуются кривые, помеща%ется в середине страницы с заданными шириной и высотой. Эти параметры, так же как и рисующая процедура line, берутся из модуля Draw. Отметим, что этот модуль помнит текущее положение пера.DEFINITION Draw;(* ADruS33_Draw *)CONST width = 1024; height = 800;PROCEDURE Clear; (* *)PROCEDURE SetPen(x, y: INTEGER); (* x, y*)PROCEDURE line(dir, len: INTEGER);(* len dir*45 # ;(* # *)END Draw.Процедура Hilbert рисует гильбертовы кривые H1 ... Hn. Она рекурсивно использует четыре процедуры A, B, C и D:VAR u: INTEGER;(* ADruS33_Hilbert *)PROCEDURE A (i: INTEGER);BEGINIF i > 0 THEND(i–1); Draw.line(4, u); A(i–1); Draw.line(6, u); A(i–1); Draw.line(0, u); B(i–1)ENDEND A;PROCEDURE B (i: INTEGER);BEGINIF i > 0 THENC(i–1); Draw.line(2, u); B(i–1); Draw.line(0, u); B(i–1); Draw.line(6, u); A(i–1)ENDEND B;PROCEDURE C (i: INTEGER);BEGINIF i > 0 THENB(i–1); Draw.line(0, u); C(i–1); Draw.line(2, u); C(i–1); Draw.line(4, u); D(i–1)ENDEND C;PROCEDURE D (i: INTEGER);BEGINIF i > 0 THENA(i–1); Draw.line(6, u); D(i–1); Draw.line(4, u); D(i–1); Draw.line(2, u); C(i–1)ENDEND D; 139PROCEDURE Hilbert (n: INTEGER);CONST SquareSize = 512;VAR i, x0, y0: INTEGER;BEGINDraw.Clear;x0 := Draw.width DIV 2; y0 := Draw.height DIV 2;u := SquareSize; i := 0;REPEATINC(i); u := u DIV 2;x0 := x0 + (u DIV 2); y0 := y0 + (u DIV 2);Draw.Set(x0, y0);A(i)UNTIL i = nEND Hilbert.Похожий, но чуть более сложный и эстетически изощренный пример показан на рис. 3.6. Этот узор тоже получается наложением нескольких кривых, две из ко%торых показаны на рис. 3.5. Si называется кривой Серпиньского порядка i. Какова ее рекурсивная структура? Есть соблазн в качестве основного строительного бло%ка взять фигуру S1, возможно, без одного ребра. Но так решение не получится.Главное отличие кривых Серпиньского от кривых Гильберта – в том, что первые замкнуты (и не имеют самопересечений). Это означает, что базовой рекурсивной схемой должна быть разомкнутая кривая и что четыре части соединяются связка%ми, не принадлежащими самому рекурсивному узору. В самом деле, эти связки состоят из четырех отрезков прямых в четырех самых внешних углах, показанных жирными линиями на рис. 3.5. Их можно считать принадлежащими непустой на%чальной кривой S0, представляющей собой квадрат, стоящий на одном из углов.Теперь легко сформулировать рекурсивную схему. Четыре узора, из которых со%ставляется кривая, снова обозначим как A, B, C и D, а линии%связки будем рисовать явно. Заметим, что четыре рекурсивных узора действительно идентичны, отлича%ясь поворотами на 90 градусов.Вот базовая схема кривых Серпиньского:S: A B C D А вот схема рекурсий (горизонтальные и вертикальные стрелки обозначают линии двойной длины):A: A B → D AB: B C ↓ A BC: C D ← B CD: D A ↑ C DЕсли использовать те же примитивы рисования, что и в примере с кривымиГильберта, то эта схема рекурсии легко превращается в рекурсивный алгоритм(с прямой и косвенной рекурсиями).Два примера рекурсивных программ Рекурсивные алгоритмы140Рис. 3.4. Гильбертовы кривые H1 … H5Рис. 3.5. Кривые Серпиньского S1 и S2 141PROCEDURE A (k: INTEGER);BEGINIF k > 0 THENA(k–1); Draw.line(7, h); B(k–1); Draw.line(0, 2*h);D(k–1); Draw.line(1, h); A(k–1)ENDEND AЭта процедура реализует первую строку схемы рекурсий. Процедуры для узо%ров B, C и D получаются аналогично. Главная программа составляется по базовой схеме. Ее назначение – установить начальное положение пера и определить длину единичной линии h в соответствии с размером рисунка. Результат выполнения этой программы для n = 4 показан на рис. 3.6.VAR h: INTEGER;(* ADruS33_Sierpinski *)PROCEDURE A (k: INTEGER);BEGINIF k > 0 THENA(k–1); Draw.line(7, h); B(k–1); Draw.line(0, 2*h);D(k–1); Draw.line(1, h); A(k–1)ENDEND A;PROCEDURE B (k: INTEGER);BEGINIF k > 0 THENB(k–1); Draw.line(5, h); C(k–1); Draw.line(6, 2*h);A(k–1); Draw.line(7, h); B(k–1)ENDEND B;PROCEDURE C (k: INTEGER);BEGINIF k > 0 THENC(k–1); Draw.line(3, h); D(k–1); Draw.line(4, 2*h);B(k–1); Draw.line(5, h); C(k–1)ENDEND C;PROCEDURE D (k: INTEGER);BEGINIF k > 0 THEND(k–1); Draw.line(1, h); A(k–1); Draw.line(2, 2*h);C(k–1); Draw.line(3, h); D(k–1)ENDEND D;PROCEDURE Sierpinski* (n: INTEGER);CONST SquareSize = 512;VAR i, x0, y0: INTEGER;BEGINДва примера рекурсивных программ Рекурсивные алгоритмы142Draw.Clear;h := SquareSize DIV 4;x0 := Draw.width DIV 2; y0 := Draw.height DIV 2 + h;i := 0;REPEATINC(i); x0 := x0-h;h := h DIV 2; y0 := y0+h; Draw.Set(x0, y0);A(i); Draw.line(7,h); B(i); Draw.line(5,h);C(i); Draw.line(3,h); D(i); Draw.line(1,h)UNTIL i = nEND Sierpinski.Элегантность приведенных примеров убеждает в полезности рекурсии. Пра%вильность получившихся программ легко установить по их структуре и по схемам композиции. Более того, использование явного (и уменьшающегося) параметра уровня гарантирует остановку, так как глубина рекурсии не может превысить nНапротив, эквивалентные программы, не использующие рекурсию явно, оказыва%ются весьма громоздкими, и понять их нелегко. Читатель легко убедится в этом,если попытается разобраться в программах, приведенных в [3.3].Рис. 3.6. Кривые Серпиньского S1 … S4 1431 ... 8 9 10 11 12 13 14 15 ... 22

3.4. Алгоритмы с возвратомВесьма интригующее направление в программировании – поиск общих методов решения сложных зачач. Цель здесь в том, чтобы научиться искать решения конк%ретных задач, не следуя какому%то фиксированному правилу вычислений, а мето%дом проб и ошибок. Общая схема заключается в том, чтобы свести процесс проб и ошибок к нескольким частным задачам. Эти задачи часто допускают очень естест%венное рекурсивное описание и сводятся к исследованию конечного числа подза%дач. Процесс в целом можно представлять себе как поиск%исследование, в ко%тором постепенно строится и просматривается (с обрезанием каких%то ветвей)некое дерево подзадач. Во многих задачах такое дерево поиска растет очень быст%ро, часто экспоненциально, как функция некоторого параметра. Трудоемкость поиска растет соответственно. Часто только использование эвристик позволяет обрезать дерево поиска до такой степени, чтобы сделать вычисление сколь%ни%будь реалистичным.Обсуждение общих эвристических правил не входит в наши цели. Мы сосредо%точимся в этой главе на общем принципе разбиения задач на подзадачи с приме%нением рекурсии. Начнем с демонстрации соответствующей техники в простом примере, а именно в хорошо известной задаче о путешествии шахматного коня.Пусть дана доска n × n с n2полями. Конь, который передвигается по шахмат%ным правилам, ставится на доске в поле , y0>. Задача – обойти всю доску, если это возможно, то есть вычислить такой маршрут из n2–1 ходов, чтобы в каждое поле доски конь попал ровно один раз.Очевидный способ упростить задачу обхода n2 полей – рассмотреть подзадачу,которая состоит в том, чтобы либо выполнить какой%либо очередной ход, либо обнаружить, что дальнейшие ходы невозможны. Эту идею можно выразить так:PROCEDURE TryNextMove; (* *)BEGINIF THEN ;WHILE ( v ) & ( v # )DO ENDENDEND TryNextMove;Предикат v # удобно выразить в виде про%цедуры%функции с логическим значением, в которой – раз уж мы собираемся за%писывать порождаемую последовательность ходов – подходящее место как для записи очередного хода, так и для ее отмены в случае неудачи, так как именно в этой процедуре выясняется успех завершения обхода.PROCEDURE CanBeDone ( ): BOOLEAN;BEGIN ;Алгоритмы с возвратом Рекурсивные алгоритмы144TryNextMove;IF THEN END;RETURN END CanBeDoneЗдесь уже видна схема рекурсии.Чтобы уточнить этот алгоритм, необходимо принять некоторые решения о пред%ставлении данных. Во%первых, мы хотели бы записать полную историю ходов.Поэтому каждый ход будем характеризовать тремя числами: его номером i и дву%мя координатами . Эту связь можно было бы выразить, введя специальный тип записей с тремя полями, но данная задача слишком проста, чтобы оправдать соответствующие накладные расходы; будет достаточно отслеживать соответствую%щие тройки переменных.Это сразу позволяет выбрать подходящие параметры для процедуры TryNextMoveОни должны позволять определить начальные условия для очередного хода, а так%же сообщать о его успешности. Для достижения первой цели достаточно указы%вать параметры предыдущего хода, то есть координаты поля x, y и его номер i. Для достижения второй цели нужен булевский параметр%результат со значением - v v . Получается следующая сигнатура:PROCEDURE TryNextMove (x, y, i: INTEGER; VAR done: BOOLEAN)Далее, очередной допустимый ход должен иметь номер i+1. Для его координат введем пару переменных u, v. Это позволяет выразить предикат - v # , используемый в цикле линейного поиска, в виде вызова процедуры%функции со следующей сигнатурой:PROCEDURE CanBeDone (u, v, i1: INTEGER): BOOLEANУсловие может быть выражено как i < n2. А для условия v введем логическую переменную eos. Тогда логика алгоритма проясняется следующим образом:PROCEDURE TryNextMove (x, y, i: INTEGER; VAR done: BOOLEAN);VAR eos: BOOLEAN; u, v: INTEGER;BEGINIF i < n2 THEN ;WHILE eos & CanBeDone(u, v, i+1) DO END;done := eosELSEdone := TRUEENDEND TryNextMove; 145PROCEDURE CanBeDone (u, v, i1: INTEGER): BOOLEAN;VAR done: BOOLEAN;BEGIN ;TryNextMove(u, v, i1, done);IF done THEN END;RETURN doneEND CanBeDoneЗаметим, что процедура TryNextMove сформулирована так, чтобы корректно об%рабатывать и вырожденный случай, когда после хода x, y, i выясняется, что доска заполнена. Это сделано по той же, в сущности, причине, по которой арифметиче%ские операции определяются так, чтобы корректно обрабатывать нулевые значения операндов: удобство и надежность. Если (как нередко делают из соображений оп%тимизации) вынести такую проверку из процедуры, то каждый вызов процедуры придется сопровождать такой охраной – или доказывать, что охрана в конкретной точке программы не нужна. К подобным оптимизациям следует прибегать, только если их необходимость доказана – после построения корректного алгоритма.Следующее очевидное решение – представить доску матрицей, скажем h:VAR h: ARRAY n, n OF INTEGERРешение сопоставить каждому полю доски целое, а не булевское значение,которое бы просто отмечало, занято поле или нет, объясняется желанием сохра%нить полную историю ходов простейшим способом:h[x, y] = 0:поле еще не пройдено h[x, y] = i:поле пройдено на i%м ходу (0 < i ≤ n2)Очевидно, запись допустимого хода теперь выражается присваиванием hxy := i,а отмена – hxy := 0, чем завершается построение процедуры CanBeDoneОсталось организовать перебор допустимых ходов u, v из заданной позиции x, y в цикле поиска процедуры TryNextMove. На бесконечной во все стороны доске для каждой позиции x, y есть несколько ходов%кандидатов u, v, которые пока конкретизировать нет нужды (см., однако, рис. 3.7). Предикат для выбора допустимых ходов среди ходов%кандидатов выражается как логическая конъюнк%ция условий, описывающих, что новое поле лежит в пределах доски, то есть0 ≤ u < n и 0 ≤ v < n, и что конь по нему еще не проходил, то есть huv = 0. Деталь,которую нельзя упустить: переменная huv существует, только если оба значения u и v лежат в диапазоне 0 ... n–1. Поэтому важно, чтобы член huv = 0 стоял после%дним. В итоге выбор следующего допустимого хода тогда представляется уже зна%комой схемой линейного поиска (только выраженной через цикл repeat вместо while,что в данном случае возможно и удобно). При этом для сообщения об исчер%пании множества ходов%кандидатов можно использовать переменную eos. Офор%мим эту операцию в виде процедуры Next, явно указав в качестве параметров зна%чимые переменные:Алгоритмы с возвратом Рекурсивные алгоритмы146PROCEDURE Next (VAR eos: BOOLEAN; VAR u, v: INTEGER);BEGIN(*eos*)REPEAT - u, vUNTIL ( v ) OR((0 <= u) & (u < n) & (0 <= v) & (v < n) & (h[u, v] = 0));eos := v END Next;Инициализация перебора ходов%кандидатов выполняется внутри аналогич%ной процедуры First, порождающей первый допустимый ход; см. детали в оконча%тельной программе, приводимой ниже.Остался только один шаг уточнения, и мы получим программу, полностью выраженную в нашей основной нотации. Заметим, что до сих пор программа раз%рабатывалась совершенно независимо от правил, описывающих допустимые хо%ды коня. Мы сознательно откладывали рассмотрение таких деталей задачи. Но теперь пора их учесть.Для начальной пары координат x,y на бесконечной свободной доске есть восемь позиций%кандидатов u,v,куда может прыгнуть конь. На рис. 3.7 они пронумеро%ваны от 1 до 8.Простой способ получить u,v из x,y состоит в при%бавлении разностей координат, хранящихся либо в мас%сиве пар разностей, либо в двух массивах одиночных разностей. Пусть эти массивы обозначены как dx и dy иправильно инициализированы:dx = (2, 1, –1, –2, –2, –1, 1, 2)dy = (1, 2, 2, 1, –1, –2, –2, –1)Тогда можно использовать индекс k для нумерации очередного хода%кандидата. Детали показаны в программе, приводимой ниже.Мы предполагаем наличие глобальной матрицы h размера n × n, представляю%щей результат, константы n (и nsqr = n2), а также массивов dx и dy, представля%ющих возможные ходы коня без ограничений (см. рис. 3.7). Рекурсивная проце%дура стартует с параметрами x0, y0 – координатами того поля, с которого должно начаться путешествие коня. В это поле должен быть записан номер 1; все прочие поля следует пометить как свободные.VAR h: ARRAY n, n OF INTEGER;(* ADruS34_KnightsTour *)dx, dy: ARRAY 8 OF INTEGER;PROCEDURE CanBeDone (u, v, i: INTEGER): BOOLEAN;VAR done: BOOLEAN;BEGINh[u, v] := i;TryNextMove(u, v, i, done);IF done THEN h[u, v] := 0 END;Рис. 3.7. Восемь возможных ходов коня 147RETURN doneEND CanBeDone;PROCEDURE TryNextMove (x, y, i: INTEGER; VAR done: BOOLEAN);VAR eos: BOOLEAN; u, v: INTEGER; k: INTEGER;PROCEDURE Next (VAR eos: BOOLEAN; VAR u, v: INTEGER);BEGINREPEATINC(k);IF k < 8 THEN u := x + dx[k]; v := y + dy[k] END;UNTIL (k = 8) OR ((0 <= u) & (u < n) & (0 <= v) & (v < n) & (h[u, v] = 0));eos := (k = 8)END Next;PROCEDURE First (VAR eos: BOOLEAN; VAR u, v: INTEGER);BEGINeos := FALSE; k := –1; Next(eos, u, v)END First;BEGINIF i < nsqr THENFirst(eos, u, v);WHILE eos & CanBeDone(u, v, i+1) DONext(eos, u, v)END;done := eosELSEdone := TRUEEND;END TryNextMove;PROCEDURE Clear;VAR i, j: INTEGER;BEGINFOR i := 0 TO n–1 DOFOR j := 0 TO n–1 DO h[i,j] := 0 ENDENDEND Clear;PROCEDURE KnightsTour (x0, y0: INTEGER; VAR done: BOOLEAN);BEGINClear; h[x0,y0] := 1; TryNextMove(x0, y0, 1, done);END KnightsTour;Таблица 3.1 показывает решения, полученные для начальных позиций <2,2>,<1,3> для n = 5 и <0,0> для n = 6Какие общие уроки можно извлечь из этого примера? Видна ли в нем какая%либо схема, типичная для алгоритмов, решающих подобные задачи? Чему он нас учит? Характерной чертой здесь является то, что каждый шаг, выполняемый в попытке приблизиться к полному решению, запоминается таким образом, чтобыАлгоритмы с возвратом Рекурсивные алгоритмы148от него можно было позднее отказаться, если выяснится, что он не может привес%ти к полному решению и заводит в тупик. Такое действие называется возвратом(backtracking). Общая схема, приводимая ниже, абстрагирована из процедурыTryNextMove в предположении, что число потенциальных кандидатов на каждом шаге конечно:PROCEDURE Try; (* v *)BEGINIF v THEN v # ;WHILE (v # v ) & CanBeDone( v #) DO v #ENDENDEND Try;PROCEDURE CanBeDone ( v # ): BOOLEAN;(* v , # v #*)BEGIN v #;Try;IF v THEN v # END;RETURN v END CanBeDoneРазумеется, в реальных программах эта схема может варьироваться. В частно%сти, в зависимости от специфики задачи может варьироваться способ передачи информации в процедуру Try при каждом очередном ее вызове. Ведь в обсуж%даемой схеме предполагается, что эта процедура имеет доступ к глобальным пе%ременным, в которых записывается выстраиваемое решение и, следовательно,содержится, в принципе, полная информация о текущем шаге построения. Напри%Таблица 3.1.Таблица 3.1.Таблица 3.1.Таблица 3.1.Таблица 3.1. Три возможных обхода конем23 49 14 25 10 15 24 18 522 318 13 16 11 20 72 21 617 12 19 116 726 11 14 34 25 12 15 627 17 233 813 10 32 35 24 21 28 523 18 330 920 36 31 22 19 429 23 10 15 425 16 524 914 11 22 118 36 17 20 13 821 12 72 19 149мер, в рассмотренной задаче о путешествии коня в процедуре TryNextMove нужно знать последнюю позицию коня на доске. Ее можно было бы найти поиском в мас%сиве h. Однако эта информация явно наличествует в момент вызова процедуры,и гораздо проще ее туда передать через параметры. В дальнейших примерах мы увидим вариации на эту тему.Отметим, что условие поиска в цикле оформлено в виде процедуры%функцииCanBeDone для максимального прояснения логики алгоритма без потери обозри%мости программы. Разумеется, можно оптимизировать программу в других отно%шениях, проведя эквивалентные преобразования. Например, можно избавиться от двух процедур First и Next, слив два легко верифицируемых цикла в один. Этот единственный цикл будет, вообще говоря, более сложным, однако в том случае,когда требуется сгенерировать все решения, может получиться довольно прозрач%ный результат (см. последнюю программу в следующем разделе).Остаток этой главы посвящен разбору еще трех примеров, в которых уместна рекурсия. В них демонстрируются разные реализации описанной общей схемы.3.5. Задача о восьми ферзяхЗадача о восьми ферзях – хорошо известный пример использования метода проб и ошибок и алгоритмов с возвратом. Ее исследовал Гаусс в 1850 г., но он не нашел полного решения. Это и неудивительно, ведь для таких задач характерно отсут%ствие аналитических решений. Вместо этого приходится полагаться на огромный труд, терпение и точность. Поэтому подобные алгоритмы стали применяться почти исключительно благодаря появлению автоматического компьютера, который обла%дает этими качествами в гораздо большей степени, чем люди и даже чем гении.В этой задаче (см. также [3.4]) требуется расположить на шахматной доске во%семь ферзей так, чтобы ни один из них не угрожал другому. Будем следовать об%щей схеме, представленной в конце раздела 3.4. По правилам шахмат ферзь угро%жает всем фигурам, находящимся на одной с ним вертикали, горизонтали или диагонали доски, поэтому мы заключаем, что на каждой вертикали может нахо%диться один и только один ферзь. Поэтому можно пронумеровать ферзей по зани%маемым ими вертикалям, так что i%й ферзь стоит на i%й вертикали. Очередным шагом построения в общей рекурсивной схеме будем считать размещение очеред%ного ферзя в порядке их номеров. В отличие от задачи о путешествии коня, здесь нужно будет знать положение всех уже размещенных ферзей. Поэтому в качестве параметра в процедуру Try достаточно передавать номер размещаемого на этом шаге ферзя i, который, таким образом, является номером столбца. Тогда опреде%лить положение ферзя – значит выбрать одно из восьми значений номера ряда jPROCEDURE Try (i: INTEGER);BEGINIF i < 8 THEN j ;Задача о восьми ферзях Рекурсивные алгоритмы150WHILE (v ) & CanBeDone(i, j) DO jENDENDEND Try;PROCEDURE CanBeDone (i, j: INTEGER): BOOLEAN;(* v , i-# ! j- *)BEGIN ! ;Try(i+1);IF v THEN ! END;RETURN v END CanBeDoneЧтобы двигаться дальше, нужно решить, как представлять данные. Напраши%вается представление доски с помощью квадратной матрицы, но небольшое раз%мышление показывает, что тогда действия по проверке безопасности позиций по%лучатся довольно громоздкими. Это крайне нежелательно, так как это самая часто выполняемая операция. Поэтому мы должны представить данные так, чтобы эта проверка была как можно проще. Лучший путь к этой цели – как можно более непосредственно представить именно ту информацию, которая конкретно нужна и чаще всего используется. В нашем случае это не положение ферзей, а информа%ция о том, был ли уже поставлен ферзь на каждый из рядов и на каждую из диаго%налей. (Мы уже знаем, что в каждом столбце k для 0≤ k < i стоит в точности один ферзь.) Это приводит к такому выбору переменных:VAR x: ARRAY 8 OF INTEGER;a: ARRAY 8 OF BOOLEAN;b, c: ARRAY 15 OF BOOLEANгде xi означает положение ферзя в i%м столбце;a j означает, что «в j%м ряду ферзя еще нет»;b k означает, что «на k%й /- диагонали нет ферзя»;c k означает, что «на k%й \- диагонали нет ферзя».Заметим, что все поля на /%диагонали имеют одинаковую сумму своих коорди%нат i и j, а на \%диагонали – одинаковую разность координат i-j. Соответствующая нумерация диагоналей использована в приведенной ниже программе QueensС такими определениями операция ! раскрывается следующим образом:x[i] := j; a[j] := FALSE; b[i+j] := FALSE; c[i-j+7] := FALSEоперация ! уточняется в a[j] := TRUE; b[i+j] := TRUE; c[i-j+7] := TRUE 151Поле безопасно, если оно находится в строке и на диагоналях, которые еще свободны. Поэтому ему соответствует логическое выражение a[j] & b[i+j] & c[i-j+7]Это позволяет построить процедуры перечисления безопасных значений j для i%го ферзя по аналогии с предыдущим примером.Этим, в сущности, завершается разработка алгоритма, представленного цели%ком ниже в виде программы Queens. Она вычисляет решение x = (0, 4, 7, 5, 2, 6,1, 3), показанное на рис. 3.8.Рис. 3.8. Одно из решений задачи о восьми ферзяхPROCEDURE Try (i: INTEGER; VAR done: BOOLEAN);(* ADruS35_Queens *)VAR eos: BOOLEAN; j: INTEGER;PROCEDURE Next;BEGINREPEAT INC(j);UNTIL (j = 8) OR (a[j] & b[i+j] & c[i-j+7]);eos := (j = 8)END Next;PROCEDURE First;BEGINeos := FALSE; j := –1; NextEND First;BEGINIF i < 8 THENFirst;WHILE eos & CanBeDone(i, j) DONextЗадача о восьми ферзях Рекурсивные алгоритмы152END;done := eosELSEdone := TRUEENDEND Try;PROCEDURE CanBeDone (i, j: INTEGER): BOOLEAN;(* v , i-# ! j- *)VAR done: BOOLEAN;BEGINx[i] := j; a[j] := FALSE; b[i+j] := FALSE; c[i-j+7] := FALSE;Try(i+1, done);IF done THENx[i] := –1; a[j] := TRUE; b[i+j] := TRUE; c[i-j+7] := TRUEEND;RETURN doneEND CanBeDone;PROCEDURE Queens*;VAR done: BOOLEAN; i, j: INTEGER; (* # W*)BEGINFOR i := 0 TO 7 DO a[i] := TRUE; x[i] := –1 END;FOR i := 0 TO 14 DO b[i] := TRUE; c[i] := TRUE END;Try(0, done);IF done THENFOR i := 0 TO 7 DO Texts.WriteInt(W, x[ i ], 4) END;Texts.WriteLn(W)ENDEND Queens.Прежде чем закрыть шахматную тему, покажем на примере задачи о восьми ферзях важную модификацию такого поиска методом проб и ошибок. Цель моди%фикации – в том, чтобы найти не одно, а все решения задачи.Выполнить такую модификацию легко. Нужно вспомнить, что кандидаты дол%жны порождаться систематическим образом, так чтобы ни один кандидат не по%рождался больше одного раза. Это соответствует систематическому поиску по де%реву кандидатов, при котором каждый узел проходится в точности один раз. При такой организации после нахождения и печати решения можно просто перейти к следующему кандидату, доставляемому систематическим процессом порожде%ния. Формально модификация осуществляется переносом процедуры%функцииCanBeDone из охраны цикла в его тело и подстановкой тела процедуры вместо ее вызова. При этом нужно учесть, что возвращать логические значения больше не нужно. Получается такая общая рекурсивная схема:PROCEDURE Try;BEGINIF v THEN v # ; 153WHILE (v # v ) DO v #;Try; # v # v #ENDELSE v ENDEND TryИнтересно, что поиск всех возможных решений реализуется более простой программой, чем поиск единственного решения.В задаче о восьми ферзях возможно еще более заметное упрощение. В самом деле, несколько громоздкий механизм перечисления допустимых шагов, состоя%щий из двух процедур First и Next, был нужен для взаимной изоляции цикла линейного поиска очередного безопасного поля (цикл по j внутри Next) и цикла линейного поиска первого j, дающего полное решение. Теперь, благодаря упро%щению охраны последнего цикла, нужда в этом отпала и его можно заменить про%стейшим циклом по j, просто отбирая безопасные j с помощью условного операто%ра IF, непосредственно вложенного в цикл, без использования дополнительных процедур.Так модифицированный алгоритм определения всех 92 решений задачи о восьми ферзях показан ниже. На самом деле есть только 12 существенно различ%ных решений, но наша программа не распознает симметричные решения. Первые12 порождаемых здесь решений выписаны в табл. 3.2. Колонка n справа показы%вает число выполнений проверки безопасности позиций.Среднее значение часто%ты по всем 92 решениям равно 161.PROCEDURE write;(* ADruS35_Queens *)VAR k: INTEGER;BEGINFOR k := 0 TO 7 DO Texts.WriteInt(W, x[k], 4) END;Texts.WriteLn(W)END write;PROCEDURE Try (i: INTEGER);VAR j: INTEGER;BEGINIF i < 8 THENFOR j := 0 TO 7 DOIF a[j] & b[i+j] & c[i-j+7] THENx[i] := j; a[j] := FALSE; b[i+j] := FALSE; c[i-j+7] := FALSE;Try(i + 1);x[i] := –1; a[j] := TRUE; b[i+j] := TRUE; c[i-j+7] := TRUEENDENDELSEЗадача о восьми ферзях Рекурсивные алгоритмы154write;m := m+1 (* v *)ENDEND Try;PROCEDURE AllQueens*;VAR i, j: INTEGER;BEGINFOR i := 0 TO 7 DO a[i] := TRUE; x[i] := –1 END;FOR i := 0 TO 14 DO b[i] := TRUE; c[i] := TRUE END;m := 0;Try(0);Log.String(' # v : '); Log.Int(m); Log.LnEND AllQueens.Таблица 3.2.Таблица 3.2.Таблица 3.2.Таблица 3.2.Таблица 3.2. Двенадцать решений задачи о восьми ферзях x0x1x2x3x4x5x6x7 n0 47 52 61 3876 05 72 63 14 264 06 35 71 42 200 06 47 13 52 136 13 57 20 64 504 14 60 27 53 400 14 63 07 52 072 15 06 37 24 280 15 72 03 64 240 16 25 74 03 264 16 47 03 52 160 17 50 24 63 3363.6. Задача о стабильных бракахПредположим, что даны два непересекающихся множества A и B равного размера n. Требуется найти набор n пар – таких, что a из A и b из B удовлетворяют некоторым ограничениям. Может быть много разных критериев для таких пар;один из них называется правилом стабильных браков.Примем, что A – это множество мужчин, а B – множество женщин. Каждый мужчина и каждая женщина указали предпочтительных для себя партнеров. Если n пар выбраны так, что существуют мужчина и женщина, которые не являются мужем и женой, но которые предпочли бы друг друга своим фактическим супру%гам, то такое распределение по парам называется нестабильным. Если таких пар нет, то распределение стабильно. Подобная ситуация характерна для многих по%хожих задач, в которых нужно сделать распределение с учетом предпочтений, на% 155пример выбор университета студентами, выбор новобранцев различными родами войск и т. п. Пример с браками особенно интуитивен; однако следует заметить,что список предпочтений остается неизменным и после того, как сделано распре%деление по парам. Такое предположение упрощает задачу, но представляет собой опасное искажение реальности (это называют абстракцией).Возможное направление поиска решения – пытаться распределить по парам членов двух множеств одного за другим, пока не будут исчерпаны оба множества.Имея целью найти все стабильные распределения, мы можем сразу сделать набро%сок решения, взяв за образец схему программы AllQueens. Пусть Try(m) означает алгоритм поиска жены для мужчины m, и пусть этот поиск происходит в соот%ветствии с порядком списка предпочтений, заявленных этим мужчиной. Первая версия, основанная на этих предположениях, такова:PROCEDURE Try (m: man);VAR r: rank;BEGINIF m < n THENFOR r := 0 TO n–1 DO r- m;IF THEN ;Try( m); ENDENDELSE v ENDEND TryИсходные данные представлены двумя матрицами, указывающими предпоч%тения мужчин и женщин:VAR wmr: ARRAY n, n OF woman;mwr: ARRAY n, n OF manСоответственно, wmr m обозначает список предпочтений мужчины m, то есть wmr m,r – это женщина, находящаяся в этом списке на r%м месте. Аналогично, mwr w –список предпочтений женщины w, а mwr w,r– мужчина на r%м месте в этом списке.Пример набора данных показан в табл. 3.3.Результат представим массивом женщин x, так что xm обозначает супругу мужчины m. Чтобы сохранить симметрию между мужчинами и женщинами, вво%дится дополнительный массив y, так что yw обозначает супруга женщины w:VAR x, y: ARRAY n OF INTEGERНа самом деле массив y избыточен, так как в нем представлена информация,уже содержащаяся в x. Действительно, соотношения x[y[w]] = w, y[x[m]] = mЗадача о стабильных браках Рекурсивные алгоритмы156выполняются для всех m и w, которые состоят в браке. Поэтому значение yw мож%но было бы определить простым поиском в x. Однако ясно, что использование массива y повысит эффективность алгоритма. Информация, содержащаяся в мас%сивах x и y, нужна для определения стабильности предполагаемого множества браков. Поскольку это множество строится шаг за шагом посредством соединения индивидов в пары и проверки стабильности после каждого преполагаемого брака,массивы x и y нужны даже еще до того, как будут определены все их компоненты.Чтобы отслеживать, какие компоненты уже определены, можно ввести булевские массивы singlem, singlew: ARRAY n OF BOOLEANсо следующими значениями: истинность singlem m означает, что значение xm еще не определено, а singlew w – что не определено yw. Однако, присмотревшись к обсуждаемому алгоритму, мы легко обнаружим, что семейное положение мужчины k определяется значением m с помощью отношенияsinglem[k] = k < mЭто наводит на мысль, что можно отказаться от массива singlem; соответствен%но, имя singlew упростим до single. Эти соглашения приводят к уточнению, пока%занному в следующей процедуре Try. Предикат можно уточнить в конъюнкцию операндов single и , где предикат еще предстоит определить:PROCEDURE Try (m: man);VAR r: rank; w: woman;BEGINIF m < n THENFOR r := 0 TO n–1 DOw := wmr[m,r];IF single[w] & THENx[m] := w; y[w] := m; single[w] := FALSE;Try(m+1);Таблица 3.3.Таблица 3.3.Таблица 3.3.Таблица 3.3.Таблица 3.3. Пример входных данных для wmr и mwr r = 0 12 34 56 7r = 0 12 34 56 7m = 0 61 54 02 73w = 0 35 14 70 26 13 21 57 06 41 74 20 56 31 22 13 07 46 52 57 01 23 64 32 73 14 56 03 21 36 57 40 47 23 45 06 14 52 03 46 17 57 64 13 20 55 10 27 63 54 61 35 20 64 76 24 61 30 75 75 03 16 42 77 61 73 45 20 157single[w] := TRUEENDENDELSE v ENDEND TryУ этого решения все еще заметно сильное сходство с процедурой AllQueensКлючевая задача теперь – уточнить алгоритм определения стабильности. К не%счастью, свойство стабильности невозможно выразить так же просто, как при про%верке безопасности позиции ферзя. Первая особенность, о которой нужно пом%нить, состоит в том, что, по определению, стабильность следует из сравнений рангов (то есть позиций в списках предпочтений). Однако нигде в нашей коллек%ции данных, определенных до сих пор, нет непосредственно доступных рангов мужчин или женщин. Разумеется, ранг женщины w во мнении мужчины m вычис%лить можно, но только с помощью дорогостоящего поиска значения w в wmr m. По%скольку вычисление стабильности – очень частая операция, полезно обеспечить более прямой доступ к этой информации. С этой целью введем две матрицы:rmw: ARRAY man, woman OF rank;rwm: ARRAY woman, man OF rankПри этом rmw m,w обозначает ранг женщины w в списке предпочтений мужчи%ны m, а rwm w,m – ранг мужчины m в аналогичном списке женщины w. Значения этих вспомогательных массивов не меняются и могут быть определены в самом начале по значениям массивов wmr и mwrТеперь можно вычислить предикат , точно следуя его исходно%му определению. Напомним, что мы проверяем возможность соединить браком mи w, где w = wmr m,r, то есть w является кандидатурой ранга r для мужчины m. Про%являя оптимизм, мы сначала предположим, что стабильность имеет место, а потом попытаемся обнаружить возможные помехи. Где они могут быть скрыты? Есть две симметричные возможности:1) может найтись женщина pw с рангом, более высоким, чем у w, по мнению m,и которая сама предпочитает m своему мужу;2) может найтись мужчина pm с рангом, более высоким, чем у m, по мнению w,и который сам предпочитает w своей жене.Чтобы обнаружить помеху первого рода, сравним ранги rwm pw,m и rwm pw,y[pw]для всех женщин, которых m предпочитает w, то есть для всех pw = wmr m,i таких,что i < r. На самом деле все эти женщины pw уже замужем, так как, будь любая из них еще не замужем, m выбрал бы ее еще раньше. Описанный процесс можно сформулировать в виде линейного поиска; имя переменной S является сокраще%нием для Stability (стабильность).i := –1; S := TRUE;REPEATINC(i);Задача о стабильных браках Рекурсивные алгоритмы158IF i < r THENpw := wmr[m,i];IF single[pw] THEN S := rwm[pw,m] > rwm[pw, y[pw]] ENDENDUNTIL (i = r) OR SЧтобы обнаружить помеху второго рода, нужно проверить всех кандидатов pm,которых w предпочитает своей текущей паре m, то есть всех мужчин pm = mwr w,i с i < rwm w,m. По аналогии с первым случаем нужно сравнить ранги rmwp m,w иrmw pm,x[pm]. Однако нужно не забыть пропустить сравнения с теми xpm, где pm еще не женат. Это обеспечивается проверкой pm < m, так как мы знаем, что все мужчины до m уже женаты.Полная программа показана ниже. Таблица 3.4 показывает девять стабильных решений, найденных для входных данных wmr и mwr, представленных в табл. 3.3.PROCEDURE write;(* ADruS36_Marriages *)(* # W*)VAR m: man; rm, rw: INTEGER;BEGINrm := 0; rw := 0;FOR m := 0 TO n–1 DOTexts.WriteInt(W, x[m], 4);rm := rmw[m, x[m]] + rm; rw := rwm[x[m], m] + rwEND;Texts.WriteInt(W, rm, 8); Texts.WriteInt(W, rw, 4); Texts.WriteLn(W)END write;PROCEDURE stable (m, w, r: INTEGER): BOOLEAN; (* *)VAR pm, pw, rank, i, lim: INTEGER;S: BOOLEAN;BEGINi := –1; S := TRUE;REPEATINC(i);IF i < r THENpw := wmr[m,i];IF single[pw] THEN S := rwm[pw,m] > rwm[pw, y[pw]] ENDENDUNTIL (i = r) OR S;i := –1; lim := rwm[w,m];REPEATINC(i);IF i < lim THENpm := mwr[w,i];IF pm < m THEN S := rmw[pm,w] > rmw[pm, x[pm]] ENDENDUNTIL (i = lim) OR S;RETURN SEND stable; 159PROCEDURE Try (m: INTEGER);VAR w, r: INTEGER;BEGINIF m < n THENFOR r := 0 TO n–1 DOw := wmr[m,r];IF single[w] & stable(m,w,r) THENx[m] := w; y[w] := m; single[w] := FALSE;Try(m+1);single[w] := TRUEENDENDELSEwriteENDEND Try;PROCEDURE FindStableMarriages (VAR S: Texts.Scanner);VAR m, w, r: INTEGER;BEGINFOR m := 0 TO n–1 DOFOR r := 0 TO n–1 DOTexts.Scan(S); wmr[m,r] := S.i; rmw[m, wmr[m,r]] := rENDEND;FOR w := 0 TO n–1 DOsingle[w] := TRUE;FOR r := 0 TO n–1 DOTexts.Scan(S); mwr[w,r] := S.i; rwm[w, mwr[w,r]] := rENDEND;Try(0)END FindStableMarriagesЭтот алгоритм прямолинейно реализует обход с возвратом. Его эффектив%ность зависит главным образом от изощренности схемы усечения дерева реше%ний. Несколько более быстрый, но более сложный и менее прозрачный алгоритм дали Маквити и Уилсон [3.1] и [3.2], и они также распространили его на случай множеств (мужчин и женщин) разного размера.Алгоритмы, подобные последним двум примерам, которые порождают все воз%можные решения задачи (при определенных ограничениях), часто используют для выбора одного или нескольких решений, которые в каком%то смысле опти%мальны. Например, в данном примере можно было бы искать решение, которое в среднем лучше удовлетворяет мужчин или женщин или вообще всех.Заметим, что в табл. 3.4 указаны суммы рангов всех женщин в списках пред%почтений их мужей, а также суммы рангов всех мужчин в списках предпочтений их жен. Это величиныЗадача о стабильных браках Рекурсивные алгоритмы160rm = SSSSSm: 0 ≤ m < n: rmw m,x[m]rw = SSSSSm: 0 ≤ m < n: rwm x[m],mТаблица 3.4.Таблица 3.4.Таблица 3.4.Таблица 3.4.Таблица 3.4. Решение задачи о стабильных браках x0x1x2x3x4x5x6x7rm rw c0 63 27 04 15 824 21 11 32 70 46 514 19 449 21 32 06 47 523 12 59 35 32 70 46 118 14 62 45 32 06 47 127 747 55 23 70 46 121 12 143 65 23 06 47 130 547 72 53 70 46 126 10 758 82 53 06 47 135 334c = сколько раз вычислялся предикат (процедуры stable).Решение 0 оптимально для мужчин; решение 8 – для женщин.Решение с наименьшим значением rm назовем стабильным решением, опти%мальным для мужчин; решение с наименьшим rw – оптимальным для женщин.Характер принятой стратегии поиска таков, что сначала генерируются решения,хорошие с точки зрения мужчин, а решения, хорошие с точки зрения женщин, –в конце. В этом смысле алгоритм выгоден мужчинам. Это легко исправить путем систематической перестановки ролей мужчин и женщин, то есть просто меняя местами mwr и wmr, а также rmw и rwmМы не будем дальше развивать эту программу, а задачу включения в програм%му поиска оптимального решения оставим для следующего и последнего примера применения алгоритма обхода с возвратом.3.7. Задача оптимального выбораНаш последний пример алгоритма поиска с возвратом является логическим раз%витием предыдущих двух в рамках общей схемы. Сначала мы применили прин%цип возврата, чтобы находить одно решение задачи. Примером послужили задачи о путешествии шахматного коня и о восьми ферзях. Затем мы разобрались с поис%ком всех решений; примерами послужили задачи о восьми ферзях и о стабильных браках. Теперь мы хотим искать оптимальное решение.Для этого нужно генерировать все возможные решения, но выбрать лишь то,которое оптимально в каком%то конкретном смысле. Предполагая, что оптималь%ность определена с помощью функции f(s), принимающей положительные значе%ния, получаем нужный алгоритм из общей схемы Try заменой операции v инструкциейIF f(solution) > f(optimum) THEN optimum := solution END 161Переменная optimum запоминает лучшее решение из до сих пор найденных.Естественно, ее нужно правильно инициализировать; кроме того, обычно значе%ние f(optimum) хранят еще в одной переменной, чтобы избежать повторных вы%числений.Вот частный пример общей проблемы нахождения оптимального решения в некоторой задаче. Рассмотрим важную и часто встречающуюся проблему выбо%ра оптимального набора (подмножества) из заданного множества объектов при наличии некоторых ограничений. Наборы, являющиеся допустимыми реше%ниями, собираются постепенно посредством исследования отдельных объектов исходного множества. Процедура Try описывает процесс исследования одного объекта, и она вызывается рекурсивно (чтобы исследовать очередной объект) до тех пор, пока не будут исследованы все объекты.Замечаем, что рассмотрение каждого объекта (такие объекты назывались кандидатами в предыдущих примерах) имеет два возможных исхода, а именно:либо исследуемый объект включается в собираемый набор, либо исключается из него. Поэтому использовать циклы repeat или for здесь неудобно, и вместо них можно просто явно описать два случая. Предполагая, что объекты пронумерова%ны 0, 1, ... , n–1, это можно выразить следующим образом:PROCEDURE Try (i: INTEGER);BEGINIF i < n THENIF THEN i- ;Try(i+1); i- END;IF THENTry(i+1)ENDELSE ENDEND TryУже из этой схемы очевидно, что есть 2n возможных подмножеств; ясно, что нужны подходящие критерии отбора, чтобы радикально уменьшить число иссле%дуемых кандидатов. Чтобы прояснить этот процесс, возьмем конкретный пример задачи выбора: пусть каждый из n объектов a0, ... ,a n–1 характеризуется своим ве%сом и ценностью. Пусть оптимальным считается тот набор, у которого суммарная ценность компонент является наибольшей, а ограничением пусть будет некото%рый предел на их суммарный вес. Эта задача хорошо известна всем путешест%венникам, которые пакуют чемоданы, делая выбор из n предметов таким образом,чтобы их суммарная ценность была наибольшей, а суммарный вес не превышал некоторого предела.Теперь можно принять решения о представлении описанных сведений в гло%бальных переменных. На основе приведенных соображений сделать выбор легко:Задача оптимального выбора Рекурсивные алгоритмы162TYPE Object = RECORD weight, value: INTEGER END;VAR a: ARRAY n OF Object;limw, totv, maxv: INTEGER;s, opts: SETПеременные limw и totv обозначают предел для веса и суммарную ценность всех n объектов. Эти два значения постоянны на протяжении всего процесса вы%бора. Переменная s представляет текущее состояние собираемого набора объек%тов, в котором каждый объект представлен своим именем (индексом). Перемен%ная opts – оптимальный набор среди исследованных к данному моменту, а maxv –его ценность.Каковы критерии допустимости включения объекта в собираемый набор?Если речь о том, имеет ли смысл включать объект в набор, то критерий здесь – не будет ли при таком включении превышен лимит по весу. Если будет, то можно не добавлять новые объекты к текущему набору. Однако если речь об исключении, то допустимость дальнейшего исследования наборов, не содержащих этого элемен%та, определяется тем, может ли ценность таких наборов превысить значение для оптимума, найденного к данному моменту. И если не может, то продолжение по%иска, хотя и может дать еще какое%нибудь решение, не приведет к улучшению уже найденного оптимума. Поэтому дальнейший поиск на этом пути бесполезен. Из этих двух условий можно определить величины, которые нужно вычислять на каждом шаге процесса выбора:1. Полный вес tw набора s, собранного на данный момент.2. Еще достижимая с набором s ценность avЭти два значения удобно представить параметрами процедуры Try. Теперь ус%ловие можно сформулирловать так:tw + a[i].weight < limw а последующую проверку оптимальности записать так:IF av > maxv THEN (* , #*)opts := s; maxv := avENDПоследнее присваивание основано на том соображении, что когда все n объек%тов рассмотрены, достижимое значение совпадает с достигнутым. Условие - выражается так:av – a[i].value > maxvДля значения av – a[i].value, которое используется неоднократно, вводится имя av1, чтобы избежать его повторного вычисления.Теперь вся процедура составляется из уже рассмотренных частей с добавлени%ем подходящих операторов инициализации для глобальных переменных. Обра%тим внимание на легкость включения и исключения из множества s с помощью операций для типа SET. Результаты работы программы показаны в табл. 3.5. 163TYPE Object = RECORD value, weight: INTEGER END; (* ADruS37_OptSelection *)VAR a: ARRAY n OF Object;limw, totv, maxv: INTEGER;s, opts: SET;PROCEDURE Try (i, tw, av: INTEGER);VAR tw1, av1: INTEGER;BEGINIF i < n THEN(* *)tw1 := tw + a[i].weight;IF tw1 <= limw THENs := s + {i};Try(i+1, tw1, av);s := s – {i}END;(* *)av1 := av – a[i].value;IF av1 > maxv THENTry(i+1, tw, av1)ENDELSIF av > maxv THENmaxv := av; opts := sENDEND Try;Задача оптимального выбораТаблица 3.5.Таблица 3.5.Таблица 3.5.Таблица 3.5.Таблица 3.5. Пример результатов работы программы Selection при выборе из 10 объектов (вверху). Звездочки отмечают объекты из отпимальных наборов opts для ограничений на суммарный вес от 10 до 120 :10 11 12 13 14 15 16 17 18 19 : 18 20 17 19 25 21 27 23 25 24limw ↓maxv10*18 20*27 30**52 40***70 50****84 60*****99 70*****115 80******130 90******139 100*******157 110********172 120********183 Рекурсивные алгоритмы164PROCEDURE Selection (WeightInc, WeightLimit: INTEGER);BEGINlimw := 0;REPEATlimw := limw + WeightInc; maxv := 0;s := {}; opts := {}; Try(0, 0, totv);UNTIL limw >= WeightLimitEND Selection.Такая схема поиска с возвратом, в которой используются ограничения для предотвращения избыточных блужданий по дереву поиска, называется методомветвей и границ (branch and bound algorithm).Упражнения3.1. (Ханойские башни.) Даны три стержня и n дисков разных размеров. Диски могут быть нанизаны на стержни, образуя башни. Пусть n дисков первона%чально находятся на стержне A в порядке убывания размера, как показано на рис. 3.9 для n = 3. Задание в том, чтобы переместить n дисков со стержня A на стержень C, причем так, чтобы они оказались нанизаны в том же порядке.Этого нужно добиться при следующих ограничениях:1. На каждом шаге со стержня на стержень перемещается только один диск.2. Диск нельзя нанизывать поверх диска меньшего размера.3. Стержень B можно использовать в качестве вспомогательного хранилища.Требуется найти алгоритм выполнения этого задания. Заметим, что башню удобно рассматривать как состоящую из одного диска на вершине и башни,составленной из остальных дисков. Опишите алгоритм в виде рекурсивной программы.3.2. Напишите процедуру порождения всех n! перестановок n элементов a0, ..., a n–1in situ, то есть без использования другого массива. После порожде%ния очередной перестановки должна вызываться передаваемая в качестве па%раметра процедура Q, которая может, например, печатать порожденную пере%становку.Рис. 3.9. Ханойские башни 165Подсказка. Считайте, что задача порождения всех перестановок элементов a0, ..., a m–1 состоит из m подзадач порождения всех перестановок элементов a0, ..., a m–2, после которых стоит am–1, где в i%й подзадаче предварительно были переставлены два элемента ai и am–1 3.3. Найдите рекурсивную схему для рис. 3.10, который представляет собой су%перпозицию четырех кривых W1, W2, W3, W4. Эта структура подобна кривымСерпиньского (рис. 3.6). Из рекурсивной схемы получите рекурсивную про%грамму для рисования этих кривых.Рис. 3.10. Кривые W1 – W4 3.4. Из 92 решений, вычисляемых программой AllQueens в задаче о восьми фер%зях, только 12 являются существенно различными. Остальные получаются отражениями относительно осей или центральной точки. Придумайте про%грамму, которая определяет 12 основных решений. Например, обратите вни%мание, что поиск в столбце 1 можно ограничить позициями 1–4.3.5. Измените программу для задачи о стабильных браках так, чтобы она находи%ла оптимальное решение (для мужчин или женщин). Получится пример применения метода ветвей и границ, уже реализованного в задаче об опти%мальном выборе (программа Selection).3.6. Железнодорожная компания обслуживает n станций S0, ... , Sn–1. В ее планах –улучшить обслуживание пассажиров с помощью компьютеризованных информационных терминалов. Предполагается, что пассажир указывает свои станции отправления SA и назначения SD и (немедленно) получает расписа%Упражнения Рекурсивные алгоритмы166ние маршрута с пересадками и с минимальным полным временем поездки.Напишите программу для вычисления такой информации. Предположите,что график движения поездов (банк данных для этой задачи) задан в подхо%дящей структуре данных, содержащей времена отправления (= прибытия)всех поездов. Естественно, не все станции соединены друг с другом прямыми маршрутами (см. также упр. 1.6).3.7. Функция Аккермана A определяется для всех неотрицательных целых аргу%ментов m и n следующим образом:A(0, n) = n + 1A(m, 0) = A(m–1, 1) (m > 0)A(m, n) = A(m–1, A(m, n–1)) (m, n > 0)Напишите программу для вычисления A(m,n), не используя рекурсию. В ка%честве образца используйте нерекурсивную версию быстрой сортировки(программа NonRecursiveQuickSort). Сформулируйте общие правила для преобразования рекурсивных программ в итеративные.Литература[3.1] McVitie D. G. and Wilson L. B. The Stable Marriage Problem. Comm. ACM, 14,No. 7 (1971), 486–492.[3.2] McVitie D. G. and Wilson L. B. Stable Marriage Assignment for Unequal Sets.Bit, 10, (1970), 295–309.[3.3] Space Filling Curves, or How to Waste Time on a Plotter. Software – Practice and Experience, 1, No. 4 (1971), 403–440.[3.4] Wirth N. Program Development by Stepwise Refinement. Comm. ACM, 14,No. 4 (1971), 221–227. 1 ... 9 10 11 12 13 14 15 16 ... 22

Глава 4Динамические структурыданных4.1. Рекурсивные типы данных ..................................... 168 4.2. Указатели ......................... 170 4.3. Линейные списки .............. 175 4.4. Деревья ............................ 191 4.5. Сбалансированные деревья ................................... 210 4.6. Оптимальные деревья поиска ..................................... 220 4.7. Б<деревья (BУпражнения ............................. 250Литература .............................. 254 Динамические структуры данных1684.1. Рекурсивные типы данныхВ главе 1 массивы, записи и множества были введены в качестве фундаменталь%ных структур данных. Мы назвали их фундаментальными, так как они являются строительными блоками, из которых формируются более сложные структуры,а также потому, что на практике они встречаются чаще всего. Смысл определения типа данных, а затем определения переменных, имеющих этот тип, состоит в том,чтобы раз и навсегда фиксировать диапазон значений этих переменных, а значит,и способ их размещения в памяти. Поэтому такие переменные называют статическими. Однако есть много задач, где нужны более сложные структуры данных.Для таких задач характерно, что не только значения, но и структура переменных меняется во время вычисления. Поэтому их называют динамическими структурами. Естественно, компоненты таких структур – на определенном уровне разреше%ния – являются статическими, то есть принадлежат одному из фундаментальных типов данных. Эта глава посвящена построению, анализу и работе с динамиче%скими структурами данных.Надо заметить, что существуют близкие аналогии между методами структури%рования алгоритмов и данных. Эта аналогия, как и любая другая, не является пол%ной, тем не менее сравнение методов структурирования программ и данных по%учительно.Элементарный неделимый оператор – присваивание значения некоторой пе%ременной. Соответствующий член семейства структур данных – скалярный, не%структурированный тип. Эта пара представляет собой неделимые строительные блоки для составных операторов и для типов данных. Простейшие структуры,получаемые посредством перечисления, суть последовательность операторов и запись. И та, и другая состоят из конечного (обычно небольшого) числа явно пе%речисленных компонент, которые все могут быть различными. Если все компо%ненты идентичны, то их не обязательно выписывать по отдельности: в этом случае используют оператор for и массив, чтобы указать известное, конечное число по%вторений. Выбор между двумя или более элементами выражается условным опе%ратором и расширением записевых типов соответственно. И наконец, повторение с заранее неизвестным (и потенциально бесконечным) числом шагов выражается операторами while и repeat. Соответствующая структура данных – последова%тельность (файл) – это простейшее средство для построения типов с бесконечной мощностью.Возникает вопрос: существует ли структура данных, которая аналогичным образом соответствовала бы оператору процедуры? Естественно, в этом отно%шении самым интересным и новым свойством процедур является рекурсия.Значения такого рекурсивного типа данных должны содержать одну или более компонент, принадлежащих этому же типу, подобно тому как процедура может содержать один или более вызовов самой себя. Как и процедуры, определения ти%пов данных могли бы быть явно или косвенно рекурсивными.Простой пример объекта, который весьма уместно представлять рекурсивно определенным типом, – арифметическое выражение, имеющееся в языках про% 169граммирования. Рекурсия используется, чтобы отразить возможность вложений,то есть использования подвыражений в скобках в качестве операндов выражений.Поэтому дадим следующее неформальное определение выражения:Выражение состоит из терма, за которым следует знак операции, за которым следует терм. (Два этих терма – операнды операции.) Терм – это либо перемен%ная, представленная идентификатором, либо выражение, заключенное в скобки.Тип данных, значениями которого представляются такие выражения, может быть легко описан, если использовать уже имеющиеся средства, добавив к ним рекурсию:TYPE expression = RECORD op: INTEGER;opd1, opd2: termENDTYPE term =RECORDIF t: BOOLEAN THEN id: Name ELSE subex: expression ENDENDПоэтому каждая переменная типа term состоит из двух компонент, а именно поля признака t, а также, если t истинно, поля id, или в противном случае поля subex. Например, рассмотрим следующие четыре выражения:1.x + y2.x – (y * z)3.(x + y) * (z – w)4.(x/(y + z)) * wЭти выражения схематически показаны на рис. 4.1, где видна их «матрешечная»,рекурсивная структура, а также показано размещение этих выражений в памяти.Второй пример рекурсивной структуры данных – семейная родословная.Пусть родословная определена именем индивида и двумя родословными его ро%дителей. Это определение неизбежно приводит к бесконечной структуре. Реаль%ные родословные ограничены, так как о достаточно далеких предках информация отсутствует. Снова предположим, что это можно учесть с помощью некоторой условной структуры (ped от pedigree – родословная):TYPE ped = RECORD IF known: BOOLEAN THEN name: Name; father, mother: ped ENDENDЗаметим, что каждая переменная типа ped имеет по крайней мере одну компо%ненту, а именно поле признака known (известен). Если его значение равно TRUE,то есть еще три поля; в противном случае эти поля отсутствуют. Пример конкрет%ного значения показан ниже в виде выражения с вложениями, а также с помощью диаграммы, показывающей возможное размещение в памяти (см. рис. 4.2).(T, Ted, (T, Fred, (T, Adam, (F), (F)), (F)), (T, Mary, (F), (T, Eva, (F), (F)))Понятно, почему важны условия в таких определениях: это единственное средство ограничить рекурсивную структуру данных, поэтому они обязательноРекурсивные типы данных Динамические структуры данных170Рис. 4.1. Схемы расположения в памяти рекурсивных записевых структурРис. 4.2. Пример рекурсивной структуры данных сопровождают каждое рекурсивное определе%ние. Здесь особенно четко видна аналогия между структурированием программ и данных. Услов%ный оператор (или оператор выбора) обяза%тельно должен быть частью каждой рекурсивной процедуры, чтобы обеспечить завершение ее вы%полнения. На практике динамические структу%ры используют ссылки или указатели на свои элементы, а идея альтернативы (для завершения рекурсии) реализуется в понятии указателя, как объясняется в следующем разделе.4.2. УказателиХарактерное свойство рекурсивных структур,четко отличающее их от фундаментальных струк%тур (массивов, записей, множеств), – это их спо%собность менять свой размер. Поэтому невозмож%но выделить фиксированный участок памяти для размещения рекурсивно определенной структу%ры, и, как следствие, компилятор не может свя%зать конкретные адреса с компонентами таких переменных. Метод, чаще всего применяемый для решения этой проблемы, состоит в динами 171ческом распределении памяти (dynamic allocation of storage), то есть распределе%нии памяти отдельным компонентам в тот момент, когда они возникают при вы%полнения программы, а не во время трансляции. При этом компилятор отводит фиксированный объем памяти для хранения адреса динамически размещаемой компоненты вместо самой компоненты. Например, родословная, показанная на рис. 4.2, будет представлена отдельными – вполне возможно, несмежными – за%писями, по одной на каждого индивида. Эти записи для отдельных людей связаны с помощью адресов, записанных в соответствующие поля father (отец) и mother(мать). Графически это лучше всего выразить с помощью стрелок или указателей(рис. 4.3).Рис. 4.3. Структура данных, связанная указателямиВажно подчеркнуть, что использование указателей для реализации рекурсив%ных структур – это всего лишь технический прием. Программисту не обязательно знать об их существовании. Память может распределяться автоматически в тот момент, когда в первый раз используется ссылка на новую компоненту. Но если явно разрешается использование указателей, то можно построить и более общие структуры данных, чем те, которые можно описать с помощью рекурсивных опре%делений. В частности, тогда можно определять потенциально бесконечные или циклические структуры (графы) и указывать, что некоторые структуры исполь%зуются совместно. Поэтому в развитых языках программирования принято разре%шать явные манипуляции не только с данными, но и со ссылками на них. Это тре%бует проведения четкого различия на уровне обозначений между данными и ссылками на данные, а также необходимость иметь типы данных, значениями ко%торых являются указатели (ссылки) на другие данные. Мы будем использовать следующую нотацию для этой цели:TYPE T = POINTER TO T0Такое определение типа означает, что значения типа T – это указатели на дан%ные типа T0. Принципиально важно, что тип элементов, на которые ссылаетсяУказатели Динамические структуры данных172указатель, очевиден из определения T. Мы говорим, что T связан с T0. Эта связь отличает указатели в языках высокого уровня от адресов в машинном языке и яв%ляется весьма важным средством повышения безопасности в программировании посредством отражения семантики программы синтаксическими средствами.Значения указательных типов порождаются при каждом динамическом разме%щении элемента данных. Мы будет придерживаться правила, что такое событие всегда должно описываться явно, в противоположность механизму автоматичес%кого размещения элемента данных при первой ссылке на него. С этой целью вве%дем процедуру NEW. Если дана указательная переменная p типа T, то операторNEW(p) размещает где%то в памяти переменную типа T0, а указатель на эту новую переменную записывает в переменную p (см. рис. 4.4). Сослаться в программе на само указательное значение теперь можно с помощью p (то есть это значение ука%зательной переменной p). При этом переменная, на которую ссылается p, обозна%чается как p^. Обычно используют ссылки на записи. Если у записи, на которую ссылается указатель p, есть, например, поле x, то оно обозначается как p^.x. По%скольку ясно, что полями обладает не указатель, а только запись p^, то мы допус%каем сокращенную нотацию p.x вместо p^.xРис. 4.4. Динамическое размещение переменной p^Выше указывалось, что в каждом рекурсивном типе необходима компонента,позволяющая различать возможные варианты, чтобы можно было обеспечить ко%нечность рекурсивных структур. Пример семейной родословной показывает весь%ма часто встречающуюся ситуацию, когда в одном из двух случаев другие компо%ненты отсутствуют. Это выражается следующим схематическим определением:TYPE T = RECORDIF nonterminal: BOOLEAN THEN S(T) ENDENDS(T) обозначает последовательность определений полей, среди которых есть одно или более полей типа T, чем и обеспечивается рекурсивность. Все структуры типа, определенного по этой схеме, имеют древесное (или списковое) строение,подобное показанному на рис. 4.3. Его особенность – наличие указателей на ком%поненты данных, состоящие только из поля признака, то есть не несущие другой полезной информации. Метод реализации с явными укзателями подсказывает простой способ сэкономить память, разрешив включать информацию о поле при% 173знака в само указательное значение. Обычно для этого расширяют диапазон значе%ний всех указательных типов единственным значением, которое вообще не являет%ся ссылкой ни на какой элемент. Обозначим это значение специальным символомNIL и постулируем, что все переменные указательных типов могут принимать зна%чение NIL. Вследствие такого расширения диапазона указательных значений ко%нечные структуры могут порождаться при отсутствии вариантов (условий) в их(рекурсивных) определениях.Ниже даются новые формулировки объявленных ранее явно рекурсивных ти%пов данных с использованием указателей. Заметим, что здесь уже нет поля known,так как p.known теперь выражается посредством p = NIL. Переименование типа ped в Person (индивид) отражает изменение точки зрения, произошедшее благо%даря введению явных указательных значений. Теперь вместо того, чтобы сначала рассматривать данную структуру целиком и уже потом исследовать ее подструк%туры и компоненты, внимание сосредоточивается прежде всего на компонентах,а их взаимная связь (представленная указателями) не фиксирована никаким яв%ным определением.TYPE term =POINTER TO TermDescriptor;TYPE exp =POINTER TO ExpDescriptor;TYPE ExpDescriptor =RECORD op: INTEGER; opd1, opd2: term END;TYPE TermDescriptor = RECORD id: ARRAY 32 OF CHAR ENDTYPE Person =POINTER TO RECORDname: ARRAY 32 OF CHAR;father, mother: PersonENDЗамечание. Тип Person соответствует указателям на записи безымянного типа(PersonDescriptor).Структура данных, представляющая родословную и показанная на рис. 4.2 и 4.3,снова показана на рис. 4.5, где указатели на неизвестных лиц обозначены констан%той NIL. Получающаяся экономия памяти очевидна.В контексте рис. 4.5 предположим, что Fred и Mary – брат и сестра, то есть у них общие отец и мать. Эту ситуацию легко выразить заменой двух значений NILв соответствующих полях двух записей. Реализация, которая скрывает указателиРис. 4.5. Структура данных с указателями, имеющими значение NILУказатели Динамические структуры данных174или использует другие приемы работы с памятью, заставила бы программиста представить записи для родителей, то есть Adam и Eva, дважды. Хотя для чтения данных не важно, одной или двумя записями представлены два отца (или две ма%тери), разница становится существенной, когда разрешено частичное изменение данных. Трактовка указателей как явных элементов данных, а не как скрытых средств реализации, позволяет программисту четко указать, где нужно совмес%тить используемые блоки памяти, а где – нет.Другое следствие явных указателей – возможность определять и манипулиро%вать циклическими структурами данных. Разумеется, такая дополнительная гиб%кость не только предоставляет дополнительные возможности, но и требует от программиста повышенного внимания, поскольку работа с циклическими струк%турами данных легко может привести к бесконечным процессам.Эта тесная связь мощи и гибкости средств с опасностью их неправильного использования хорошо известна в программировании и заставляет вспомнить оператор GOTO. В самом деле, если продолжить аналогию между структурами программ и данных, то чисто рекурсивные структуры данных можно сопоста%вить с процедурами, а введение указателей сравнимо с операторами GOTO. Ибо как оператор GOTO позволяет строить любые программные схемы (включая циклы), так и указатели позволяют строить любые структуры данных (включая кольцевые). [Однако в отличие от операторов GOTO, типизированные указатели не нарушают структурированности соответствующих записей – прим. перев.]Параллели между структурами управления и структурами данных суммирова%ны в табл. 4.1.Таблица 4.1.Таблица 4.1.Таблица 4.1.Таблица 4.1.Таблица 4.1. Соответствия структур управления и структур данныхСхема построенияСхема построенияСхема построенияСхема построенияСхема построенияОператор программыОператор программыОператор программыОператор программыОператор программыТип данныхТип данныхТип данныхТип данныхТип данныхНеделимый элементПрисваиваниеСкалярный типПеречислениеОператорнаяЗапись последовательностьПовторение (числоОператор forМассив повторений известно)ВыборУсловный операторОбъединение типов(запись с вариантами)ПовторениеОператор while илиПоследовательностный тип repeatРекурсияПроцедураРекурсивный тип данныхОбщий графОператор переходаСтруктура, связанная указателямиВ главе 3 мы видели, что итерация является частным случаем рекурсии и что вы%зов рекурсивной процедуры P, определенной в соответствии со следующей схемой,PROCEDURE P;BEGINIF B THEN P0; P ENDEND 175где оператор P0 не включает в себя P и может быть заменен на эквивалентный опе%ратор циклаWHILE B DO P0 ENDАналогии, представленные в табл. 4.1, подсказывают, что похожая связь долж%на иметь место между рекурсивными типами данных и последовательностью.В самом деле, рекурсивный тип, определенный в соответствии со схемойTYPE T = RECORDIF b: BOOLEAN THEN t0: T0; t: T ENDENDгде тип T0 не имеет отношения к T, может быть заменен на эквивалентную после%довательность элементов типа T0Остальная часть этой главы посвящена созданию и работе со структурами дан%ных, компоненты которых связаны с помощью явных указателей. Особое внима%ние уделяется конкретным простым схемам; из них можно понять, как работать с более сложными структурами. Такими простыми схемами являются линейный список (простейший случай) и деревья. Внимание, которое мы уделяем этим средствам структурирования данных, не означает, что на практике не встречают%ся более сложные структуры. Следующий рассказ, опубликованный в цюрихской газете в июле 1922 г., доказывает, что странности могут встречаться даже в тех случаях, которые обычно служат образцами регулярных структур, таких как (генеа%логические) деревья. Мужчина жалуется на свою жизнь следующим образом:Я женился на вдове, у которой была взрослая дочь. Мой отец, который частонас навещал, влюбился в мою приемную дочь и женился на ней. Таким образом, мойотец стал моим зятем, а моя приемная дочь стала моей мачехой. Через несколькомесяцев моя жена родила сына, который стал сводным братом моему отцу и моимдядей. Жена моего отца, то есть моя приемная дочь, тоже родила сына, которыйстал мне братом и одновременно внуком. Моя жена стала мне бабушкой, так какона мать моей мачехи. Следовательно, я муж моей жены и в то же время ее приемный внук; другими словами, я сам себе дедушка.1 ... 10 11 12 13 14 15 16 17 ... 22

Глава 5Хэширование5.1. Введение .......................... 256 5.2. Выбор хэш<функции ......... 257 5.3. Разрешение коллизий ...... 257 5.4. Анализ хэширования ........ 261Упражнения ............................. 263Литература .............................. 263 Хэширование2565.1. ВведениеВ главе 4 подробно обсуждалась следующая основная проблема: если задан набор элементов, характеризующихся ключом (который определяет отношение поряд%ка), то как организовать этот набор, чтобы извлечение элемента с заданным клю%чом требовало наименьших усилий? Ясно, что в конечном счете доступ к каждому элементу в памяти компьютера осуществляется указанием его адреса в памяти.Поэтому вышеуказанная проблема по сути сводится к нахождению подходящего отображения H ключей (K) в адреса (A):H: K → AВ главе 4 это отображение реализовывалось с помощью различных алгоритмов поиска в списках и деревьях на основе разных способов организации данных.Здесь мы опишем еще один подход, простой по сути и во многих случаях очень эффективный. Затем мы обсудим и некоторые его недостатки.В этом методе данные организуются с помощью массива. Поэтому H является отображением, преобразующим ключи в индексы массива, откуда и происходит название преобразование ключей, нередко используемое для этого метода. Заме%тим, что здесь нам не понадобятся процедуры динамического размещения; массив является одной из фундаментальных, статических структур. Метод преобра%зования ключей часто используют в тех задачах, где с примерно равным успехом можно применить и деревья.Фундаментальная трудность при использовании преобразования ключей заключается в том, что множество возможных значений ключей гораздо больше,чем множество доступных адресов в памяти (индексов массива). К примеру,возьмем имена длиной до 16 букв в качестве ключей, идентифицирующих отдель%ных людей во множестве из тысячи человек. Здесь есть 26 16 возможных значений ключей, которые нужно отобразить на 10 3 возможных индексов. Очевидно, что функция H отображает несколько значений аргументов в одно значение индекса.Если задан ключ k, то первый шаг операции поиска состоит в вычислении соот%ветствующего индекса h = H(k), а второй – очевидно, обязательный – шаг состоит в проверке того, действительно ли элемент с ключом k соответствует элементу массива (таблицы) T с индексом h, то есть выполняется ли равенство T[H(k)].key = kМы сразу сталкиваемся с двумя вопросами:1. Какую функцию H надо взять?2. Что делать, если H не смогла вычислить адрес искомого элемента?Ответ на второй вопрос состоит в том, чтобы использовать метод, который даст альтернативную позицию, скажем индекс h', и если там по%прежнему нет иско%мого элемента, то третий индекс h", и т. д. (Такие попытки обозначаются ниже какпробы (probe) – прим. перев.) Ситуацию, когда в вычисленной позиции находится элемент, отличный от искомого, называют коллизией; задача порождения альтер%нативных индексов называется разрешением коллизий. Далее мы обсудим выбор функции преобразования ключей и методы разрешения коллизий. 2575.2. Выбор хэшGфункцииХорошая функция преобразования ключей должна обеспечивать как можно бо%лее равномерное распределение ключей по всему диапазону значений индекса.Других ограничений на распределение нет, но на самом деле желательно, чтобы оно казалось совершенно случайным. Это свойство дало методу несколько нена%учное название хэширование (hashing от англ. «превращать в фарш» и «мешани%на» – прим. перев.). H называется хэшфункцией. Очевидно, эта функция должна допускать эффективное вычисление, то есть состоять из очень небольшого числа основных арифметических операций.Предположим, что имеется функция преобразования ORD(k), которая вычис%ляет порядковый номер ключа k во множестве всех возможных ключей. Кроме того, предположим, что индекс массива i принимает значения в диапазоне целых чисел 0 .. N–1, где N – размер массива. Тогда есть очевидный вариант:H(k) = ORD(k) MOD NТакой выбор обеспечивает равномерное распределение ключей по диапазону индексов и поэтому является основой большинства хэш%функций. Это выраже%ние очень быстро вычисляется, если N есть степень 2, но именно этого случая сле%дует избегать, если ключи являются последовательностями букв. Предположе%ние, что все ключи равно вероятны, в этом случае неверно, и на самом деле слова,отличающиеся лишь немногими буквами, будут с большой вероятностью отобра%жаться на одно и то же значение индекса, так что получится весьма неоднородное распределение. Поэтому особенно рекомендуется в качестве значения N выбирать простое число [5.2]. Как следствие придется использовать полную операцию де%ления, которую нельзя заменить простым отбрасыванием двоичных цифр, но это не является проблемой на большинстве современных компьютеров, имеющих встроенную инструкцию деления.Часто используют хэш%функции, состоящие в применении логических опера%ций, таких как исключающее «или», к некоторым частям ключа, представленного как последовательность двоичных цифр. На некоторых компьютерах эти опера%ции могут выполняться быстрее, чем деление, но иногда они приводят к удиви%тельно неоднородному распределению ключей по диапазону индексов. Поэтому мы воздержимся от дальнейшего обсуждения таких методов.5.3. Разрешение коллизийЕсли оказывается, что элемент таблицы, соответствующий данному ключу, не яв%ляется искомым элементом, то имеет место коллизия, то есть у двух элементов ключи отображаются на одно значение индекса. Тогда нужна вторая проба с неко%торым значением индекса, полученным из данного ключа детерминированным способом. Есть несколько способов порождения вторичных индексов. Очевидный способ – связать все элементы с одинаковым первичным индексом H(k) в связный список. Это называют прямым связыванием (direct chaining). Элементы этого списка могут находиться в первичной таблице или вне ее; во втором случае об%Разрешение коллизий Хэширование258ласть памяти, где они размещаются, называется областью переполнения (overflow area). Недостатки этого метода – необходимость поддерживать вторичные спис%ки, а также что каждый элемент таблицы должен содержать указатель (или ин%декс) на список конфликтующих элементов.Альтернативный способ разрешения коллизий состоит в том, чтобы вообще отказаться от списков и просто перебирать другие элементы в той же таблице,пока не будет найден искомый элемент либо пустая позиция, что означает отсут%ствие указанного ключа в таблице. Такой метод называется открытой адресацией(open addressing [5.3]). Естественно, последовательность индексов во вторичных попытках должна быть всегда одной и той же для заданного ключа. Тогда алго%ритм поиска в таблице может быть кратко описан следующим образом:h := H(k); i := 0;REPEATIF T[h].key = k THEN ELSIF T[h].key = free THEN ELSE (* *)i := i+1; h := H(k) + G(i)ENDUNTIL ( )В литературе предлагались разные функции для разрешения коллизий. Обзор темы, сделанный Моррисом в 1968 г. [4.8], вызвал значительную активность в этой области. Простейший метод – проверить соседнюю позицию (считая таблицу циклической), пока не будет найден либо элемент с указанным ключом,либо пустая позиция. Таким образом, G(i) = i; в этом случае индексы hi, исполь%зуемые для поиска, даются выражениями h0= H(k)h i= (h i–1 + i) MOD N,i = 1 ... N–1Этот способ называется методом линейных проб (linear probing). Его недоста%ток – тенденция элементов к скучиванию вблизи первичных ключей (то есть клю%чей, не испытавших коллизии при вставке). Конечно, в идеале функция G должна тоже распределять ключи равномерно по множеству свободных позиций. Однако на практике это довольно сложно обеспечить, и здесь предпочитают компромисс%ные методы, которые не требуют сложных вычислений, но все же работают лучше,чем линейная функция. Один из них состоит в использовании квадратичной фун%кции, так что индексы для последовательных проб задаются формулами h0= H(k)h i= (h0 + i2) MOD N, i > 0Заметим, что при вычислении очередного индекса можно обойтись без возве%дения в квадрат, если воспользоваться следующими рекуррентными соотношени%ями для hi = i2 и di = 2i + 1:h i+1= h i + d id i+1= d i + 2, i > 0причем h0 = 0 и d0 = 1. Этот способ называется методом квадратичных проб(quadratic probing), и он, в общем, обходит упомянутую проблему скучивания, 259практически не требуя дополнительных вычислений. Незначительный недоста%ток здесь в том, что при последовательных пробах проверяются не все элементы таблицы, то есть при вставке можно не обнаружить свободной позиции, хотя в таблице они еще есть. На самом деле в методе квадратичных проб проверяется по крайней мере половина таблицы, если ее размер N является простым числом.Это утверждение можно доказать следующим образом. Тот факт, что i%я и j%я про%бы попадают в один элемент таблицы, выражается уравнением i2 MOD N = j2 MOD N(i2 – j2) ≡ 0 (modulo N)Применяя формулу для разности квадратов, получаем(i + j)(i – j) ≡ 0 (modulo N)и так как i ≠ j, то заключаем, что хотя бы одно из чисел i или j должно быть не меньше N/2, чтобы получить i+j = c*N с целым c. На практике этот недостаток не важен, так как необходимость выполнять N/2 вторичных проб при разрешении коллизий случается крайне редко, и только если таблица уже почти полна.В качестве применения описанной техники перепишем процедуру порожде%ния перекрестных ссылок из раздела 4.4.3. Главные отличия – в процедуре search и в замене указательного типа Node глобальной хэш%таблицей слов T. Хэш%функ%ция H вычисляется как остаток от деления на размер таблицы; для разрешения коллизий применяются квардатичные пробы. Подчеркнем, что для хорошей производительности важно, чтобы размер таблицы был простым числом.Хотя метод хэширования весьма эффективен в этом случае, – даже более эф%фективен, чем методы, использующие деревья, – у него есть и недостаток. Про%смотрев текст и собрав слова, мы, вероятно, захотим создать из них алфавитный список. Это несложно, если данные организованы в виде дерева, потому что прин%цип упорядоченности – основа этого способа организации. Однако простота теря%ется, если используется хэширование. Здесь и проявляется смысл слова «хэширо%вание». Для печати таблицы придется не только выполнить сортировку (которая здесь не показана), но оказывается даже предпочтительным отслеживать вставляе%мые ключи, явным образом связывая их в список. Поэтому высокая производитель%ность метода хэширования при поиске частично компенсируется дополнительны%ми операциями, необходимыми для завершения полной задачи порождения упорядоченного указателя перекрестных ссылок.CONST N = 997; (* , *)(*ADruS53_CrossRef*)WordLen = 32; (* *)Noc = 16; (* . *)TYPEWord = ARRAY WordLen OF CHAR;Table = POINTER TO ARRAY N OFRECORD key: Word; n: INTEGER;lno: ARRAY Noc OF INTEGEREND;VAR line: INTEGER;Разрешение коллизий Хэширование260PROCEDURE search (T: Table; VAR a: Word);VAR i, d: INTEGER; h: LONGINT; found: BOOLEAN;(* # line*)BEGIN(* v– h a*)i := 0; h := 0;WHILE a[i] > 0X DO h := (256*h + ORD(a[i])) MOD N; INC(i) END;d := 1; found := FALSE;REPEATIF T[h].key = a THEN (* *)found := TRUE; T[h].lno[T[h].n] := line;IF T[h].n < Noc THEN INC(T[h].n) ENDELSIF T[h].key[0] = " " THEN (* *)found := TRUE; COPY(a, T[h].key); T[h].lno[0] := line; T[h].n := 1ELSE (* *) h := h+d; d := d+2;IF h >= N THEN h := h–N END;IF d = N THEN Texts.WriteString(W," "); HALT(88)ENDENDUNTIL foundEND search;PROCEDURE Tabulate (T: Table);VAR i, k: INTEGER;(* # W*)BEGINFOR k := 0 TO N–1 DOIF T[k].key[0] # " " THENTexts.WriteString(W, T[k].key); Texts.Write(W, TAB);FOR i := 0 TO T[k].n –1 DO Texts.WriteInt(W, T[k].lno[i], 4) END;Texts.WriteLn(W)ENDENDEND Tabulate;PROCEDURE CrossRef (VAR R: Texts.Reader);VAR i: INTEGER; ch: CHAR; w: Word;H: Table;BEGINNEW(H); (* v– *)FOR i := 0 TO N–1 DO H[i].key[0] := " " END;line := 0;Texts.WriteInt(W, 0, 6); Texts.Write(W, TAB); Texts.Read(R, ch);WHILE R.eot DOIF ch = 0DX THEN (* *) Texts.WriteLn(W);INC(line); Texts.WriteInt(W, line, 6); Texts.Write(W, 9X); Texts.Read(R, ch)ELSIF ("A" <= ch) & (ch <= "Z") OR ("a" <= ch) & (ch <= "z") THENi := 0;REPEATIF i < WordLen–1 THEN w[i] := ch; INC(i) END;Texts.Write(W, ch); Texts.Read(R, ch)UNTIL (i = WordLen–1) OR (("A" <= ch) & (ch <= "Z")) & 261(("a" <= ch) & (ch <= "z")) & (("0" <= ch) & (ch <= "9"));w[i] := 0X; (* *)search(H, w)ELSE Texts.Write(W, ch); Texts.Read(R, ch)END;Texts.WriteLn(W); Texts.WriteLn(W); Tabulate(H)ENDEND CrossRef5.4. Анализ хэшированияПроизводительность вставки и поиска в методе хэширования для худшего случая,очевидно, ужасная. Ведь нельзя исключать, что аргумент поиска таков, что все пробы пройдут в точности по занятым позициям, ни разу не попав в нужные (или свободные). Нужно иметь большое доверие законам теории вероятности, чтобы применять технику хэширования. Здесь нужна уверенность в том, что в среднем число проб мало. Приводимые ниже вероятностные аргументы показывают, что это число не просто мало, а очень мало.Снова предположим, что все возможные значения ключей равновероятны и что хэш%функция H распределяет их равномерно по диапазону индексов таблицы.Еще предположим, что некоторый ключ вставляется в таблицу размера N, уже со%держащую k элементов. Тогда вероятность попадания в свободную позицию с первого раза равна (N–k)/N. Этой же величине равна вероятность p1 того, что будет достаточно одного сравнения. Вероятность того, что понадобится в точно%сти еще одна проба, равна вероятности коллизии на первой попытке, умноженной на вероятность попасть в свободную позицию на второй. В общем случае получа%ем вероятность pi вставки, требующей в точности i проб:p1= (N–k)/Np2= (k/N) × (N–k)/(N–1)p3= (k/N) × (k–1)/(N–1) × (N–k)/(N–2)………p i= (k/N) × (k–1)/(N–1) × (k–2)/(N–2) × … × (N–k)/(N–(i–1))Поэтому среднее число E проб, необходимых для вставки k+1%го ключа, равноEk+1= SSSSSi: 1 ≤ i ≤ k+1 : i × p i= 1 × (N–k)/N + 2 × (k/N) × (N–k)/(N–1) + ...+ (k+1) * (k/N) × (k–1)/(N–1) × (k–2)/(N–2) × … × 1/(N–(k–1))= (N+1) / (N–(k–1))Поскольку число проб для вставки элемента совпадает с числом проб для его поиска, этот результат можно использовать для вычисления среднего числа Eпроб, необходимых для доступа к случайному ключу в таблице. Пусть снова раз%мер таблицы обозначен как N, и пусть m – число ключей уже в таблице. ТогдаE = (SSSSSk: 1 ≤ k ≤ m : Ek) / m= (N+1) × (SSSSSk: 1 ≤ k ≤ m : 1/(N–k+2))/m= (N+1) × (HN+1 – HN–m+1)Анализ хэширования Хэширование262где H – гармоническая функция. H можно аппроксимировать как HN = ln(N) + g,где g – постоянная Эйлера. Далее, если ввести обозначение a для отношения m/(N+1), то получаемE = (ln(N+1) – ln(N–m+1))/a = ln((N+1)/(N–m+1))/a = –ln(1–a)/aВеличина a примерно равна отношению занятых и сво%бодных позиций; это отношение называется коэффициентом заполнения (load factor); a = 0 соответствует пустой таблице, a = N/(N+1) ≈ 1 – полной. Среднее число E проб для поиска или вставки случайного ключа дано в табл. 5.1как функция коэффициента заполнения.Числа получаются удивительные, и они объясняют ис%ключительно высокую производительность метода преоб%разования ключей. Даже если таблица заполнена на 90%, в среднем нужно только 2,56 пробы, чтобы найти искомый ключ или свободную позицию. Особо подчеркнем, что это число не зависит от абсолютного числа ключей, а только от коэффициента заполнения.Приведенный анализ предполагает, что применяемый метод разрешения коллизий равномерно рассеивает ключи по оставшимся пози%циям. Методы, используемые на практике, дают несколько худшую производи%тельность. Детальный анализ метода линейных проб дает следующий результат для среднего числа проб:E = (1 – a/2) / (1 – a)Некоторые численные значения E(a) приведены в табл. 5.2 [5.4].Результаты даже для простейшего способа разрешения коллизий настолько хороши, что есть соблазн рассматривать хэширование как панацею на все случаи жизни. Тем более что его производительность превышает даже самые изощрен%ные из обсуждавшихся методов с использованием деревьев, по крайней мере с точки зрения числа сравнений, необходимых для поиска и вставки. Но именно поэтому важно явно указать некоторые недостатки хэширования, даже если они очевидны при непредвзятом анализе.Разумеется, серьезным недостатком по сравнению с методами с динамическим размещением являются фиксированный размер таблицы и невозможность изме%нять его в соответствии с текущей необходимостью.Поэтому обязательно нужна достаточно хорошая ап%риорная оценка числа обрабатываемых элементов дан%ных, если неприемлемы плохое использование памяти или низкая производительность (или переполнение таблицы). Даже если число элементов известно точ%но, – что бывает крайне редко, – стремление к хорошей производительности заставляет выбирать таблицу не%много большего размера (скажем, на 10%).Второй серьезный недостаток методов «рассеянно%го хранения» становится очевидным, если ключи нуж%Таблица 5.1.Таблица 5.1.Таблица 5.1.Таблица 5.1.Таблица 5.1. Среднее число проб E как функция коэффици:ента заполнения aaE0.1 1.05 0.25 1.15 0.5 1.39 0.75 1.85 0.9 2.56 0.95 3.15 0.99 4.66Таблица 5.2.Таблица 5.2.Таблица 5.2.Таблица 5.2.Таблица 5.2. Среднее число проб для метода линейных проб aE0.1 1.06 0.25 1.17 0.5 1.50 0.75 2.50 0.9 5.50 0.95 10.50 263но не только вставлять и искать, но и удалять. Удаление элементов в хэш%табли%це – чрезвычайно громоздкая операция, если только не использовать прямое свя%зывание в отдельной области переполнения. Поэтому разумно заключить, что древесные способы организации по%прежнему привлекательны и даже предпоч%тительны, если объем данных плохо предсказуем, сильно меняется и даже может уменьшаться.1 ... 14 15 16 17 18 19 20 21 22

Алгоритмы и структуры данных
Новая версия для Оберона + CD
Москва, 2010
Никлаус Вирт
Перевод с английского под редакцией
доктора физмат. наук, Ткачева Ф. В.

УДК 32.973.26018.2
ББК 004.438
В52
Никлаус Вирт
В52
Алгоритмы и структуры данных. Новая версия для Оберона + CD / Пер.
с англ. Ткачев Ф. В. – М.: ДМК Пресс, 2010. – 272 с.: ил.
ISBN 9785940745846
В классическом учебнике тьюринговского лауреата Н.Вирта аккуратно, на тщательно подобранных примерах прорабатываются основные темы алго%
ритмики – сортировка и поиск, рекурсия, динамические структуры данных.
Перевод на русский язык выполнен заново, все рассуждения и програм%
мы проверены и исправлены, часть примеров по согласованию с автором переработана с целью максимального прояснения их логики (в том числе за счет использования цикла Дейкстры). Нотацией примеров теперь служит
Оберон/Компонентный Паскаль – наиболее совершенный потомок старого
Паскаля по прямой линии.
Все программы проверены и работают в популярном варианте Оберона –
системе Блэкбокс, и доступны в исходниках на прилагаемом CD вместе с самой системой и дополнительными материалами.
Большая часть материала книги составляет необходимый минимум знаний по алгоритмике не только для программистов%профессионалов, но и любых других специалистов, активно использующих программирование в работе.
Книга может быть использована как учебное пособие при обучении буду%
щих программистов, начиная со старшеклассников в профильном обуче%
нии, а также подходит для систематического самообразования.
Содержание компактдиска:
Базовая конфигурация системы Блэкбокс с коллекцией модулей, реализующих программы из книги.
Базовые инструкции по работе в системе Блэкбокс.
Полный перевод документации системы Блэкбокс на русский язык.
Конфигурация системы Блэкбокс для использования во вводных курсах програм%
мирования в университетах.
Конфигурация системы Блэкбокс для использования в школах (полная русифика%
ция меню, сообщений компилятора, с возможностью использования ключевых слов на русском и других национальных языках).
Доклады участников проекта Информатика%21 по опыту использования системы
Блэкбокс в обучении программированию.
Оригинальные дистрибутивы системы Блэкбокс 1.5 (основной рабочий) и 1.6rc6.
Инструкции по работе в Блэкбоксе под Linux/Wine.
Дистрибутив оптимизирующего компилятора XDS Oberon (версии Linux и MS
Windows).
OberonScript – аналог JavaScript для использования в Web%приложениях.
ISBN 0%13%022005%9 (анг.)
© N. Wirth, 1985 (Oberon version: August 2004).
© Перевод на русский язык, исправления и изменения, Ф. В. Ткачев, 2010.
ISBN 978%5%94074%584%6
© Оформление, издание, ДМК Пресс, 2010

Содержание
О новой версии классического учебника
Никлауса Вирта
....................................................................... 5
Предисловие
.......................................................................... 11
Предисловие к изданию 1985 года
............................. 15
Нотация
..................................................................................... 16
Глава 1. Фундаментальные структуры данных
..... 11 1.1. Введение .............................................................................. 18 1.2. Понятие типа данных ............................................................ 20 1.3. Стандартные примитивные типы .......................................... 22 1.4. Массивы ............................................................................... 26 1.5. Записи .................................................................................. 29 1.6. Представление массивов, записей и множеств .................... 31 1.7. Файлы или последовательности ........................................... 35 1.8. Поиск .................................................................................... 49 1.9. Поиск образца в тексте (string search) .................................. 54
Упражнения.................................................................................. 65
Литература .................................................................................. 67
Глава 2. Сортировка
........................................................... 69 2.1. Введение .............................................................................. 70 2.2. Сортировка массивов ........................................................... 72 2.3. Эффективные методы сортировки ....................................... 81 2.4. Сортировка последовательностей ....................................... 97
Упражнения................................................................................ 128
Литература ................................................................................ 130
Глава 3. Рекурсивные алгоритмы
.............................. 131 3.1. Введение ............................................................................ 132 3.2. Когда не следует использовать рекурсию .......................... 134 3.3. Два примера рекурсивных программ ................................. 137 3.4. Алгоритмы с возвратом ...................................................... 143 3.5. Задача о восьми ферзях ..................................................... 149

Содержание
4 3.6. Задача о стабильных браках ............................................... 154 3.7. Задача оптимального выбора ............................................. 160
Упражнения................................................................................ 164
Литература ................................................................................ 166
Глава 4. Динамические структуры данных
........... 167 4.1. Рекурсивные типы данных .................................................. 168 4.2. Указатели ........................................................................... 170 4.3. Линейные списки ................................................................ 175 4.4. Деревья .............................................................................. 191 4.5. Сбалансированные деревья ............................................... 210 4.6. Оптимальные деревья поиска ............................................. 220 4.7. Б<деревья (BУпражнения................................................................................ 250
Литература ................................................................................ 254
Глава 5. Хэширование
..................................................... 255 5.1. Введение ............................................................................ 256 5.2. Выбор хэш<функции ........................................................... 257 5.3. Разрешение коллизий ........................................................ 257 5.4. Анализ хэширования .......................................................... 261
Упражнения................................................................................ 263
Литература ................................................................................ 264
Приложение A. Множество символов ASCII
.......... 265
Приложение B. Синтаксис Оберона
......................... 266
Приложение C. Цикл Дейкстры
................................... 269

О новой версии
классического учебника
Никлауса Вирта
Новая версия учебника Н. Вирта «Алгоритмы и структуры данных» отличается от английского прототипа [1] сильнее, чем просто исправлением многочисленных опечаток и огрехов, накопившихся в процессе тридцатилетней эволюции книги.
Объясняется это целями автора и переводчика при работе над книгой в контексте проекта «Информатика%21» [2], который, опираясь на обширный совокупный опыт ряда высококвалифицированных специалистов (см. списки консультантов и участников на сайте проекта [2]), ставит задачу создания единой системы ввод%
ных курсов информатики и программирования, охватывающей учащихся пример%
но от 5%го класса общей средней школы по 3%й курс университета. Такая система должна иметь образцом и дополнять уникальную российскую систему матема%
тического образования. Это предполагает наличие стержня общих курсов, состав%
ляющих единство без внутренних технологических барьеров (которые приводят,
среди прочего, к недопустимым потерям дефицитного учебного времени) и лишь варьирующихся в зависимости от специализации, вместе с надстройкой из профессионально ориентированных курсов, опирающихся на этот стержень в от%
ношении базовых знаний учащихся. Такая система подразумевает наличие каче%
ственных учебников (первым из которых имеет шанс стать данная книга),
«говорящих» на общем образцовом языке программирования. Естественный кан%
дидат на роль такого общего языка – Оберон/Компонентный Паскаль. Подроб%
ней об Обероне речь пойдет ниже, здесь только скажем, что Паскаль (использо%
ванный в первом издании данной книги 1975 г.), Модулу%2 (использованную во втором издании, переведенном на русский язык в 1989 г. [3]) и Оберон (использо%
ванный в данной версии) логично рассматривать соответственно как альфа%, бета%
и окончательную версию одного и того же языка. Использование Оберона – самое очевидное отличие данной версии книги от предыдущего издания.
В контекст идеи о единой системе вводных курсов вписывается и узкая задача,
решавшаяся новой версией учебника, – дать небольшое продуманное пособие, в котором аккуратно, но не топя читателя в болоте второстепенных деталей, прора%
батывались бы традиционные темы классической алгоритмики, для полного обсуждения которых нет времени в спецкурсе, читаемом переводчиком с 2001 г.
на физфаке МГУ в попытке обеспечить хотя бы минимум культуры программиро%
вания у будущих аспирантов. Здесь требуется «отлаженный» текст, пригодный для самостоятельной работы студентов. С точки зрения содержания, лучшим кандидатом на эту роль оказался прототип [1].

О новой версии классического учебника Никлауса Вирта
6
Что двойное переделывание программ и рассуждений в тексте (с Паскаля на
Модулу%2 и затем на Оберон) не прошло безнаказанно, само по себе неудиви%
тельно. Однако затруднения, возникшие при верификации программ и текста,
хотя и были преодолены, все же показались чрезмерными. Поэтому, и ввиду учеб%
ного назначения книги, встал ребром вопрос о необходимости доработки примеров.
Предложения переводчика были одобрены автором на совместной рабочей сессии в апреле сего года и реализованы непосредственно в данном переводе (при первой возможности соответствующие изменения будут внесены и в прототип [1]).
Во%первых, алгоритмы поиска образца в тексте переписаны в терминах цикла
Дейкстры (многоветочный while
[4]). Эта фундаментальная и мощная управля%
ющая структура поразительным образом до сих пор не представлена в распро%
страненных языках программирования, поэтому ей посвящено новое приложение
C. Раздел 1.9, в который теперь выделены эти алгоритмы, будет неплохой иллю%
страцией реального применения цикла Дейкстры. Вторая группа заметно изме%
ненных программ – алгоритмы с возвратом в главе 3, в которых теперь экспли%
цировано применение линейного поиска и, благодаря этому, тривиализована верификация. Такое прояснение рекурсивных комбинаторных алгоритмов явля%
ется довольно общим. Обсуждались – но были признаны в данный момент неце%
лесообразными – модификации и некоторых других программ.
Надо заметить, что программистский стиль автора вырабатывался с конца
1950%х гг., когда проблема эффективности программ висела над головами про%
граммистов дамокловым мечом, и за несколько лет до того, как Дейкстра опубли%
ковал систематический метод построения программ [4]. В старых версиях книги заметна рефлекторная склонность к оптимизации до полного прояснения логики программ, что затрудняло эффективное применение формальной техники. Это легко объяснить: Н. Вирт осваивал только еще формирующиеся систематические методы, непосредственно участвуя в процессе создания программирования как академической дисциплины, версия за версией улучшая свои учебники.
Но и через четверть века после последней существенной переделки учебника автором аналогичная склонность к преждевременной оптимизации при не просто не вполне уверенной, а напрочь отсутствующей формальной технике – и, как следствие, запутанные циклы, – характерные черты стиля «широких програм%
мистских масс»! В профессиональных интернет%форумах до сих пор можно найти позорные дискуссии о том, нужно ли учиться писать циклы по Дейкстре, – и это в лучшем случае. Если же вообразить себе весь окружающий нас непрерывно рас%
тущий массив софта, от которого наша жизнь зависит все больше, то впору впасть в депрессию: Quo usque tandem, Catilina? – Сколько еще нужно десятилетий, что%
бы система образования вышла, наконец, на уровень, давным%давно достигнутый наукой? Во всяком случае, ясно, что едва ли не главная причина проблемы – хаос,
царящий в системе ИТ%образования, тормозящий создание и распространение качественных методик и поддерживаемый, среди прочего, корыстными интереса%
ми «монстров» индустрии.
Здесь уместно сказать о языке Оберон/Компонентный Паскаль, пропаганди%
руемом в качестве общей платформы для предполагаемой единой системы курсов

О новой версии классического учебника Никлауса Вирта
7
программирования. Оберон – последний большой проект Никлауса Вирта, выда%
ющегося инженера, ученого и педагога, вместе с Бэкусом, А. Ершовым, Дейкст%
рой, Хоором и другими пионерами компьютерной информатики превратившего программирование в систематическую дисциплину и лучше всего известного со%
зданием серии все более совершенных языков программирования – Паскаля
(1970), Модулы%2 (1980) и наконец Оберона (1988, 2007). В этих языках отража%
лось все более полное понимание проблематики эффективного программирова%
ния. Языки эти сохраняют идейную и стилевую преемственность, и коммерсант,
озабоченный сохранением доли рынка, не назвал бы их по%разному (ср. зоопарк бейсиков). Чтобы подчеркнуть эту преемственность, самому популярному диа%
лекту Оберона было возвращено законное фамильное имя – Компонентный Пас%
каль.
Оберон/Компонентный Паскаль унаследовал лучшие черты старого доброго
Паскаля и добавил к ним промышленный опыт Модулы%2 (на которой програм%
мируются, например, российские спутники связи [5]), а также выверенный мини%
мум средств объектно%ориентированного программирования. Принципальное до%
стижение – удалось наконец добиться герметичности системы типов (теперь ее нельзя обойти средствами языка даже при работе с указателями). Это обеспечило возможность автоматического управления памятью (сбора мусора; до Оберона сбор мусора оставался прерогативой динамических языков – функциональных,
скриптовых и т. п.) В результате диапазон эффективного применения Оберона,
похоже, шире, чем у любого другого языка: это и вычислительные приложения, и системы управления любого масштаба (от беспилотников весом в 1 кг до гранди%
озных каскадов ГЭС), и, например, задачи символической алгебры с предельно динамичными структурами данных.
Особо следует остановиться на минимализме Оберона. Традиционно разра%
ботчики сосредоточиваются на том, чтобы снабдить свои языки, программы, биб%
лиотеки «богатым набором средств» – ведь так легче привлечь клиента, надеюще%
гося побыстрее найти готовое решение для своих прикладных нужд. Погоня за
«богатым набором средств» оборачивается ущербом качеству и надежности сис%
темы. Вместе с коммерческими соображениями это приводит к тому, что полу%
чается большая закрытая сложная система с вроде бы богатым набором средств,
но хромающей надежностью и ограниченной расширяемостью, так что если поль%
зователь сталкивается с нестандартной ситуацией в своих приложениях (что слу%
чается сплошь и рядом – ведь разнообразие реального мира превосходит любое воображение писателей библиотек), то он оказывается в тупике.
Н. Вирт еще со времен Паскаля, созданного в пику фантазийному Алголу%68
[6], пошел другим путем. Его гамбит заключался в том, чтобы, отказавшись от включения в язык максимума средств на все случаи жизни, тщательнейшим обра%
зом выделить минимум реально ключевых средств, – обязательно включив в этот минимум все, что нужно для безболезненной, неограниченной расширяемости программных систем, – и добиться высоконадежной реализации такого ядра.
Этот замысел был с блеском реализован Н. Виртом и его соратником Ю. Гуткнех%
том в проекте Оберон [7]. Минимализм и уникальная надежность Оберона

О новой версии классического учебника Никлауса Вирта
8
заставляют вспомнить автомат Калашникова. При этом вся мощь Оберона оказы%
вается открытой даже программистам%непрофессионалам – физикам, инженерам,
лингвистам.., занятым программированием изрядную долю своего рабочего времени.
Для преподавателя важно, что в Обероне достигнуты ортогональность и сво%
бодная комбинируемость языковых средств, смысловая прозрачность, а также беспрецедентно малый для столь мощного языка размер (см. полное описание синтаксиса в приложении B, а также обсуждение в [8]). В этом отношении Оберон побеждает за явным преимуществом традиционные промышленные языки, пре%
словутая избыточная сложность которых оказывается источником своего рода ренты, взимаемой с остального мира. Оберон скромно уходит в тень при рассмо%
трении любой языково%неспецифичной темы – от введения в алгоритмику до принципов компиляции и программной архитектуры. А после постановки базо%
вой техники программирования на Обероне изучение промышленных языков за%
частую сводится к изучению способов обходить дефекты их дизайна. Если уже старый Паскаль оказался настолько удачной платформой для обучения програм%
мированию, что принес своему автору высшую почесть в компьютерной инфор%
матике – премию им. Тьюринга, то понятно, что буквально вылизанный Оберон/
Компонентный Паскаль называют уже «практически идеальной» платформой для обучения программированию.
Имея в виду исключительные педагогические достоинства Оберона, для всех примеров программ, приведенные в книге, обеспечена воспроизводимость в сис%
теме программирования для Компонентного Паскаля, известной как Блэкбокс
(BlackBox Component Builder [9]). Это пулярный вариант Оберона, созданный для работы в распространенных операционных системах. Конфигурации Блэк%
бокса для использования в школе и университете доступны на сайте проекта «Ин%
форматика%21» [2]. Открытый, бесплатный и безупречно современный Блэкбокс оказывается естественной заменой устаревшему Турбо Паскалю – заменой тем более привлекательной, что, несмотря на минимализм и благодаря автоматиче%
скому управлению памятью, это более мощный инструмент, чем промышленные системы программирования на диалектах старого Паскаля. Краткое описание возможностей Блэкбокса с точки зрения использования в школьных курсах мож%
но найти в статье [10].
Важное приложение к книге – полный комплект программ, представленных в тексте учебника, в виде, готовом к выполнению. Программы оформлены в отдель%
ных модулях вместе с необходимыми вспомогательными процедурами, и все та%
кие модули собраны в папке
ADru/Mod/
, которая должна лежать внутри основной папки Блэкбокса (следует иметь в виду, что файлы с расширением .odc должны читаться из Блэкбокса). Читатель без труда разберется с компиляцией и запуском программ по комментариям в модулях, читая модули в том порядке, в каком они встречаются в тексте книги (или в лексикографическом порядке имен файлов).
В тексте книги в начальных строках каждого законченного программного приме%
ра справа указано имя соответствующего модуля. Например, комментарий
(ADruS18_)
означает, что данная программа содержится в модуле

О новой версии классического учебника Никлауса Вирта
9
ADruS18_
, который в соответствии с правилами Блэкбокса хранится в фай%
ле
ADru/Mod/S18_.odc
. При этом речь идет о программе из раздела 1.8,
а необязательный суффикс "_"
служит удобству ориентации. Вся папка
ADru в составе Блэкбокса имеется на диске, если диск приложен к книге, либо может быть скачана с адреса [11].
Наконец, несколько слов о собственно переводе. Старый перевод [3] был вы%
полнен, что называется, из общих соображений. Но совсем другое дело – иметь в виду конкретных студентов, не обязательно будущих профессиональных программистов, пытающихся за минимальное время овладеть основами програм%
мирования. Поэтому в новом переводе были предприняты особые усилия, чтобы избежать размывания смысла из%за неточностей, неизбежно вкрадывающихся при неполном понимании переводчиком оригинала (ср. примечание на с. 110
в главе о сортировках в [3], где выражена надежда, что «сам читатель разберется,
что хотел сказать автор»). Например, при более%менее прямолинейной пофразо%
вой интерпретации малейшая неточность способна развалить смысл лаконичного текста Вирта из%за того, например, что после перевода могут перестать быть одно%
коренными слова, благодаря которым только и обеспечивалась смысловая связь между предложениями в оригинале. Поэтому добиться полного сохранения смыс%
ла при переводе оказалось проще, выполнив его с нуля.
В отношении терминологии переводам специалистов было отдано должное.
Вслед за Д. Б. Подшиваловым [3] мы используем прилагательные «массивовый»,
«последовательностный» и «записевый». Решающий довод в пользу таких прила%
гательных – они естественно вписываются в грамматическую систему русского языка, чем обеспечивается необходимая гибкость выражения.
Однако даже в отношении терминологии переводы по компьютерной тематике часто демонстрируют неполное понимание существенных деталей английской грамматики. Например, при использовании существительного в качестве опреде%
ления в препозиции (что, кстати, не эквивалентно русской конструкции, выража%
емой родительным падежом) множественное число может нейтрализоваться, и при переводе на русский его иногда нужно восстанавливать. Так, path length дол%
жно переводиться не как «длина пути», а как «длина путей», что, между прочим,
прямо соответствует математическому определению и ощутимо помогает пони%
мать рассуждения. Optimal search tree – «оптимальное дерево поиска», а не «дере%
во оптимального поиска». Advanced sort algorithms – «эффективные алгоритмы сортировки», потому что буквальное значение advanced в данном случае давно нейтрализовано. Переводить на русский язык двумя словами специфичные для стилистики английского языка синонимичные пары вроде «methods and tech%
niques» обычно неразумно. И так далее. Масса подобных неточностей снижает удобочитаемость текста и затемняет и без того непростой смысл оригинала.
Хотя по конкретным стилистическим вопросам копья можно ломать до беско%
нечности, все же хочется надеяться, что предпринятые усилия в основном достиг%
ли цели – не потерять точный смысл английского «исходника» этого выдержав%
шего проверку временем прекрасного учебника.
Троицк, Московская обл., июль 2009*
Ф. В. Ткачев

О новой версии классического учебника Никлауса Вирта
10
[1] Wirth N. Algorithms and Data Structures. Oberon version: 2004 //http://www.
inr.ac.ru/info21/pdf/AD.pdf
[2] Информатика%21: Международный общественный научно%образователь%
ный проект // http://www.inr.ac.ru/info21/
[3] Н. Вирт. Алгоритмы и структуры данных / пер. с англ. Д. Б. Подшивалова. –
М.: Мир, 1989.
[4] Дейкстра Э. Дисциплина программирования. – М.: Мир, 1978.
[5] Koltashev A. A., in: Lecture Notes in Computer Science 2789. – Springer%Verlag,
2003.
[6] Кто такой Никлаус Вирт? // http://www.inr.ac.ru/info21/wirth/wirth.htm
[7] Wirth N. and Gutknecht J. Project Oberon. – Addison%Wesley, 1992.
[8] Свердлов С. В. Языки программирования и методы трансляции. – СПб.:
Питер, 2007.
[9] http://www.oberon.ch/blackbox.html
[10] Ильин А. С. и Попков А. И. Компонентный Паскаль в школьном курсе ин%
форматики // http://inf.1september.ru/article.php?ID=200800100
[11] http://www.inr.ac.ru/info21/ADru/

Предисловие
В последние годы признано, что умение создавать программы для вычислитель%
ных машин является залогом успеха во многих инженерных проектах и что дис%
циплина программирования может быть объектом научного анализа и допускает систематическое изложение. Программирование из ремесла превратилось в ака%
демическую дисциплину. Первые выдающиеся результаты на этом пути получе%
ны Дейкстрой (E. W. Dijkstra) и Хоором (C. A. R. Hoare). «Заметки по структурно%
му программированию» Дейкстры [1] позволили взглянуть на программирование как на объект научного анализа, бросающий вызов человеческому интеллекту,
а слова структурное программирование дали название «революции» в програм%
мировании. Работа Хоора «Аксиоматические основы программирования» [2]
продемонстрировала, что программы допускают точный анализ, основанный на математических рассуждениях. И обе статьи убедительно доказывают, что мно%
гих ошибок в программах можно избежать, если программисты будут систе%
матически применять методы и приемы, которые ранее применялись лишь инту%
итивно и часто неосознанно. Эти статьи сосредоточили внимание на построении и анализе программ, или, точнее говоря, на структуре алгоритмов, представленных текстом программы. При этом вполне очевидно, что систематический научный подход к построению программ уместен прежде всего в случае больших, непрос%
тых программ, работающих со сложными наборами данных. Отсюда следует, что методология программирования должна включать в себя все аспекты структури%
рования данных. В конце концов, программы суть конкретные формулировки аб%
страктных алгоритмов, основанные на конкретных представлениях и структурах данных. Выдающийся вклад в наведение порядка в огромном разнообразии тер%
минологии и понятий, относящихся к структурам данных, сделал Хоор в статье
«О структурной организации данных» [3]. В этой работе продемонстрировано,
что нельзя принимать решения о структуре данных без учета того, какие алгорит%
мы применяются к данным, и что, обратно, структура и выбор алгоритмов часто сильно зависят от стуктуры обрабатываемых данных. Короче говоря, задачу пост%
роения программ нельзя отделять от задачи структурирования данных.
Но данная книга начинается главой о структурах данных, и для этого есть две причины. Во%первых, интуитивно ощущается, что данные предшествуют алгорит%
мам: нужно иметь некоторые объекты до того, как можно будет что%то с ними де%
лать. Во%вторых, эта книга предполагает, что читатель знаком с основными поня%
тиями программирования. Однако в соответствии с разумной традицией вводные курсы программирования концентрируют внимание на алгоритмах, работающих с относительно простыми структурами данных. Поэтому уместно посвятить ввод%
ную главу структурам данных.
На протяжении всей книги, включая главу 1, мы следуем теории и термино%
логии, развитой Хоором и реализованной в языке программирования Паскаль [4].
Сущность теории – в том, что данные являются прежде всего абстракциями реальных явлений и их предпочтительно формулировать как абстрактные струк%

Предисловие
12
туры безотносительно к их реализации в распространенных языках программиро%
вания. В процессе построения программы представление данных постепенно уточняется – в соответствии с уточнением алгоритма, – чтобы все более и более удовлетворить ограничениям, налагаемым имеющейся системой программи%
рования [5]. Поэтому мы постулируем несколько основных структур данных, на%
зываемых фундаментальными. Очень важно, что это конструкции, которые дос%
таточно легко реализовать на реальных компьютерах, ибо только в этом случае их можно рассматривать как истинные элементарные составляющие реального представления данных, появляющиеся как своего рода молекулы на последнем шаге уточнения описания данных. Это запись, массив (с фиксированным разме%
ром) и множество. Неудивительно, что эти базовые строительные элементы соответствуют математическим понятиям, которые также являются фундамен%
тальными.
Центральный пункт этой теории структур данных – разграничение фундамен
тальных и сложных структур. Первые суть молекулы, – сами построенные из ато%
мов, – из которых строятся вторые. Переменные, принадлежащие одному из таких фундаментальных видов структур, меняют только свое значение, но никогда не ме%
няют ни свое строение, ни множество своих допустимых значений. Как следствие –
размер занимаемой ими области памяти фиксирован. «Сложные» структуры, на%
против, характеризуются изменением во время выполнения программы как своих значений, так и строения. Поэтому для их реализации нужны более изощренные методы. В этой классификации последовательность оказывается гибридом. Конеч%
но, у нее может меняться длина; но такое изменение структуры тривиально. По%
скольку последовательности играют поистине фундаментальную роль практичес%
ки во всех вычислительных системах, их обсуждение включено в главу 1.
Во второй главе речь идет об алгоритмах сортировки. Там представлено не%
сколько разных методов, решающих одну и ту же задачу. Математическое изу%
чение некоторых из них показывает их преимущества и недостатки, а также под%
черкивает важность теоретического анализа при выборе хорошего решения для конкретной задачи. Разделение на методы сортировки массивов и методы сорти%
ровки файлов (их часто называют внутренней и внешней сортировками) демон%
стрирует решающее влияние представления данных на выбор алгоритмов и на их сложность. Теме сортировки уделяется такое внимание потому, что она пред%
ставляет собой идеальную площадку для иллюстрации очень многих принципов программирования и ситуаций, возникающих в большинстве других приложе%
ний. Похоже, что курс программирования можно было бы построить, используя только примеры из темы сортировки.
Другая тема, которую обычно не включают во вводные курсы программиро%
вания, но которая играет важную роль во многих алгоритмических решениях, –
это рекурсия. Поэтому третья глава посвящена рекурсивным алгоритмам. Здесь показывается, что рекурсия есть обобщение понятия цикла (итерации) и что она является важным и мощным понятием программирования. К сожалению, во мно%
гих учебниках программирования она иллюстрируется примерами, для которых было бы достаточно простой итерации. Мы в главе 3, напротив, сосредоточим внимание на нескольких задачах, для которых рекурсия дает наиболее естествен%
ную формулировку решения, тогда как использование итерации привело бы к за%

Предисловие
13
путанным и громоздким программам. Класс алгоритмов с возвратом – отличное применение рекурсии, но самые очевидные кандидаты для применения рекур%
сии – это алгоритмы, работающие с данными, структура которых определена ре%
курсивно. Эти случаи рассматриваются в последних двух главах, для которых,
таким образом, третья закладывает фундамент.
В главе 4 рассматриваются динамические структуры данных, то есть такие,
строение которых меняется во время выполнения программы. Показывается, что рекурсивные структуры данных являются важным подклассом часто использу%
емых динамических структур. Хотя рекурсивные определения возможны и даже естественны в этих случаях, на практике они обычно не используются. Вместо них используют явные ссылочные или указательные переменные. Данная книга тоже следует подобному подходу и отражает современный уровень понимания предме%
та: глава 4 посвящена программированию с указателями, списками, деревьями и содержит примеры с даже еще более сложно организованными данными. Здесь речь идет о том, что обычно (хотя и не совсем правильно) называют обработкой списков. Немало места уделено построению деревьев и, в частности, деревьям по%
иска. Глава заканчивается обсуждением так называемых хэш%таблиц, которые ча%
сто используют вместо деревьев поиска. Это дает возможность сравнить два принципиально различных подхода к решению часто возникающей задачи.
Программирование – это конструирование. Как вообще можно учить изобре%
тательному конструированию? Можно было бы попытаться из анализа многих примеров выделить элементарные композиционные принципы и представить их систематическим образом. Но программирование имеет дело с задачами огромно%
го разнообразия и часто требует серьезных интеллектуальных усилий. Ошибочно думать, что обучить ему можно, просто дав некий список рецептов. Но тогда в на%
шем арсенале методов обучения остаются только тщательный подбор и изложе%
ние образцовых примеров. Естественно, не следует ожидать, что изучение приме%
ров будет равно полезным для разных людей. При таком подходе многое зависит от самого учащегося, от его прилежания и интуиции. Это особенно справедливо для относительно сложных и длинных примеров программ. Такие примеры включены в книгу не случайно. Длинные программы доминируют в практике программирования, и они гораздо больше подходят для демонстрации тех труд%
но определяемых, но существенных свойств, которые называют стилем и хоро%
шей структурой. Они также должны послужить упражнениями в искусстве чте%
ния программ, которым часто пренебрегают в пользу написания программ. Это главная причина того, почему в качестве примеров используются целиком до%
вольно большие программы. Читатель имеет возможность проследить постепен%
ную эволюцию программы и увидеть ее состояние на разных шагах, так что про%
цесс разработки предстает как пошаговое уточнение деталей. Считаю, что важно показать программу в окончательном виде, уделяя достаточно внимания деталям,
так как в программировании дьявол прячется в деталях. Хотя изложение общей идеи алгоритма и его анализ с математической точки зрения могут быть увлека%
тельными для ученого, по отношению к инженеру%практику ограничиться только этим было бы нечестно. Поэтому я строго придерживался правила давать оконча%
тельные программы на таком языке, на котором они могут быть реально выполне%
ны на компьютере.

Предисловие
14
Разумеется, здесь возникает проблема поиска нотации, которая одновременно позволяла бы выполнить программу на вычислительной машине и в то же время была бы достаточно машинно независимой, чтобы ее можно было включать в по%
добный текст. В этом отношении не удовлетворительны ни широко используемые языки, ни абстрактная нотация. Язык Паскаль представляет собой подходящий компромисс; он был разработан именно для этой цели и поэтому используется на протяжении всей книги. Программы будут понятны программистам, знакомым с другими языками высокого уровня, такими как Алгол 60 или PL/1: смысл нота%
ции Паскаля объясняется в книге по ходу дела. Однако некоторая подготовка все же могла бы быть полезной. Книга «Систематическое программирование» [6]
идеальна в этом отношении, так как она тоже основана на нотации Паскаля. Одна%
ко следует помнить, что настоящая книга не предназначена быть учебником язы%
ка Паскаль; для этой цели есть более подходящие руководства [7].
Данная книга суммирует – и при этом развивает – опыт нескольких курсов программирования, прочитанных в Федеральном политехническом институте
(ETH) в Цюрихе. Многими идеями и мнениями, представленными в этой книге,
я обязан дискуссиям со своими коллегами в ETH. В частности, я хотел бы поблагодарить г%на Г. Сандмайра за внимательное чтение рукописи, а г%жу Хайди
Тайлер и мою жену за тщательную и терпеливую перепечатку текста. Я должен также упомянуть о стимулирующем влиянии заседаний рабочих групп 2.1 и 2.3
ИФИПа, и в особенности многих дискуссий, которые мне посчастливилось иметь с Э. Дейкстрой и Ч. Хоором. Наконец, нужно отметить щедрость ETH, обеспечив%
шего условия и предоставившего вычислительные ресурсы, без которых подго%
товка этого текста была бы невозможной.
Цюрих, август 1975
Н. Вирт
[1]
Dijkstra E. W., in: Dahl O%.J., Dijkstra E. W., Hoare C. A. R. Structured Prog%
ramming. F. Genuys, Ed., New York, Academic Press, 1972. Р. 1–82 (имеется перевод: Дейкстра Э. Заметки по структурному программированию, в кн.:
Дал У., Дейкстра Э., Хоор К. Структурное программирование. – М.: Мир,
1975. С. 7–97).
[2]
Hoare C. A. R. Comm. ACM, 12, No. 10 (1969), 576–83.
[3]
Hoare C. A. R., in Structured Programming [1]. Р. 83%174 (имеется перевод:
Хоор К. О структурной организации данных, в кн. [1]. С. 98–197).
[4]
Wirth N. The Programming Language Pascal. Acta Informatica, 1, No. 1 (1971),
35–63.
[5]
Wirth N. Program Development by Stepwise Refinement. Comm. ACM, 14, No. 4
(1971), 221–27.
[6]
Wirth N. Systematic Programming. Englewood Cliffs, N. J. Prentice%Hall, Inc.,
1973 (имеется перевод: Вирт Н. Систематическое программирование. Вве%
дение. – М.: Мир, 1977).
[7]
Jensen K. and Wirth N. PASCAL%User Manual and Report. Berlin, Heidelberg,
New York; Springer%Verlag, 1974 (имеется перевод: Йенсен К., Вирт Н. Пас%
каль. Руководство для пользователя и описание языка. – М.: Финансы и ста%
тистика, 1988).

Предисловие
к изданию 1985 года
В этом новом издании сделано много улучшений в деталях, а также несколько бо%
лее серьезных модификаций. Все они мотивированы опытом, приобретенным за десять лет после первого издания. Однако основное содержание и стиль текста не изменились. Кратко перечислим важнейшие изменения.
Главное изменение, повлиявшее на весь текст, касается языка программирова%
ния, использованного для записи алгоритмов. Паскаль был заменен на Модулу%2.
Хотя это изменение не оказывает серьезного влияния на представление алгорит%
мов, выбор оправдан большей простотой и элегантностью синтаксиса Модулы%2,
что часто приводит к большей ясности представления структуры алгоритма. Кро%
ме того, было сочтено полезным использовать нотацию, которая приобретает по%
пулярность в довольно широком сообществе по той причине, что она хорошо под%
ходит для разработки больших программных систем. Тем не менее тот очевидный факт, что Паскаль является предшественником Модулы, облегчает переход. Для удобства читателя синтаксис Модулы суммирован в приложении.
Как прямое следствие замены языка программирования был переписан раз%
дел 1.11 о последовательной файловой структуре. В Модуле%2 нет встроенного файлового типа. В пересмотренном разделе 1.11 понятие последовательности как структуры данных представлено в более общем виде, и там также вводится набор программных модулей, которые явно реализуют идею последовательности конк%
ретно в Модуле%2.
Последняя часть главы 1 является новой. Она посвящена теме поиска и, начи%
ная с линейного и двоичного поиска, подводит к некоторым недавно изобретен%
ным быстрым алгоритмам поиска строк. В этом разделе подчеркивается важность проверок промежуточных состояний (assertions) и инвариантов цикла для дока%
зательства корректности представляемых алгоритмов.
Новый раздел о приоритетных деревьях поиска завершает главу, посвященную динамическим структурам данных. Эта разновидность деревьев была неизвестна во время выхода первого издания. Такие деревья допускают экономное представление и позволяют выполнять быстрый поиск по множествам точек на плоскости.
Целиком исключена вся пятая глава первого издания. Это сделано потому, что тема построения компиляторов стоит несколько в стороне от остальных глав и заслуживает более подробного обсуждения в отдельной книге.
Наконец, появление нового издания отражает прогресс, глубоко повлиявший на издательское дело в последние десять лет: применение компьютеров и изощ%
ренных алгоритмов для подготовки и автоматического форматирования докумен%
тов. Эта книга была набрана и сформатирована автором с помощью компьютера
Lilith и редактора документов Lara. Без этих инструментов книга не только стала бы дороже, но, несомненно, даже еще не была бы закончена.
Пало Альто, март 1985 г.
Н. Вирт

Нотация
В книге используются следующие обозначения, взятые из работ Дейкстры.
В логических выражениях литера
&
обозначает конъюнкцию и читается как
«и». Литера

обозначает отрицание и читается как «не». Комбинация литер or обозначает дизъюнкцию и читается как «или». Литеры
A
A
A
A
A
и
E
E
E
E
E
, набранные жирным шрифтом, обозначают кванторы общности и существования. Нижеследующие формулы определяют смысл нотации в левой части через выражение в правой.
Интерпретация символа «...» в правых частях оставлена интуиции читателя.
A
A
A
A
Ai: m
≤ i < n : P
i
P
m
& P
m+1
& ... & P
n–1
Здесь
P
i
– некоторые предикаты, а формула утверждает, что выполняются все
P
i для значений индекса i
из диапазона от m
до n
, но не включая само n
E
E
E
E
Ei: m
≤ i < n : P
i
P
m or P
m+1
or ... or P
n–1
Здесь
P
i
– некоторые предикаты, а формула утверждает, что выполняются некоторые из
P
i для каких%то значений индекса i
из диапазона от m
до n
, но не включая само n
S
S
S
S
Si: m
≤ i < n : x i
= x m
+ x m+1
+ ... + x n–1
MIN i: m
≤
i
<
n : x i
= минимальное среди значений
(x m
, ... , x n–1
)
MAX i: m
≤
i
<
n : x i
= максимальное среди значений
(x m
, ... , x n–1
)

1 2 3 4 5 6 7 8 9 ... 22

Глава 1
Фундаментальные
структуры данных
1.1. Введение ............................ 18 1.2. Понятие типа данных .......... 20 1.3. Стандартные примитивные типы ..................... 22 1.4. Массивы ............................. 26 1.5. Записи ............................... 29 1.6. Представление массивов,
записей и множеств ................... 31 1.7. Файлы или последовательности .................. 35 1.8. Поиск ................................. 49 1.9. Поиск образца в тексте
(string search) ............................. 54
Упражнения ............................... 65
Литература ................................ 67

Фундаментальные структуры данных
18
1.1. Введение
Современные цифровые компьютеры были изобретены для выполнения сложных и длинных вычислений. Однако в большинстве приложений предоставляемая та%
ким устройством возможность хранить и обеспечивать доступ к большим масси%
вам информации играет основную роль и рассматривается как его главная характеристика, а возможность призводить вычисления, то есть выполнять арифметические действия, во многих случаях стала почти несущественной.
В таких приложениях большой массив обрабатываемой информации является в определенном смысле абстрактным представлением некоторой части реального мира. Информация, доступная компьютеру, представляет собой специально подобранный набор данных, относящихся к решаемой задаче, причем предпо%
лагается, что этот набор достаточен для получения нужных результатов. Данные являются абстрактным представлением реальности в том смысле, что некоторые свойства реальных объектов игнорируются, так как они несущественны для этой задачи. Поэтому абстракция – это еще и упрощение реальности.
В качестве примера можно взять файл с данными о служащих некоторой ком%
пании. Каждый служащий (абстрактно) представлен в этом файле набором дан%
ных, который нужен либо для руководства компании, либо для бухгалтерских расчетов. Такой набор может содержать некоторую идентификацию служащего,
например имя и зарплату. Но в нем почти наверняка не будет несущественной информации о цвете волос, весе или росте.
Решая задачу с использованием компьютера или без него, необходимо выбрать абстрактное представление реальности, то есть определить набор данных, кото%
рый будет представлять реальную ситуацию. Этот выбор можно сделать, руко%
водствуясь решаемой задачей. Затем нужно определиться с представлением ин%
формации. Здесь выбор определяется средствами вычислительной установки.
В большинстве случаев эти два шага не могут быть полностью разделены.
Выбор представления данных часто довольно сложен и не полностью определя%
ется имеющимися вычислительными средствами. Делать такой выбор всегда нужно с учетом операций, которые нужно выполнять с данными. Хороший пример – пред%
ставление чисел, которые сами суть абстракции свойств некоторых объектов. Если единственное (или основное) действие, которое нужно выполнять, – сложение, то хорошим представлением числа n
может быть n
черточек. Правило сложения при та%
ком представлении – очевидное и очень простое. Римская нотация основана на этом принципе простоты, и правила сложения просты для маленьких чисел. С другой сто%
роны, представление арабскими цифрами требует неочевидных правил сложения
(для маленьких чисел), и их нужно запоминать. Однако ситуация меняется на проти%
воположную, если нужно складывать большие числа или выполнять умножение и деление. Разбиение этих операций на более простые шаги гораздо проще в случае арабской нотации благодаря ее систематической позиционной структуре.
Хорошо известно, что компьютеры используют внутреннее представление,
основанное на двоичных цифрах (битах). Это представление непригодно для использования людьми, так как здесь обычно приходится иметь дело с большим

19
числом цифр, но весьма удобно для электронных схем, так как два значения 0 и 1
можно легко и надежно представить посредством наличия или отсутствия элект%
рических токов, зарядов или магнитных полей.
Из этого примера также видно, что вопрос представления часто требует рассма%
тривать несколько уровней детализации. Например, в задаче представления по%
ложения объекта первое решение может касаться выбора пары чисел в, скажем,
декартовых или полярных координатах. Второе решение может привести к пред%
ставлению с плавающей точкой, где каждое вещественное число x
состоит из пары целых, обозначающих дробную часть f
и показатель e
по некоторому основанию
(например, x = f
×
2
e
). Третье решение, основанное на знании, что данные будут храниться в компьютере, может привести к двоичному позиционному представ%
лению целых чисел. Наконец, последнее решение может состоять в том, чтобы представлять двоичные цифры электрическими зарядами в полупроводниковом устройстве памяти. Очевидно, первое решение в этой цепочке зависит главным образом от решаемой задачи, а дальнейшие все больше зависят от используемого инструмента и применяемых в нем технологий. Вряд ли можно требовать, чтобы программист решал, какое представление чисел использовать или даже какими должны быть характеристики устройства хранения данных. Такие решения низ%
кого уровня можно оставить проектировщикам вычислительного оборудования,
у которых заведомо больше информации о существующих технологиях, чтобы сделать разумный выбор, приемлемый для всех (или почти всех) приложений, где играют роль числа.
В таком контексте выявляется важность языков программирования. Язык программирования представляет абстрактный компьютер, допускающий интер%
претацию в терминах данного языка, что может подразумевать определенный уровень абстракции по сравнению с объектами, используемыми в реальном вычислительном устройстве. Тогда программист, использующий такой язык вы%
сокого уровня, будет освобожден от заботы о представлении чисел (и лишен воз%
можности что%то сделать в этом отношении), если числа являются элементар%
ными объектами в данном языке.
Использование языка, предоставляющего удобный набор базовых абстракций,
общих для большинства задач обработки данных, влияет главным образом на на%
дежность получающихся программ. Легче спроектировать программу, опираясь в рассуждениях на знакомые понятия чисел, множеств, последовательностей и циклов, чем иметь дело с битами, единицами хранения и переходами управления.
Конечно, реальный компьютер представляет любые данные – числа, множества или последовательности – как огромную массу битов. Но программист может за%
быть об этом, если ему не нужно беспокоиться о деталях представления выбран%
ных абстракций и если он может считать, что выбор представления, сделанный компьютером (или компилятором), разумен для решаемых задач.
Чем ближе абстракции к конкретному компьютеру, тем легче сделать выбор представления инженеру или автору компилятора и тем выше вероятность, что единственный выбор будет подходить для всех (или почти всех) мыслимых при%
ложений. Это обстоятельство устанавливает определенные пределы на «высоту»
Введение

Фундаментальные структуры данных
20
используемых абстракций по сравнению с уровнем реального «железа». Напри%
мер, неразумно включать в язык общего назначения геометрические фигуры, так как из%за внутренне присущей им сложности их подходящее представление будет сильно зависеть от действий, выполняемых с ними. Однако природа и частота та%
ких действий неизвестна проектировщику языка программирования общего на%
значения и соответствующего компилятора, и любой выбор проектировщика мо%
жет оказаться плохим для некоторого класса приложений.
Эти соображения определили выбор нотации для описания алгоритмов и соот%
ветствующих данных в настоящей книге. Разумеется, нам хотелось бы использо%
вать знакомые понятия математики, такие как числа, множества, последователь%
ности и т. д., а не машинно зависимые сущности вроде строк битов. Но нам также хотелось бы использовать нотацию, для которой существуют эффективные компиляторы. Неразумно использовать язык, в сильной степени машинно зави%
симый, но также недостаточно и описывать программы в абстрактной нотации,
в которой проблемы представления остаются нерешенными. Язык программи%
рования Паскаль был спроектирован в попытке найти компромисс между этими двумя крайностями, а его наследники Модула%2 и Оберон учитывают опыт,
накопленный за десятилетия [1.3]. Оберон сохраняет базовые понятия Паскаля с некоторыми усовершенствованиями и добавлениями; он используется на протя%
жении этой книги [1.5]. Оберон был успешно реализован для ряда компьютеров,
при этом было продемонстрировано, что его нотация достаточно близка к реально%
му «железу», чтобы выбранные средства и их представления можно было объяс%
нить с полной ясностью. Язык также близок к другим языкам, так что уроки, усво%
енные здесь, могут быть с равным успехом применены и при их использовании.
1.2. Понятие типа данных
В математике переменные обычно классифицируются по некоторым важным ха%
рактеристикам. Проводится четкое различие между вещественными, комплекс%
ными и логическими переменными, или между переменными, представляющими отдельные значения, множества значений, множества множеств, или между фун%
кциями, функционалами, множествами функций и т. д. Такая классификация не менее, если не более, важна в обработке данных. Мы будем придерживаться того принципа, что каждая константа, выражение или функция имеет определенный
тип. В сущности, тип характеризует множество значений, к которому принад%
лежит константа, или которые может принимать переменная или выражение, или которые могут порождаться функцией.
В математических текстах тип переменной обычно можно определить просто по шрифту, без учета контекста; но это невозможно в компьютерных программах.
На вычислительной установке обычно доступен только один шрифт (латинские буквы). Поэтому часто следуют правилу явно вводить соответствующий тип в объявлении константы, переменной или функции, причем такое объявление должно предшествовать использованию этой константы, переменной или функ%
ции. Это правило тем более разумно, что компилятор должен выбрать пред%

21
ставление объекта в памяти компьютера. Очевидно, что объем памяти, отведен%
ной под переменную, должен быть выбран в соответствии с диапазоном значений,
которые может принимать переменная. Если эта информация доступна компиля%
тору, то можно избежать так называемого динамического размещения. Очень час%
то этот пункт оказывается ключевым для эффективной реализации алгоритма.
Сущность понятия типа, как оно используется в данном тексте и реализуется в языке программирования Оберон, выражается в следующих утверждениях [1.2]:
1. Тип данных определяет множество значений, которому принадлежит зна%
чение константы, или в котором принимает значения переменная или выра%
жение, или которому принадлежат значения, порождаемые операцией или функцией.
2. Тип значения, обозначенного константой, переменной или выражением,
может быть выведен из их объявлений и вида выражения без выполнения вычислений.
3. Каждая операция или функция требует аргументов определенных типов и дает результат некоторого, тоже определенного типа. Если операция допус%
кает аргументы нескольких типов (например, + используется для сложения как целых, так и вещественных чисел), то тип результата может быть опре%
делен на основе особых правил языка программирования.
Компилятор может использовать такую информацию о типах для проверки законности различных конструкций. Например, ошибочное присваивание булев%
ского (логического) значения арифметической переменной может быть обнару%
жено без выполнения программы. Подобная избыточность текста программы весьма полезна при ее разработке и может рассматриваться как главное преиму%
щество хороших языков высокого уровня по сравнению с машинным кодом (или кодом символического ассемблера).
Очевидно, в конечном итоге данные будут представлены огромным количест%
вом двоичных цифр независимо от того, была ли написана исходная программа на языке высокого уровня, использующего понятие типа, или на ассемблере, где ти%
пов нет. Для компьютера память представляется однородной массой битов без явной структуры. Но именно абстрактная структура позволяет человеку%програм%
мисту видеть смысл в монотонном пейзаже компьютерной памяти.
Теория, о которой идет речь в данной книге, и язык программирования Оберон дают некоторые способы определения типов данных. В большинстве случаев но%
вый тип данных строится из других типов, уже определенных (назовем их состав
ляющими). Значения такого типа – это обычно агрегаты значений%компонент,
принадлежащих ранее определенным составляющим типам, и такие значения на%
зываются составными,или структурированными. Если используется только один составляющий тип, то естьвсе компоненты принадлежат одному типу, то этот тип называют базовым. Число различных значений типа

называют его мощ
ностью. Мощность позволяет определить объем памяти для представления пере%
менной x
, имеющей тип
T
, что обозначается как x: T
Поскольку составляющие типы, в свою очередь, могут быть составными, то могут выстраиваться целые иерархии структур. Впрочем, очевидно, что наимень%
Понятие типа данных

Смотрите также файлы

Масаты А. Білімні сара жолы бастауыштан басталатынын, бастауышта алан білімні негіз болып аланатынына кз жеткізу. Б.docx

Федеральное государственное бюджетное образовательное учреждение высшего образования Ульяновский государственный педагогический университет им. И. Н. Ульянова.docx

2 Космологией 3 Астрономией 4 Небесной механики Применение общей теории относительности для Вселенной в целом привело к выводу, что Вселенная 1 Нестационарна 2 Бесконечна 3 Конечна 4 Стационарна.docx

Реферат по дисциплине Логика на тему " Уловки в споре ".docx

Нрмобу Сентябрьская сош Исследовательский проект Как появился Храм в п. Сентябрьский Авторы учащиеся 3 класса.docx

Файл: Алгоритмы и структуры данныхНовая версия для Оберона cdмосква, 2010Никлаус ВиртПеревод с английского под редакцией.pdf

Смотрите также файлы

Информация

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

Дополнительно