a(i,j) = min {a(i,k)+ a(k,j) + d[i]*d[k]*d[j]}
где минимум берется по всем возможных местам последнего умноже-
ния, то есть по всем k=i+1..j-1. В самом деле, произведение мат-
риц на отрезке [i,k] есть матрица размера d[i]*d[k], произведе-
ние матриц на отрезке [k,j] имеет размер d[k]*d[j], и цена вы-
числения их произведения равна d[i]*d[k]*d[j].
Замечание. Две последние задачи похожи. Это сходство станет
яснее, если написать матрицы - множители на сторонах 1--2,
2--3,..., s-1--s многоугольника, а на каждой хорде i--j написать
произведение всех матриц, стягиваемых этой хордой.
8.1.5. Железная дорога с односторонним движением имеет n
станций. Известны цены белетов от i-ой станции до j-ой (при i <
j - в обратную сторонону проезда нет). Найти минимальную сто-
имость проезда от начала до конца (с учетом возможной экономии
за счет пересадок).
Мы видели, что замена рекурсивной программы на заполнение
таблицы значений иногда позволяет уменьшить число действий. При-
мерно того же эффекта можно добиться иначе: оставить программу
рекурсивной, но в ходе вычислений запоминать уже вычисленные
значения, а перед очередным вычислением проверять, нет ли уже
готового значения.
8.1.6. Задано конечное множество с бинарной операцией (во-
обще говоря, не коммутативной и даже не ассоциативной). Имеется
n элементов a[1]..a[n] этого множества и еще один элемент x.
Проверить, можно ли так расставить скобки в произведении
a[1]..a[n], чтобы в результате получился x. Число операций
должно не превосходить C*n*n*n для некоторой константы C (зави-
сищей от числа элементов в выбранном конечном множестве).
Решение. Заполняем таблицу, в которой для каждого участка
a[i]..a[j] нашего произведения хранится список всех возможных
его значений (при разной расстановке скобок).
По существу этот же прием применяется в полиномиальном ал-
горитме проверки принадлежности слова произвольному кон-
текстно-свободному языку (см. главу 13).
Следующая задача (задача о рюкзаке) уже упоминалась в главе
3 (Обход дерева).
8.1.7. Имеется n положительных целых чисел x[1]..x[n] и
число N. Выяснить, можно ли получить N, складывая некоторые из
чисел x[1]..x[n]. Число действий должно быть порядка N*n.
Указание. После i шагов хранится множество тех чисел на от-
реке 0..N, которые предствимы в виде суммы некоторых из
x[1]..x[i].
8.2. Стек отложенных заданий.
Другой прием устранения рекурсии продемонстрируем на приме-
ре задачи о ханойских башнях.
8.2.1. Написать нерекурсивную программу для нахождения пос-
ледовательности перемещений дисков в задаче о ханойских башнях.
Решение. Вспомним рекурсивную программу:
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
дисками и к одной задаче с единственным диском. Выполняя эти за-
дачи, важно не позабыть, что еще осталось сделать.
Для этой цели заведем стек отложенных заданий, элементами
которого будут тройки . Каждая такая тройка интерпретиру-
ется как заказ "переложить 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". (При этом инвариант соблюдает-
