А. шень Издание шестое, дополненное Москва
 Скачать 1.62 Mb.
|
|
Почему? Как изменится спецификация процедуры? Решение. Спецификацию можно выбрать такой: дано: напечатанное корректно надо: напечатанное корректно и включает вершину i; все вновь напечатанные вершины доступны из i. 130 7. Рекурсия 7.4.4. Где использован тот факт, что граф не имеет циклов? Решение. Мы опустили доказательство конечности глубины рекур- сии. Для каждой вершины рассмотрим её «глубину» | максимальную длину пути по стрелкам, из неё выходящего. Условие отсутствия циклов гарантирует, что эта величина конечна. Из вершины нулевой глубины стрелок не выходит. Глубина конца стрелки по крайней мере на 1 мень- ше, чем глубина начала. При работе процедуры add(i) все рекурсивные вызовы add(j) относятся к вершинам меньшей глубины. Вернёмся к оценке времени работы. Сколько вызовов add(i) воз- можно для какого-то фиксированного i? Прежде всего ясно, что пер- вый из них печатает i, остальные сведутся к проверке того, что i уже напечатано. Ясно также, что вызовы add(i) индуцируются «печата- ющими» (первыми) вызовами add(j) для тех j, из которых в i ведёт ребро. Следовательно, число вызовов add(i) равно числу входящих в i рёбер (стрелок). При этом все вызовы, кроме первого, требуют 𝑂(1) операций, а первый требует времени, пропорционального числу исходя- щих из i стрелок. (Не считая времени, уходящего на выполнение add(j) для концов j выходящих рёбер.) Отсюда видно, что общее время про- порционально числу рёбер (плюс число вершин). Связная компонента графа. Неориентированный граф | набор то- чек (вершин), некоторые из которых соединены линиями (рёбрами). Неориентированный граф можно считать частным случаем ориенти- рованного графа, в котором для каждой стрелки есть обратная. Связной компонентой вершины i называется множество всех тех вершин, в которые можно попасть из i, идя по рёбрам графа. (По- скольку граф неориентированный, отношение «j принадлежит связной компоненте i» является отношением эквивалентности.) 7.4.5. Дан неориентированный граф (для каждой вершины указано число соседей и массив номеров соседей, как в задаче о топологической сортировке). Составьте алгоритм, который по заданному i печатает все вершины связной компоненты i по одному разу (и только их). Чи- сло действий не должно превосходить 𝐶 · (общее число вершин и рёбер в связной компоненте). Решение. Программа в процессе работы будет «закрашивать» неко- торые вершины графа. Незакрашенной частью графа будем называть то, что останется, если выбросить все закрашенные вершины и веду- щие в них рёбра. Процедура add(i) закрашивает связную компоненту i в незакрашенной части графа (и не делает ничего, если вершина i уже закрашена). 7.4. Другие применения рекурсии 131 procedure add (i:1..n); begin if вершина i закрашена then begin ничего делать не надо end else begin закрасить i (напечатать и пометить как закрашенную) для всех j, соседних с i add(j); end; end; end; Докажем, что эта процедура действует правильно (в предположении, что рекурсивные вызовы работают правильно). В самом деле, ниче- го, кроме связной компоненты незакрашенного графа, она закрасить не может. Проверим, что вся она будет закрашена. Пусть k | вер- шина, доступная из вершины i по пути i → j → . . . → k, проходящему только по незакрашенным вершинам. Будем рассматривать только пу- ти, не возвращающиеся снова в i. Из всех таких путей выберем путь с наименьшим j (в порядке просмотра соседей в процедуре). Тогда при рассмотрении предыдущих соседей ни одна из вершин пути j → . . . → k не будет закрашена (иначе j не было бы минимальным) и потому k ока- жется в связной компоненте незакрашенного графа к моменту вызова add(j). Что и требовалось. Чтобы установить конечность глубины рекурсии, заметим, что на каждом уровне рекурсии число незакрашенных вершин уменьшается хотя бы на 1. Оценим число действий. Каждая вершина закрашивается не более одного раза | при первым вызове add(i) с данным i. Все последую- щие вызовы происходят при закрашивании соседей | количество та- ких вызовов не больше числа соседей | и сводятся к проверке того, что вершина i уже закрашена. Первый же вызов состоит в просмо- тре всех соседей и рекурсивных вызовах add(j) для всех них. Таким образом, общее число действий, связанных с вершиной i, не превосхо- дит константы, умноженной на число её соседей. Отсюда и вытекает требуемая оценка. 7.4.6. Решите ту же задачу для ориентированного графа (напе- чатать все вершины, доступные из данной по стрелкам; граф может содержать циклы). Ответ. Годится по существу та же программа (строку «для всех соседей» надо заменить на «для всех вершин, куда ведут стрелки»). 132 7. Рекурсия Следующий вариант задачи о связной компоненте имеет скорее те- оретическое значение (и называется теоремой Сэвича). 7.4.7. Ориентированный граф имеет 2 𝑛 вершин (двоичные слова длины 𝑛) и задан в виде функции есть ребро, которая по двум верши- нам 𝑥 и 𝑦 сообщает, есть ли в графе ребро из 𝑥 в 𝑦. Составьте алгоритм, который для данной пары вершин 𝑢 и 𝑣 определяет, есть ли путь (по рёбрам) из 𝑢 в 𝑣, используя память, ограниченную многочленом от 𝑛. (Время при этом может быть | и будет | очень большим.) [Указание. Используйте рекурсивную процедуру, выясняющую, су- ществует ли путь из 𝑥 в 𝑦 длины не более 2 𝑘 (и вызывающую себя с уменьшенным на единицу значением 𝑘).] Быстрая сортировка Хоара. В заключение приведём рекурсивный алгоритм сортировки массива, который на практике является одним из самых быстрых. Пусть дан массив a[1] . . . a[n]. Рекурсивная про- цедура sort(l,r:integer) сортирует участок массива с индексами из полуинтервала (l, r], то есть a[l+1] . . . a[r], не затрагивая остального массива. procedure sort (l,r: integer); begin if l = r then begin ничего делать не надо - участок пуст end else begin выбрать случайное число s в полуинтервале (l,r] b := a[s] переставить элементы сортируемого участка так, чтобы сначала шли элементы, меньшие b - участок (l,ll] затем элементы, равные b - участок (ll,rr] затем элементы, большие b - участок (rr,r] sort (l,ll); sort (rr,r); end; end; Разделение элементов сортируемого участка на три категории (мень- шие, равные, больше) рассматривалась в главе 1 , с. 36 (это можно сде- лать за время, пропорциональное длине участка). Конечность глубины рекурсии гарантируется тем, что длина сортируемого участка на ка- ждом уровне рекурсии уменьшается хотя бы на 1. 7.4.8. (Для знакомых с основами теории вероятностей). Докажите, что математическое ожидание числа операций при работе этого ал- 7.4. Другие применения рекурсии 133 горитма не превосходит 𝐶𝑛 log 𝑛, причём константа 𝐶 не зависит от сортируемого массива. [Указание. Пусть 𝑇 (𝑛) | максимум математического ожидания чи- сла операций для всех входов длины 𝑛. Из текста процедуры вытекает такое неравенство: 𝑇 (𝑛) 6 𝐶𝑛 + 1 𝑛 ∑︁ 𝑘+𝑙=𝑛−1 (︀ 𝑇 (𝑘) + 𝑇 (𝑙))︀ Первый член соответствует распределению элементов на меньшие, рав- ные и большие. Второй член | это среднее математическое ожидание для всех вариантов случайного выбора. (Строго говоря, поскольку сре- ди элементов могут быть равные, в правой части вместо 𝑇 (𝑘) и 𝑇 (𝑙) должны стоять максимумы 𝑇 (𝑥) по всем 𝑥, не превосходящим 𝑘 или 𝑙, но это не мешает дальнейшим рассуждениям.) Далее индукцией по 𝑛 нуж- но доказывать оценку 𝑇 (𝑛) 6 𝐶 ′ 𝑛 ln 𝑛. При этом для вычисления средне- го значения 𝑥 ln 𝑥 по всем 𝑥 = 1, . . . , 𝑛 − 1 нужно вычислять ∫︀ 𝑛 1 𝑥 ln 𝑥 𝑑𝑥 по частям как ∫︀ ln 𝑥 𝑑(𝑥 2 ). При достаточно большом 𝐶 ′ член 𝐶𝑛 в пра- вой части перевешивается за счёт интеграла ∫︀ 𝑥 2 𝑑 ln 𝑥, и индуктивный шаг проходит.] 7.4.9. Имеется массив из 𝑛 различных целых чисел и число 𝑘. Требу- ется найти 𝑘-е по величине число в этом массиве, сделав не более 𝐶𝑛 дей- ствий, где 𝐶 | некоторая константа, не зависящая от 𝑘 и 𝑛. Замечание. Сортировка позволяет очевидным образом сделать это за 𝐶𝑛 log 𝑛 действий. Очевидный способ: найти наименьший элемент, затем найти второй, затем третий, . . . , 𝑘-й требует порядка 𝑘𝑛 дей- ствий, то есть не годится (константа при 𝑛 зависит от 𝑘). [Указание. Изящный (хотя практически и бесполезный | константы слишком велики) способ сделать это таков: А. Разобьём наш массив на 𝑛/5 групп, в каждой из которых по 5 эле- ментов. Каждую группу упорядочим. Б. Рассмотрим средние элементы всех групп и перепишем их в мас- сив из 𝑛/5 элементов. С помощью рекурсивного вызова найдём средний по величине элемент этого массива. В. Сравним этот элемент со всеми элементами исходного массива: они разделятся на большие его и меньшие его (и один равный ему). Подсчитав количество тех и других, мы узнаем, в какой из этих частей должен находится искомый (𝑘-й) элемент и каков он там по порядку. Г. Применим рекурсивно наш алгоритм к выбранной части. 134 7. Рекурсия Пусть 𝑇 (𝑛) | максимально возможное число действий, если этот способ применять к массивам из не более чем 𝑛 элементов (𝑘 может быть каким угодно). Имеем оценку: 𝑇 (𝑛) 6 𝐶𝑛 + 𝑇 (𝑛/5) + 𝑇 (примерно 0,7𝑛). Последнее слагаемое объясняется так: при разбиении на части каждая часть содержит не менее 0,3𝑛 элементов. В самом деле, если 𝑥 | сред- ний из средних, то примерно половина всех средних меньше 𝑥. А если в пятёрке средний элемент меньше 𝑥, то ещё два заведомо меньше 𝑥. Тем самым по крайней мере 3/5 от половины элементов меньше 𝑥. Теперь по индукции можно доказать оценку 𝑇 (𝑛) 6 𝐶𝑛 (решающую роль при этом играет то обстоятельство, что 1/5 + 0,7 < 1).] 8. КАК ОБОЙТИСЬ БЕЗ РЕКУРСИИ Для универсальных языков программирования (каковым является паскаль) рекурсия не даёт ничего нового: для всякой рекурсивной про- граммы можно написать эквивалентную программу без рекурсии. Мы не будем доказывать этого, а продемонстрируем некоторые приёмы, позволяющие избавиться от рекурсии в конкретных ситуациях. Зачем это нужно? Ответ прагматика мог бы быть таким: во мно- гих компьютерах (в том числе, к сожалению, и в современных, исполь- зующих так называемые RISC-процессоры), рекурсивные программы в несколько раз медленнее соответствующих нерекурсивных программ. Ещё один возможный ответ: в некоторых языках программирования ре- курсивные программы запрещены. А главное, при удалении рекурсии возникают изящные и поучительные конструкции. 8.1. Таблица значений (динамическое программирование) 8.1.1. Следующая рекурсивная процедура вычисляет числа сочета- ний (биномиальные коэффициенты). Напишите эквивалентную нере- курсивную программу. function C(n,k: integer):integer; {n >= 0; 0 <= k <=n} begin if (k = 0) or (k = n) then begin C:=1; end else begin {0 end; end; 136 8. Как обойтись без рекурсии Замечание. 𝐶 𝑘 𝑛 | число 𝑘-элементных подмножеств 𝑛-элементного множества. Соотношение 𝐶 𝑘 𝑛 = 𝐶 𝑘−1 𝑛−1 + 𝐶 𝑘 𝑛−1 получится, если мы фикси- руем некоторый элемент 𝑛-элементного множества и отдельно подсчи- таем 𝑘-элементные подмножества, включающие и не включающие этот элемент. Таблица значений 𝐶 𝑘 𝑛 1 1 1 1 2 1 1 3 3 1 называется треугольником Паскаля (того самого). В нём каждый эле- мент, кроме крайних единиц, равен сумме двух стоящих над ним. Решение. Можно воспользоваться формулой 𝐶 𝑘 𝑛 = 𝑛! 𝑘! (𝑛 − 𝑘)! Мы, однако, не будем этого делать, так как хотим продемонстрировать более общие приёмы устранения рекурсии. Вместо этого составим та- блицу значений функции C(n,k) = 𝐶 𝑘 𝑛 , заполняя её для 𝑛 = 0, 1, 2, . . ., пока не дойдём до интересующего нас элемента. 8.1.2. Что можно сказать о времени работы рекурсивной и нере- курсивной версий в предыдущей задаче? Тот же вопрос о памяти. Решение. Таблица занимает место порядка 𝑛 2 , его можно сократить до 𝑛, если заметить, что для вычисления следующей строки треуголь- ника Паскаля нужна только предыдущая. Время работы остаётся по- рядка 𝑛 2 . Рекурсивная программа требует существенно большего вре- мени: вызов C(n,k) сводится к двум вызовам для C(n-1,...), те | к четырём вызовам для C(n-2,...) и так далее. Таким образом, время оказывается экспоненциальным (порядка 2 𝑛 ). Используемая рекурсив- ной версией память пропорциональна 𝑛 | умножаем глубину рекурсии (𝑛) на количество памяти, используемое одним экземпляром процедуры (константа). Кардинальный выигрыш во времени при переходе от рекурсивной версии к нерекурсивной связан с тем, что в рекурсивном варианте одни и те же вычисления происходят много раз. Например, вызов C(5,3) 8.1. Таблица значений (динамическое программирование) 137 в конечном счёте порождает два вызова C(3,2): C(5,3) ↘ ↘ C(4,2) C(4,3) ↘ ↘ ↘ ↘ C(3,1) C(3,2) C(3,3) Заполняя таблицу, мы каждую клетку заполняем только однажды | отсюда и экономия. Этот приём называется динамическим программи- рованием, и применим в тех случаях, когда объём хранимой в таблице информации оказывается не слишком большим. 8.1.3. Поговорите на ту же тему на примере рекурсивной и (про- стейшей) нерекурсивной программ для вычисления чисел Фибоначчи, заданных соотношением ˘ 1 = ˘ 2 = 1; ˘ 𝑛 = ˘ 𝑛−1 + ˘ 𝑛−2 (𝑛 > 2). 8.1.4. Дан выпуклый 𝑛-угольник (заданный координатами своих вершин в порядке обхода). Его разрезают на треугольники диагоналя- ми, для чего необходимо 𝑛 − 2 диагонали (это можно доказать индукци- ей по 𝑛). Стоимостью разрезания назовём сумму длин всех использован- ных диагоналей. Найдите минимальную стоимость разрезания. Число действий должно быть ограничено некоторым многочленом от 𝑛. (Пере- бор не подходит, так как число вариантов не ограничено многочленом.) Решение. Будем считать, что вершины пронумерованы от 1 до 𝑛 и идут по часовой стрелке. Пусть 𝑘, 𝑙 | номера вершин, причём 𝑙 > 𝑘. Через 𝐴(𝑘, 𝑙) обозначим многоугольник, отрезаемый от нашего хор- дой 𝑘 { 𝑙. (Эта хорда разрезает многоугольник на два, один из которых включает сторону 1 { 𝑛; через 𝐴(𝑘, 𝑙) мы обозначаем другой.) Исходный многоугольник естественно обозначить 𝐴(1, 𝑛). При 𝑙 = 𝑘 + 1 получа- ется «двуугольник» с совпадающими сторонами. q q q q q A A A A q q q q A A A A 1 𝑘 𝑙 𝑛 𝐴(𝑘, 𝑙) 138 8. Как обойтись без рекурсии Через 𝑎(𝑘, 𝑙) обозначим стоимость разрезания многоугольника 𝐴(𝑘, 𝑙) диагоналями на треугольники. Напишем рекуррентную формулу для 𝑎(𝑘, 𝑙). При 𝑙 = 𝑘 + 1 получается двуугольник, и мы полагаем 𝑎(𝑘, 𝑙) = 0. При 𝑙 = 𝑘 + 2 получается треугольник, и в этом случае также 𝑎(𝑘, 𝑙) = 0. Пусть 𝑙 > 𝑘 + 2. q q A A A A q q q q 𝑘 𝑙 𝑖 @ @ @ @ @ @ Хорда 𝑘 { 𝑙 является стороной многоугольника 𝐴(𝑘, 𝑙) и, следовательно, стороной одного из треугольников, на которые он разрезан. Противо- положной вершиной 𝑖 этого треугольника может быть любая из вершин 𝑘 + 1, . . . , 𝑙 − 1, и минимальная стоимость разрезания может быть вы- числена как min{(длина хорды 𝑘 { 𝑖) + (длина хорды 𝑖 { 𝑙) + 𝑎(𝑘, 𝑖) + 𝑎(𝑖, 𝑙)} по всем 𝑖 = 𝑘 + 1, . . . , 𝑙 − 1. При этом надо учесть, что при 𝑞 = 𝑝 + 1 хорда 𝑝 { 𝑞 | не хорда, а сторона, и её длину надо считать равной 0 (по стороне разрез не проводится). Составив таблицу для 𝑎(𝑘, 𝑙) и заполняя её в порядке возрастания числа вершин (равного 𝑙 − 𝑘 + 1), мы получаем программу, использую- щую память порядка 𝑛 2 и время порядка 𝑛 3 (однократное применение рекуррентной формулы требует выбора минимума из не более чем 𝑛 чи- сел). 8.1.5. Матрицей размера 𝑚 × 𝑛 называется прямоугольная таблица из 𝑚 строк и 𝑛 столбцов, заполненная числами. Матрицу размера 𝑚 × 𝑛 можно умножить на матрицу размера 𝑛 × 𝑘 (ширина левого сомножи- теля должна равняться высоте правого), и получается матрица разме- ром 𝑚 × 𝑘. Ценой такого умножения будем считать произведение 𝑚𝑛𝑘 (таково число умножений, которые нужно выполнить при стандартном способе умножения | но сейчас это нам не важно). Умножение матриц ассоциативно, поэтому произведение 𝑠 матриц можно вычислять в раз- ном порядке. Для каждого порядка подсчитаем суммарную цену всех матричных умножений. Найдите минимальную цену вычисления произ- ведения, если известны размеры всех матриц. Число действий должно быть ограничено многочленом от числа матриц. 8.1. Таблица значений (динамическое программирование) 139 Пример. Матрицы размером 2 × 3, 3 × 4, 4 × 5 можно перемножать двумя способами. В первом цена равна 2 · 3 · 4 + 2 · 4 · 5 = 24 + 40 = 64, во втором цена равна 3 · 4 · 5 + 2 · 3 · 5 = 90. Решение. Представим себе, что первая матрица написана на отрезке [0, 1], вторая | на отрезке [1, 2], . . . , 𝑠-я | на отрезке [𝑠 − 1, 𝑠]. Матри- цы на отрезках [𝑖 − 1, 𝑖] и [𝑖, 𝑖 + 1] имеют общий размер, позволяющий их перемножить. Обозначим его через 𝑑[𝑖]. Таким образом, исходным данным в задаче является массив 𝑑[0] . . . 𝑑[𝑠]. Через 𝑎(𝑖, 𝑗) обозначим минимальную цену вычисления произведе- ния матриц на участке [𝑖, 𝑗] (при 0 6 𝑖 < 𝑗 6 𝑠). Искомая величина равна 𝑎(0, 𝑠). Величины 𝑎(𝑖, 𝑖 + 1) равны нулю (матрица одна и перемножать ничего не надо). Рекуррентная формула будет такой: 𝑎(𝑖, 𝑗) = min{𝑎(𝑖, 𝑘) + 𝑎(𝑘, 𝑗) + 𝑑[𝑖]𝑑[𝑘]𝑑[𝑗]} где минимум берётся по всем возможных местам последнего умноже- ния, то есть по всем 𝑘 = 𝑖 + 1, . . . , 𝑗 − 1. В самом деле, произведение матриц на отрезке [𝑖, 𝑘] есть матрица размера 𝑑[𝑖]𝑑[𝑘], произведение матриц на отрезке [𝑘, 𝑗] имеет размер 𝑑[𝑘]𝑑[𝑗], и цена вычисления их произведения равна 𝑑[𝑖]𝑑[𝑘]𝑑[𝑗]. Замечание. Две последние задачи похожи. Это сходство станет яс- нее, если написать матрицы-множители на сторонах 1 { 2, 2 { 3, . . . , (𝑠 − 1) { 𝑠 многоугольника, а на каждой хорде 𝑖 { 𝑗 написать произве- дение всех матриц, стягиваемых этой хордой. 8.1.6. Железная дорога с односторонним движением имеет 𝑛 стан- ций. Известны цены билетов от 𝑖-й станции до 𝑗-й (при 𝑖 < 𝑗 | в обрат- ную сторону проезда нет). Найдите минимальную стоимость проез- да от начала до конца (с учётом возможной экономии за счёт переса- док). 8.1.7. Задано конечное множество с бинарной операцией (вообще говоря, не коммутативной и даже не ассоциативной). Имеется 𝑛 эле- ментов 𝑎 1 , . . . , 𝑎 𝑛 этого множества и ещё один элемент 𝑥. Проверьте, можно ли так расставить скобки в произведении 𝑎 1 × . . . × 𝑎 𝑛 , чтобы в результате получился 𝑥. Число операций должно не превосходить 𝐶𝑛 3 для некоторой константы 𝐶 (зависящей от числа элементов в выбран- ном конечном множестве). Решение. Заполняем таблицу, в которой для каждого участка 𝑎 𝑖 . . . 𝑎 𝑗 нашего произведения хранится список всех возможных его зна- чений (при разной расстановке скобок). 140 8. Как обойтись без рекурсии По существу этот же приём применяется в полиномиальном алго- ритме проверки принадлежности слова произвольному контекстно-сво- бодному языку (см. главу 15 ). Следующая задача (задача о рюкзаке) уже упоминалась в главе 3 8.1.8. Имеется 𝑛 положительных целых чисел 𝑥 1 , . . . , 𝑥 𝑛 и число 𝑁. Выясните, можно ли получить 𝑁, складывая некоторые из чисел 𝑥 1 , . . . . . . , 𝑥 𝑛 . Число действий должно быть порядка 𝑁𝑛. [Указание. После 𝑖 шагов хранится множество тех чисел на отрезке 0 . . . 𝑁, которые представимы в виде суммы некоторых из 𝑥 1 . . . 𝑥 𝑖 .] Замечание. Мы видели, что замена рекурсивной программы на за- полнение таблицы значений иногда позволяет уменьшить число дей- ствий. Примерно того же эффекта можно добиться иначе: оставить программу рекурсивной, но в ходе вычислений запоминать уже вычи- сленные значения, а перед очередным вычислением проверять, нет ли уже готового значения. 8.2. Стек отложенных заданий Другой приём устранения рекурсии продемонстрируем на примере задачи о ханойских башнях. 8.2.1. Напишите нерекурсивную программу для нахождения после- довательности перемещений колец в задаче о ханойских башнях. Решение. Вспомним рекурсивную программу, перекладывающую i верхних колец с m на n: procedure move(i,m,n: integer); var s: integer; begin if i = 1 then begin writeln (’сделать ход ’, m, ’->’, n); end else begin s:=6-m-n; {s - третий стержень: сумма номеров равна 6} move (i-1, m, s); writeln (’сделать ход ’, m, ’->’, n); move (i-1, s, n); end; end; Видно, что задача «переложить i верхних дисков с m-го стержня на n-й» сводится к трём задачам того же типа: двум задачам с i-1 дисками 8.2. Стек отложенных заданий 141 и к одной задаче с единственным диском. Занимаясь этими задачами, важно не позабыть, что ещё осталось сделать. Для этой цели заведём стек отложенных заданий, элементами ко- торого будут тройки ⟨i, m, n⟩. Каждая такая тройка интерпретируется как заказ «переложить i верхних дисков с m-го стержня на n-й». Зака- зы упорядочены в соответствии с требуемым порядком их выполнения: самый срочный | вершина стека. Получаем такую программу: procedure move(i,m,n: integer); begin сделать стек заказов пустым положить в стек тройку {инвариант: осталось выполнить заказы в стеке} while стек непуст do begin удалить верхний элемент, переложив его в if j = 1 then begin writeln (’сделать ход’, p, ’->’, q); end else begin s:=6-p-q; {s - третий стержень: сумма номеров равна 6} положить в стек тройки end; end; end; (Заметим, что первой в стек кладётся тройка, которую надо выполнять последней.) Стек троек может быть реализован как три отдельных сте- ка. (Кроме того, в паскале есть специальный тип, называемый «запись» (record), который может быть применён.) 8.2.2. (Сообщил А. К. Звонкин со ссылкой на Анджея Лисовского.) Для задачи о ханойских башнях есть и другие нерекурсивные алгорит- мы. Вот один из них: простаивающим стержнем (не тем, с которого переносят, и не тем, на который переносят) должны быть все стерж- ни по очереди. Другое правило: поочерёдно перемещать наименьшее кольцо и не наименьшее кольцо, причём наименьшее | по кругу. 8.2.3. Используйте замену рекурсии стеком отложенных заданий в рекурсивной программе печати десятичной записи целого числа. Решение. Цифры добываются с конца и закладываются в стек, а за- тем печатаются в обратном порядке. 8.2.4. Напишите нерекурсивную программу, печатающую все вер- шины двоичного дерева. 142 8. Как обойтись без рекурсии Решение. В этом случае стек отложенных заданий будет содержать заказы двух сортов: «напечатать данную вершину» и «напечатать все вершины поддерева с данным корнем» (при этом nil считается корнем пустого дерева). Таким образом, элемент стека есть пара: ⟨тип заказа, номер вершины⟩. Вынимая элемент из стека, мы либо сразу исполняем его (если это заказ первого типа), либо помещаем в стек три порождённых им зака- за | в одном из шести возможных порядков. |