Разминка для мозгов: Ханойские башни

Что-то грустно стало в королевстве Датском... Видимо надо сделать разминку для мозгов ))

Классика жанра: Ханойские башни

В начале времён Будда ниспослал монахам одного монастыря три алмазных стержня и 64 золотых диска, нанизанных на один из стержней. Все диски разного диаметра, но нанизаны в строгом порядке: меньший всегда на большем. И сказал Будда монахам: перенесите все диски с первого стержня на второй, пользуясь третьим стержнем, как вспомогательным. Переносить диски можно только по одному, а класть можно только меньший на больший. Когда все диски окажутся на втором стержне, мир закончит своё существование.

Рис. 1. Стержни считать алмазными, а диски — золотыми! ))

К сожалению, эту красивую легенду (возможны варианты!) придумали гораздо позже, чем тот момент, когда Будда явился к монахам )) Да и монахам нет никакого резона рвать пупок, перекладывая диски и приближая конец света. Однако...

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

How many disks? 3
A -> B
A -> C
B -> C
A -> B
C -> A
C -> B
A -> B
Press any key to continue . . .

Т.е. слева от стрелки указан стержень с которого взяли диск, а справа — стержень, на который диск поместили.

Дополнительные условия:

1. Программа должна работать правильно.

2. Программа должна быть максимально короткой (но без обфускации на уровне исходного кода).

3. Запретить пользоваться интернетом для поиска решения вам, конечно, ни кто не может... Но всё же попробуйте дойти до решения самостоятельно!

4. Корректность ввода количества дисков не проверять. Т.е. считать, что для количества дисков всегда введено число в диапазоне от 0 до 64 включительно.

PS. При тестировании не указывайте количество дисков больше 5-6. Поскольку минимальное количество перемещений дисков равно 2^n-1. Так что при 64 дисках конец мира нам пока не грозит ))

В своё время я читал одну статью на хабрахабре про ханойские башни. Там было простое и хорошее объяснение как решать через рекурсию, которое очень хорошо запоминается (приблизительное цитирование): «Чтобы переместить N дисков со столбика A на столбик B нужно перенести N-ный диск на столбик B, а сами верхние N-1 дисков на столбик C, потом необходимо перенести N-1 дисков со столбика C на столбик B таким же образом, но теперь »буфером« будет A. И так пока N-1 не станет равна 0».
Вот как я её реализовал:

#include <iostream>

void hanoi(int num, char from, char to, char buff)
{
    if (num != 0 )
    {
        hanoi(num-1, from, buff, to);
        std::cout << from << " -> " << to << std::endl;
        hanoi(num-1, buff, to, from);
    }
}

int main()
{
    int num;
    std::cin >> num;
    hanoi(num, 'A', 'B', 'C');
    return 0;
}

Я пытался ещё реализовать не рекурсивно. Что-то не получается :(

Я пытался ещё реализовать не рекурсивно. Что-то не получается

Стек для возврата к нужному состоянию ;-)

Стек для возврата к нужному состоянию ;-)

То есть?

Cranium, не будет какого-нибудь подытоживания? :(

porshe, итожить-то собственно нечего. Твоё решение — попадание в «десятку»: просто, изящно, экономично. Молодец!

Твоё решение

Это не моё решение. Строго говоря, мне просто повезло, что сколько-то времени назад я прочитал про этот алгоритм. Так что не за что меня хвалить :(