Пример задачи
Давайте рассмотрим другой пример, он основан на головоломке, разработанной более века назад.
По преданию, монахи в отдаленном монастыре могли предсказать, когда наступит конец света.
У них был набор из 3 алмазных игл.
Вот это современный игровой набор башен Ханоя, и здесь у нас есть 3 деревянные иглы вместо алмазных игл.
На первой алмазной игле было нанизано 64 дисков с уменьшением размера.
Здесь, у нас есть только 8 дисков.
Задача состоит в том, чтобы переместить все диски с одной иглы на другую, следуя определенным правилам.
По преданию, конец света наступит, когда они закончат решение этой задачи!
Монахи могли переносить только один диск на другую иглу каждый день, может быть, это были очень тяжелые диски.
Вот правила, которым они должны следовать, когда они перемещают диски.
Только один диск может быть перемещен за один раз.
Это было бы просто, если бы они могли переместить всю стопку из 64 дисков только в одном направлении.
Но это не было разрешено.
Больший диск никогда не должен быть уложен выше меньшего.
В любом случае, они могут перемещать только один диск за другим от большего к меньшему.
И, наконец, только одна дополнительная игла может быть использована для промежуточного размещения дисков.
Следуя этим правилам, это, казалось бы, простая задача потребует 2 в 64-й степени минус один перемещений!
Но как долго это будет до конца мира?
Вы не можете в это поверить, но 2 в степени 64 является огромным числом.
Даже если мы ускорим задачу путем перемещения каждого диска один раз в секунду вместо каждого дня, это потребует 580 миллионов лет, для выполнения поставленной задачи.
Возможно, в легенде есть доля правды, никто не будет знать, как будет выглядеть мир через 500 миллионов лет, но это, конечно, будет другой мир.
В общем, для n дисков, количество необходимых шагов составляет 2 в n степени минус один.
Давайте посмотрим, как эта проблема может быть решена с помощью программы.
Давайте сначала рассмотрим несколько простых примеров.
Давайте посмотрим на более простой случай с участием всего двух дисков.
Здесь показано начальное состояние для n, равного 2, и цель состоит в перемещении двух дисков из А в С.
Вы не можете просто переместить меньший диск из А в С, а затем больший диск из А в С, потому что тогда больший диск будет в верхней части над меньшим диском.
Поэтому меньший диск первым переносится в В.
Это будет промежуточный результат.
Теперь, больший диск освобождается и может быть перемещен из А в С, и далее меньший диск может быть перемещен из B в C.
И мы достигли нашей цели в 3 этапа.
Как я упоминал ранее, необходимые шаги это 2 в n-й степени минус один.
В этом случае, n = 2, и 2 в квадрате это 4, 4 минус 1 дает 3, такое же, как количество шагов, которые мы здесь нашли.
Давайте вернемся к задаче 3 дисков. Вот начальное состояние.
Мы только что решили задачу 2 дисков, и теперь мы знаем, как бороться с n равным 2. И мы знаем, что для того, чтобы переместить больший диск или нижний диск из А в С, мы должны сначала освободить его путем перемещения диска выше него куда-нибудь в другое место.
Давайте предположим, что 2 меньших дисков были перемещены в B, пропуская промежуточные шаги, потому что мы уже знаем, что это может быть сделано в 3 этапа.
После того, как самый большой диск освобождается, он может быть перемещен из А в С, теперь его конечный пункт назначения.
Остальную работу предстоит сделать, чтобы переместить два диска из B в C.
Опять мы знаем, как решить эту проблему 2 дисков в 3 этапа, так что мы можем пропустить детали.
Обратите внимание на то, что здесь одно отличие состоит в том, что B становится основной иглой и А используется в качестве вспомогательного средства, в то время как C, это по-прежнему игла назначения.
Как показано на схеме, решение может быть достигнуто в 7 шагов, снова, для n, равным 3, 2 в 3-й степени это 8, 8 минус 1 дает 7.
Вот схема, которая иллюстрирует идею алгоритма для решения задачи, используя метод, называемый Towers с 4 параметрами.
Мы начинаем решать задачу, указав размер задачи, в этом случае, 3, а затем А является источником, C является местом назначения и B является вспомогательным местом.
Чтобы решить эту задачу для n, равным 3, метод будет вызывать Towers для меньшей задачи с n, равным 2.
В этом случае, А является источником, B назначением и C вспомогательным местом.
Вот шаги для решения этого вызова Towers.
Это один простой шаг, чтобы переместить большой диск из А в С.
И здесь есть вызов Towers, чтобы завершить поставленную задачу, перемещая 2 диска из В в С с помощью А как вспомогательной иглы.
Обратите внимание, что два вызова Towers здесь являются рекурсивными вызовами, также как другие вызовы Towers ниже.
И шаг 4 это не рекурсивный шаг, также, как и шаги 1, 2, 3, 5, 6 и 7.
Надеюсь, что вы уже можете здесь увидеть шаблон.
Чтобы решить проблему Башня Ханоя для любого заданного n, мы можем сначала переместить n-1 дисков с вершины самого большого диска на вспомогательную иглу, следуя последовательным шагам, используя рекурсивный вызов, в котором А является источником, B назначением и C, как вспомогательная игла, затем переместить большой диск до места назначения с помощью нерекурсивного шага, и наконец, переместить n-1 дисков из вспомогательной иглы в конечный пункт назначения, используя другой рекурсивный вызов.
Важно заметить, что в этом вызове, идет перемещение n-1 дисков из B, в качестве источника, в C, в качестве места назначения, используя А в качестве вспомогательной иглы.
После того, как мы отработали стратегию, реализация рекурсивного метода решения проблемы Башен Ханоя является довольно простой.
Вот определение рекурсивного метода.
В этом варианте реализации, вместо того чтобы использовать 4 параметра, необходимы всего три параметра, num это количество дисков, from является источником и to является пунктом назначения.
Мы не нужен 4-й параметр, потому что это может быть определено внутри метода.
Если предположить, что иглы обозначены как 1, 2, и 3, это выражение здесь, где определяется расположение вспомогательной иглы.
На самом деле, как это делается, довольно умно.
Вы можете подумать о том, как это работает. Я вернусь к этому позже.
Эта часть является не рекурсивным вызовом, когда num равен 1, или есть только один диск.
Внутри кода else, три выражения представляют три ветви, которые мы видели при описании решения.
Три красных стрелки соответствуют трем выражениям, которые находятся в теле else, в том числе двум рекурсивным вызовам и не рекурсивному шагу.
Первый шаг, это рекурсивный вызов для перемещения num-1 дисков из from места в место temp.
Второе выражение должно фактически перемещать диск из верхней части from иглы в иглу назначения.
3-й выражение, это рекурсивный вызов перемещения num-1 дисков из temp места в место to.
Вы выяснили, как вспомогательная игла может быть определена, используя это выражение для temp.
Если предположить, что иглы обозначены как 1, 2 и 3, при этом 1, 2 и 3 будет составлять 6.
После того, как два из трех чисел фиксированы, мы можем определить третье путем вычитания двух известных значений, в этом случае, from и to, из 6.
Например, если from имеет значение 1 и to имеет значение 3, вычитая 1 и 3 из 6 будет давать 2, то есть, третью иглу.
Так что это вся реализация решения Башен Ханоя, хотя это может занять 580 миллионов лет, чтобы решить проблему, сама программа очень проста.
Давайте взглянем на эту программу в IDEA.
