@ MattTimmermans, конечно, прав, говоря, что рекурсия не нужна для решения Ханойских башен. Но я думаю, что стандартное рекурсивное решение элегантно и раскрывает структуру решения. Поэтому стоит потратить несколько минут на то, чтобы разобраться с этим.
Прежде всего, следующее утверждение из вашего вопроса не является правильной интерпретацией:
Первый шаг: n - 1 -> 2, значит, мы получаем второй диск из стека дисков:
Это не то. hanoi (n, A, B, C) означает «переместить все диски из A в C, используя B в качестве временного места хранения. Это не означает« переместить диск N в одиночку », что вы не можете этого сделать, потому что правило игры состоит в том, что вы можете перемещать только диск c, на котором ничего нет.
Итак, рекурсивное решение говорит следующее:
Переместить n дисков от исходной привязки к целевой привязке (используя другую привязку в качестве временной):
Переместите верхние n −1 дисков на временную привязку.
Переместите диск c n (на котором теперь ничего нет) на привязку назначения.
Переместите диски n −1 с временного колышка (куда мы поместили их на шаге 1) на целевой колышек, используя исходный колышек в качестве временного.
Вот и все.
Что делает это решение рекурсивным, так это то, что в нем не объясняется, как на самом деле реализовать шаги 1 и 3. (Шаг 2 - это всего лишь простой ход.) Мы делаем шаг s 1 и 3, используя тот же алгоритм, за исключением одного dis c. Фактически, пока мы выполняем шаги 1 и 3, мы игнорируем dis c n (и диски большего размера, если таковые имеются). (Или, если хотите, мы притворяемся, что это пол.) Это прекрасно работает, потому что все они больше, чем любой из дисков, которые мы перемещаем, поэтому они не мешают нам поставить один из дисков, которыми мы являемся.
Итак, чтобы переместить три диска:
<b>Start: Goal is to move 3 discs from A to C</b>
┌─┐
└─┘
┌───┐
└───┘
┌─────┐
└─────┘
▀▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀
<b>1. Move 2 discs from A to B (using C)</b>
┌─┐
└─┘
┌─────┐ ┌───┐
└─────┘ └───┘
▀▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀
<b>2. Move disc 3 from A to C</b>
┌─┐
└─┘
┌───┐ ┌─────┐
└───┘ └─────┘
▀▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀
<b>3. Move 2 discs from B to C (using A)</b>
┌─┐
└─┘
┌───┐
└───┘
┌─────┐
└─────┘
▀▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀
Если по какой-то причине рекурсия кажется вам сбивающей с толку, представьте, что вы занимаетесь Ханойскими башнями и у вас есть друг, который вам поможет. Итак, вы начинаете с чтения инструкций по перемещению трех дисков с привязки A на привязку C, и они говорят, что первое, что вам нужно сделать, это переместить два диска с привязки A на привязку B. Но вы не знаете, как для этого вы позвоните своему другу, и он переместит два верхних диска с стержня A на стержень B, так что вы окажетесь на второй диаграмме выше. Теперь инструкции говорят переместить диск 3 с привязки A на привязку C, что вы можете сделать, потому что диск 3 теперь не покрыт. Итак, теперь вы находитесь на третьей диаграмме, и вам снова нужно переместить два диска. Итак, вы снова звоните своему другу, и он перемещает два диска с колышка A на колышек C для вас, и в результате появляется нижняя диаграмма, что означает, что проблема решена.
Так как же ваш другу удается это сделать? Что ж, они читают те же инструкции, что и вы, поэтому, когда вы просите их переместить два диска с привязки A на привязку B, им нужно сначала переместить один диск (два минус один, верно?) С привязки A на временную привязку , который является колышком C. Но это легко, поэтому они сдвигают один стержень. Затем инструкции говорят, что нужно переместить диск с колышка A на колышек B; опять же без проблем. И затем они должны переместить один диск с привязки C на привязку B. И в результате они переместили два диска с A на B. Enhorabuena.
Теперь давайте вернемся немного назад. Предположим, вы друг человека, которого попросили решить Ханойскую башню с четырьмя дисками, как в этой очень красивой анимации на странице Википедии . Конечно, у них те же инструкции, поэтому им пришлось начать с перемещения трех дисков с привязки A на привязку B, и, конечно, они попросили вас сделать это, потому что у вас уже есть практика перемещения трех дисков. Вы делаете это за них, а затем они снимают диск 4 с штифта A и помещают его на штифт C. А потом они перезвонят вам, чтобы переместить три диска с стержня B на стержень C.
А теперь самое интересное: вам действительно не нужны три человека для этого. Все, что вам нужно, это куча заметок. Каждый раз, когда у вас появляется подцель, вместо того, чтобы найти друга, вы просто записываете в инструкциях, какова ваша текущая цель и на каком этапе вы находитесь. Затем вы кладете стикер на стопку стикеров и притворяетесь, что вы тот друг, который должен сделать ход с одним диском меньше. Когда вы завершаете sh эту задачу, вы берете листок с вершины стопки и продолжаете с того места, где остановились, выбрасывая листок в мусор.
Это рекурсия. Это просто способ сказать, что когда вы решаете проблему, вам часто приходится делать ее по частям. И иногда решение по частям использует по существу тот же метод, но с меньшими входами.
Почему бы вам не попробовать его самому? Все, что вам нужно, - это несколько листов бумаги для обозначения дисков и несколько заметок (или больше кусочков бумаги), которые помогут вам запомнить, где вы находитесь. Выполнение этого вручную не займет у вас слишком много времени, и это намного легче понять, чем читать слова, написанные на иностранном языке.