Глава 8. Как обойтись без рекурсии. Для универсальных языков программирования (каковым является паскаль) рекурсия не дает ничего нового: для всякой рекурсивной программы можно написать эквивалентную программу без рекурсии. Мы не будем доказывать этого, а продемонстрируем некоторые при- емы, позволяющие избавиться от рекурсии в конкретных ситуациях. Зачем это нужно? Ответ прагматика мог бы быть таким: во многих компьютерах (в том числе, к сожалению, и в современных, использующих так называемые RISC-процессоры), рекурсивные прог- раммы в несколько раз медленнее соответствующих нерекурсивных программ. Еще один возможный ответ: в некоторых языках програм- мирования рекурсивные программы запрещены. А главное, при удале- нии рекурсии возникают изящные и поучительные конструкции. 8.1. Таблица значений (динамическое программирование) 8.1.1. Следующая рекурсивная процедура вычисляет числа со- четаний (биномиальные коэффициенты). Написать эквивалентную не- рекурсивную программу. function C(n,k: integer):integer; | {n,k >=0; k <=n} begin | if (k = 0) or (k = n) then begin | | C:=1; | end else begin {0 2. 8.1.3. Дан выпуклый n-угольник (заданный координатами своих вершин в порядке обхода). Его разрезают на треугольники диагона- лями, для чего необходимо n-2 диагонали (докажите индукцией по n). Стоимостью разрезания назовем сумму длин всех использованных диагоналей. Найти минимальную стоимость разрезания. Число действий должно быть ограничено некоторым многочленом от n. (Пе- ребор не подходит, так как число вариантов не ограничено многоч- леном.) Решение. Будем считать, что вершины пронумерованы от 1 до n и идут по часовой стрелке. Пусть k, l - номера вершин, причем l>k. Через A(k,l) обозначим многоугольник, отрезаемый от нашего хордой k--l. (Эта хорда разрезает многоугольник на 2, один из которых включает сторону 1--n; через A(k,l) мы обозначаем дру- гой.) Исходный многоугольник естественно обозначить A(1,n). При l=k+1 получается "двуугольник" с совпадающими сторонами. Через a(k,l) обозначим стоимость разрезания многоугольника A(k,l) диагоналями на треугольники. Напишем рекуррентную формулу для a(k,l). При l=k+1 получается двуугольник, и мы полагаем a(k,l)=0. При l=k+2 получается треугольник, и в этом случае так- же a(k,l)=0. Пусть l > k+2. Хорда k--l является стороной много- угольника A(k,l) и, следовательно, стороной одного из тре- угольников, на которые он разрезан. Противоположной вершиной i этого треугольника может быть любая из вершин k+1,...,l-1, и ми- нимальная стоимость разрезания может быть вычислена как min {(длина хорды k--i)+(длина хорды i--l)+a(k,i)+a(i,l)} по всем i=k+1,..., i=l-1. При этом надо учесть, что при i=k+1 хорда k--i - не хорда, а сторона, и ее длину надо считать равной 0 (по стороне разрез не проводится). Составив таблицу для a(k,l) и заполняя ее в порядке возрас- тания числа вершин (равного l-k+2), мы получаем программу, ис- пользующую память порядка n*n и время порядка n*n*n (однократное применение рекуррентной формулы требует выбора минимума из не более чем n чисел). 8.1.4. Матрицей размера m*n называется прямоугольная табли- ца из m строк и n столбцов, заполненная числами. Матрицу размера m*n можно умножить на матрицу размера n*k (ширина левого сомно- жителя должна равняться высоте правого), и получается матрица размером m*k. Ценой такого умножения будем считать произведение m*n*k (таково число умножений, которые нужно выполнить при стан- дартном способе умножения - но сейчас это нам не важно). Умноже- ние матриц ассоциативно, поэтому произведение n матриц можно вы- числять в разном порядке. Для каждого порядка подсчитаем суммар- ную цену всех матричных умножений. Найти минимальную цену вычис- ления произведения, если известны размеры всех матриц. Число действий должно быть ограничено многочленом от числа матриц. Пример. Матрицы размером 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],..., s-ая - на отрезке [s-1,s]. Матрицы на отрезках [i-1,i] и [i,i+1] имеют общий раз- мер, позволяющих их перемножить. Обозначим его через d[i]. Таким образом, исходным данным в задаче является массив d[0]..d[s]. Через a(i,j) обозначим минимальную цену вычисления произве- дения матриц на участке [i,j] (при 0<=i', 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 дисками и к одной задаче с единственным диском. Выполняя эти за- дачи, важно не позабыть, что еще осталось сделать. Для этой цели заведем стек отложенных заданий, элементами которого будут тройки . Каждая такая тройка интерпретиру- ется как заказ "переложить 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} | | | положить в стек тройки , <1,p,q>, | | end; | end; end; (Заметим, что сначала в стек кладется тройка, которую надо вы- полнять последней.) Стек троек может быть реализован как стри отдельных стека. (Кроме того, в паскале есть специальный тип, называемый "запись", который может быть применен.) 8.2.2. (Сообщил А.К.Звонкин со ссылкой на Анджея Лисовско- го.) Для задачи о ханойских башнях есть и другие нерекусивные алгоритмы. Вот один из них: простаивающим стержнем (не тем, с которого переносят, и не тем, на который переносят) должны быть все стержни по очереди. Другое правило: поочередно перемещать наименьшее кольцо и не наименьшее кольцо, причем наименьшее - по кругу. 8.2.3. Использовать замену рекурсии стеком отложенных зада- ний в рекурсивной программе печати десятичной записи целого чис- ла. Решение. Цифры добываются с конца и закладываются в стек, а затем печатаются в обратном порядке. 8.2.4. Написать нерекурсивную программу, печатающую все вершины двоичного дерева. Решение. В этом случае стек отложенных заданий будет содер- жать заказы двух сортов: заказ напечатать (в свое время) данную вершину и заказ напечатать все вершины поддерева с данным корнем (при этом nil считается корнем пустого дерева). Таким образом, элемент стека есть пара: <тип заказа, номер вершины>. Вынимая элемент из стека, мы либо сразу исполняем его (если это заказ первого типа) либо помещаем в стек три порожденных им заказа - в одном из шести возможных порядков. 8.2.5. Что изменится, если требуется не печатать вершины двоичного дерева, а подсчитать их количество? Решение. Печатание вершины следует заменить прибавлением единицы к счетчику. Другими словами, инвариант таков: (общее число вершин) = (счетчик) + (сумма чисел вершин в поддеревьях, корни которых лежат в стеке). 8.2.6. Для некоторых из шести возможных порядков возможны упрощения, делающие ненужным хранение в стеке элементов двух ви- дов. Указать некоторые из них. Решение. Если требуемый порядок таков: корень, левое поддерево, правое поддерево, то заказ на печатание корня можно не закладывать в стек, а вы- полнять сразу. Несколько более сложная конструкция применима для порядка левое поддерево, корень, правое поддерево. В этом случае все заказы в стеке, кроме самого первого (напеча- тать поддерево) делятся на пары: напечатать вершину x, напечатать правое поддерево x (т.е. поддерево с корнем в правом сыне x). Объединив эти пары в заказы специального вида и введя переменную для отдельного хра- нения первого заказа, мы обойдемся стеком однотипных заказов. То же самое, разумеется, верно, если поменять местами левое и правое - получается еще два порядка. Замечание. Другую программу печати всех вершин дерева можно построить на основе программы обхода дерева, разобранной в соот- ветствующей главе. Там используется команда "вниз". Поскольку теперешнее представление дерева с помощью массивов l и r не поз- воляет найти предка заданной вершины, придется хранить список всех вершин на пути от корня к текущей вершине. Cмотри также главу об алгоритмах на графах. 8.2.7. Написать нерекурсивный вариант программы быстрой сортировки. Как обойтись стеком, глубина которого ограничена C*log n, где n - число сортируемых элементов? Решение. В стек кладутся пары , интерпретируемые как отложенные задания на сортировку соответствующих участков масси- ва. Все эти заказы не пересекаются, поэтому размер стека не мо- жет превысить n. Чтобы ограничиться стеком логарифмической глу- бины, будем придерживаться такого правила: глубже в стек поме- щать больший из возникающих двух заказов. Пусть f(n) - макси- мальная глубина стека, которая может встретиться при сортировке массива из не более чем n элементов таким способом. Оценим f(n) сверху таким способом: после разбиения массива на два участка мы сначала сортируем более короткий (храня в стеке про запас) более длинный, при этом глубина стека не больше f(n/2)+1, затем сорти- руем более длинный, так что f(n) <= max (f(n/2)+1, f(n-1)), откуда очевидной индукцией получаем f(n) = O(log n). 8.3. Более сложные случаи рекурсии. Пусть функция f с натуральными аргументами и значениями оп- ределена рекурсивно условиями f(0) = a, f(x) = h(x, f(l(x))), где a - некоторое число, а h и l - известные функции. Другими словами, значение функции f в точке x выражается через значение f в точке l(x). При этом предполагается, что для любого x в пос- ледовательности x, l(x), l(l(x)),... рано или поздно встретится 0. Если дополнительно известно, что l(x) < x для всех x, то вычисление f не представляет труда: вычисляем последовательно f(0), f(1), f(2),... 8.3.1. Написать нерекурсивную программу вычисления f для общего случая. Решение. Для вычисления f(x) вычисляем последовательность l(x), l(l(x)), l(l(l(x))),... до появления нуля и запоминаем ее, а затем вычисляем значения f в точках этой последовательности, идя справа налево. Еще более сложный случай из следующей задачи вряд ли встре- тится на практике (а если и встретися, то проще рекурсию не устранять, а оставить). Но тем не менее: пусть функция f с нату- ральными аргументами и значениями определяется соотношениями f(0) = a, f(x) = h(x, f(l(x)), f(r(x))), где a - некоторое число, а l, r и h - известные функции. Предпо- лагается, что если взять произвольное число и начать применять к нему функции l и r в произвольном порядке, то рано или поздно получится 0. 8.3.2. Написать нерекурсивную программу вычисления f. Решение. Можно было бы сначала построить дерево, у которого в корне находится x, а в сыновьях вершины i стоят l(i) и r(i) - если только i не равно нулю, а затем вычислять значения функции, идя от листьев к корню. Однако есть и другой способ. "Обратной польской записью" (или "постфиксной записью") вы- ражения называют запись, где знак функции стоит после всех ее аргументов, а скобки не используются. Вот несколько примеров: f(2) 2 f f(g(2)) 2 g f s(2,t(7)) 2 7 t s s(2, u(2, s(5,3)) 2 2 5 3 s u s Постфиксная запись выражения позволяет удобно вычислять его с помощью "стекового калькулятора". Этот калькулятор имеет стек, который мы будем представлять себе расположенным горизонтально (числа вынимаются и кладутся справа). При нажатии на клавишу с числом это число кладется в стек. При нажатии на функциональную клавишу соответствующая функция применяется к нескольким аргу- ментам у вершины стека. Например, если в стеке были числа 2 3 4 5 6 и нажата функциональная клавиша s, соотвтетствующая функции от двух аргументов, то в стеке окажутся числа 2 3 4 s(5,6) Перейдем теперь к нашей задаче. В процессе вычисления значения функции f мы будем работать со стеком чисел, а также с последо- вательностью чисел и символов "f", "l", "r", "h", которую мы бу- дем интерпретировать как последовательность нажатий кнопок на стековом калькуляторе. Инвариант такой: если стек чисел представляет собой текущее состояние стекового калькулятора, то после нажатия всех клавиш последовательности в стеке останется единственное число, и оно будет искомым ответом. Пусть нам требуется вычислить значение, к примеру, f(100). Тогда вначале мы помещаем в стек число 100, а последовательность со- держит единственный символ "f". (При этом инвариант соблюдает- ся.) Далее с последовательностью и стеком выполняются такие пре- образования: старый старая новый новая стек последовательность стек последовательность X x P X x P X x l P X l(x) P X x r P X r(x) P X x y z h P X h(x,y,z) P X 0 f P X a P X x f P X x x l f x r f h P Обозначения: x, y, z,.. - числа, X - последовательность чисел, P - последовательность чисел и символов "f", "l", "r", "h". В пос- ледней строке предполагается, что m не равно 0. Эта строка соот- ветствует равенству f(x) = h(x, f(l(x)), f(r(x))), Эти преобразования выполняются, пока последовательность не ста- нет пуста. В этот момент в стеке окажется единственное число, которое и будет ответом. Замечание. Последовательность по существу представляет со- бой стек отложенных заданий (вершина которого находится слева).