Не могу понять рекурсивный алгоритм моих лекторов для Ханойских Башен

Question

Алгоритм следующий:

Algorithm move(k, from, to, spare)
if k >0 then
move(k−1, from, spare, to)
printf (”move top disc from %d to %d\n”,
from, to)
move(k−1, spare, to, from)

k - количество дисков (http://en.wikipedia.org/wiki/Tower_of_Hanoi). Я понимаю рекурсию, я просто не понимаю, как это должно работать, может кто-нибудь разобраться вthis?

Извините за то, что я нечеткий в моем описании здесь, это просто мое понимание того, что происходит, тоже довольно расплывчато - я понятия не имею, что делает строка printf, которая кажется основной для всей функции.

Answer 1

Рекурсивный алгоритм разбит на три этапа:

1. Переместить все диски, кроме одного, в «запасную» колышек
2. Переместить последний диск в конечный колышек
3. Переместите все диски, кроме одного (те, что на шаге 1), из запасного штифта в штифт назначения

Таким образом, все диски были перемещены в штифт назначения.

Шаги 1и 3 - два рекурсивных вызова move(k-1, ...) в псевдокоде.Шаг 2 смоделирован с помощью printf.

. Суть в том, что шаги 1 и 3 повторяются в большем количестве вызовов на move, и каждый вызов на move, для которого k > 0 печатает ровно одинстрока инструкций с prinft.Так что произойдет, что этот алгоритм напечатает шаги, которые вам нужно предпринять, чтобы переместить диски в мельчайших деталях, один за другим.

По сути, этот псевдокод не реализует алгоритм для перемещения колышки;это алгоритм для предоставления инструкций человеку , если хотите.