Cтраница 2
Рассмотрим классическую головоломку, известную под назйанием Ханойская башня. Имеется три вертикальных стержня, назовем их а, Ь и с. На стержень а нанизано некоторое количество разных дисков, упорядоченных по размерам. Наименьший диск находится сверху, наибольший - снизу. Требуется перенести исходную башню дисков со стержня а на стержень с. При этом разрешается на каждом шаге перекладывать только один диск и требуется, чтобы никогда больший диск не находился выше меньшего. Решение задачи для случая трех дисков показано на рис. 6.1. Дугами изображены этапы перемещения дисков со стержня на стержень. Номера дуг задают порядок перемещений. [16]
На этой схеме отображено решение задачи о ханойских башнях для случая с пятью дисками. Приведенная ниже последовательность вызовов функций образует вычисление для трех дисков. [17]
Докажите, что рекурсивное решение задачи о ханойских башнях ( программа 5.7) является оптимальным. То есть, покажите, что любое решение требует, по меньшей мере, 2N - 1 перемещений. [18]
Лемма 5.2 Рекурсивный алгоритм разделяй и властвуй решения задачи о ханойских башнях дает решение, приводящее к 2 - 1 перемещениям. [19]
Чтобы дать представление о масштабах времени, рассмотрим решение задачи о Ханойской башне, заданной так, как это рассказывается в одной из дошедших до нас легенд. Нужно, перемещая каждый раз по одному диску и следя за тем, чтобы нигде больший диск не оказался над меньшим, рересадить все диски на стержень III так, чтобы они были расположены, как это было первоначально, когда они были посажены на стержень I. Подсчитано, что при затрате на каждый ход долей секунды решение этой задачи должно занять чуть ли не миллиард лет. То же самое оказывается при попытках решения некоторых практически важных задач управления методом перебора. [20]
Нетрудно заметить, что если известен алгоритм, решающий задачу о Ханойской башне с п - 1 дисками, то тогда можно легко указать решение и для случая п дисков. Перекладываем башню из п - 1 первых дисков на стержень Ь, затем / г-й диск на стержень с, затем опять решаем задачу о перемещении башни из / г - 1 дисков со стержня b на стержень с. Предположим, диски перенумерованы от 1 до / г, начиная с самого маленького диска. [21]
Формальное доказательство методом индукции того, что в решении задачи о ханойских башнях каждое второе перемещение затрагивает маленький диск ( все начинается и завершается такими перемещениями), весьма поучительно: Для п 1 существует только одно перемещение, затрагивающее маленький диск, следовательно, утверждение подтверждается. Это можно подтвердить, прибегнув к следующей рекурсивной конструкции: первое решение для п - 1 начинается с перемещения маленького диска, а второе решение для п - 1 завершается перемещением маленького диска, следовательно, решение для п начинается и завершается перемещением маленького диска. Мы поместили перемещение, не затрагивающее маленький диск, между двумя перемещениями, которые его затрагивают ( перемещением, завершающим первое решение для л - 1, и перемещением, начинающим второе решение для п - 1), следовательно, утверждение, что каждое второе перемещение затрагивает маленький диск, подтверждается. [22]
Докажите, что программы, порожденные продукционной системой из раздела 3.2 ( ханойская башня), не нарушают правил - больший диск не кладется на меньший. Покажите, что эти программы оптимальны - более коротких программ не существует. Сколько ходов требуется для решения задачи с п дисками. [23]
Ханойская башня для случая четырех дисков. [24] |
Ханойская башня) Каждый подающий надежды ученый должен познакомиться с некоторыми классическими задачами, а Ханойская башня ( см. рис. 5.18) - это одна из наиболее известных классических задач. Легенда гласит, что в храме на Дальнем Востоке священники пытаются переместить башню из дисков с одной стойки на другую. [25]
Напишите нерекурсивную программу, формирующую список операций, которые необходимо выполнить, чтобы решить задачу Ханойских башен ( разд. Подробно опишите все сделанные вами дополнения программы. [26]
Каждый подающий надежды исследователь в области вычислений рано или поздно должен столкнуться с некоторыми классическими задачами и Ханойские Башни ( смотри рис. 3.28) - одна из наиболее известных среди них. Легенда гласит, что в одном из монастырей Дальнего Востока монахи пытались переместить стопку дисков с одного колышка на другой. Начальная стопка имела 64 диска, нанизанных на один колышек так, что их размеры последовательно уменьшались к вершине. [27]
Сразу видно, что последовательность длин в точности совпадает с последовательностью перемещаемых дисков при решении задачи о ханойских башнях. Действительно, простым доказательством их идентичности является идентичность рекурсивных программ. Таким образом, применив другой подход, наши монахи могли воспользоваться метками на линейке для определения диска, который требуется переместить. [28]
При отыскании максимума время получения решения линейно связано с размером входного массива; при рисовании линейки и при решении задачи о ханойских башнях время линейно связано с размером выходного массива. [29]
Исследуйте таблицы - разрядных чисел, подобную приведенной на рис. 5.9, на предмет определения свойства / - го числа, определяющего направление / - го перемещения ( указанного знаковым битом на рис. 5.7) при решении задачи о ханойских башнях. [30]