+1 jaasski -1

РИСУНОК 5.7 ХАНОЙСКИЕ БАШНИ

На этой схеме отображено решение задачи о ханойских башнях для случая с пятью дисками. Мы сдвигаем четыре верхних диска влево на одну позицию (левый столбец), затем

+1 jgggjg -; Перемещаем диск 5 вправо,

а затем верхние четыре диска перемещаем влево на одну позицию (правый столбец). Приведенная ниже последовательность вызовов функций образует вычисление для трех дисков. Вычисленная последовател ьност ь перемещений - +1 -2 +1 +3+1-2+1 появляется в решении четыре раза (для примера показано первых семь перемещений).

ЬапоКЗ, +1) hanoi(2, -1) hanoid, +1) hanoiCO, -1) % shiftd, +1)

hanoiCO, -1) shift(2, -1)

I jBB. Jbi hanoid. +1)

hanoKO, -1) shift d. +1) JBm hanoKO, -1)

shift(3, +1) 1 haiioi(2, -1)

hanoid, +1) hanoKO. -1) shift d, +1) hanoKO, -1) shift(2, -1) hanoid, +1) hanoKO, -1) shift d, +1) hanoKO, -1)

Если требуемое разрешение равно 1/2 дюймов, давайте изменим масштаб, чтобы задача состояла в помещении метки в каждой точке в интервале от О до 2 , за исключением конечных точек. Таким образом, средняя метка должна иметь высоту п условных единиц, метки в середине левой и правой половин должны иметь высоту п - 1 условных единиц и т.д. Профамма 5.8 - простой алгоритм разделяй и властвуй для выполнения этой задачи; работа данного алгоритма применительно к небольшому примеру проиллюстрирована на рис. 5.8. С точки зрения рекурсии в основе метода лежит следующая идея. Для помещения меток на интервале, последний вначале делится на две равные половины. Затем создаются метки (более короткие) в левой половине (рекурсивно), помещается длинная метка в середине и рисуются метки (более короткие) в правой половине (рекурсивно). Если говорить об итерации, рис. 5.8 иллюстрирует, что с помощью этого метода метки создаются по порядку, слева направо - фокус заключается в вычислении длин интервалов. Дерево рекурсии, приведенное на рисунке, помогает понять вычисление: просматривая его сверху вниз, мы видим, что длина меток уменьшается на 1 для каждого вызова рекурсивной функции. Если просматривать дерево в поперечном направлении, мы получаем метки в том порядке, в каком они рисуются, поскольку для каждого данного узла вначале рисуются метки, связанные с вызовом функции слева, затем метка, связанная с данным узлом, а затем метки, связанные с вызовом функции справа.

Программа 5.8 Применение алгоритма разделяй и властвуй для рисования линейки

Для рисования меток на линейке мы рисуем метки в левой половине, затем самую длинную метку в середине, а затем метки в правой половине. Эта программа предназначена для использования со значением г-/ равным степени 2 - свойство, сохраняемое в ее рекурсивных вызовах (см. упражнение 5.27).

void rule (int 1, int г, int h) { int m = (l+r)/2; if (h > 0)

1 JL

rule(0, 8, 3) rule(0, 4. 2) ruleCO, 2, 1) ruleCO, 1, 0) maxkCl, 1) ruleCl, 2, 0) mark(2. 2) rule (2, 4, 1) rule(2, 3, 0) шагкСЗ, 1) rule(3, 4, 0) 1Пс1гк(4, 3) rule (4, 8, 2) rule (4, 6. 1) rule (4, 5, 0) mark(5, 1) rule(5, 6, 0) mark(6, 2) rule (6, 8. 1) rule(6, 7, 0) mark(7, 1) rule(7. 8, 0)

РИСУНОК 5.8 ВЫЗОВЫ ФУНКЦИЙ. РИСУЮЩИХ ЛИНЕЙКИ

Эта последовательность вызовов функций составляет вычисление для рисования линейки длиной 8, в результате чего наносятся метки 1, 2, I, J, 1, 2 и 1.

rule(l, m, h-1) mark(m, h) ; rule(m, r, h-1)

1 о 1 1 о о

Сразу видно, что последовательность длин в точности совпадает с последовательностью перемещаемых дисков при рещении задачи о ханойских башнях. Действительно, простым доказательством их идентичности является идентичность рекурсивных программ. Таким образом, применив другой подход, наши монахи могли воспользоваться метками на линейке для определения диска, который требуется переместить.

Более того, и решение задачи о ханойских башнях в программе 5.7, и программа рисования линейки в программе 5.8 являются вариантами общей схемы разделяй и властвуй , представленной программой 5.6. Все три профаммы решают задачу размера 2 , разделяя ее на две задачи размера 2 . При отыскании максимума время получения решения линейно связано с размером входного массива; при рисовании линейки и при решении задачи о ханойских башнях время линейно связано с размером выходного массива. Обычно считается, что время выполнения задачи о ханойских башнях определяется экспоненциальной зависимостью, поскольку объем задачи измеряется количеством дисков, т.е. п.

Рисование меток на линейке с помощью рекурсивной программы не представляет особой сложности, но не существует ли более простого способа вычисления длины /-ой метки для любого данного значения /? На рис. 5.9 показан еще один простой вычислительный процесс, дающий ответ на этот вопрос, /-ый номер, выводимый и программой решения задачи о ханойских башнях, и программой рисования линейки, - ни что иное как количество оконечных 0-вых разрядов в двоичном представлении /. Это утверждение можно доказать методом индукции по соответствию с формулировкой метода разделяй и властвуй для процесса вывода таблицы я-разрядных чисел: достаточно напечатать таблицу {п - 1)-разрядных чисел, каждому из которых предшествует 0-й разряд, а затем напечатать таблицу {п - 1)-разряд-ных чисел, каждому из которых предшествует 1-й разряд (см. упражнение 5.25).

Применительно к задаче о ханойских башнях использование соответствия с я-разрядными числами - простой алгоритм решения задачи. Можно смещать стопку дисков на один стержень вправо, до завершения повторяя следующие два шага:

ш Перемещение маленького диска вправо, если п нечетно (влево, если оно четно).

Выполнение единственного разрешенного перемещения, не затрагивающего маленький диск.

То есть, после перемещения маленького диска, остальные два стержня содержат два диска, один из которых меньше другого. Единственное разрешенное перемещение, не затрагивающее маленький диск - перемещение меньшего диска поверх большего. Каждое второе перемещение затрагивает маленький диск по

1 о 1 1

РИСУНОК 5.9

БИНАРНЫЙ

ПОДСЧЕТ И

ФУНКЦИЯ

РИСОВАНИЯ

ЛИНЕЙКИ

Вычисление функции рисования линейки эквивалентно подсчету количества оконечных нулей в четных N-разрядных числах.