Проблема Towers of Hanoi - классическая проблема для рекурсии. Вам дается 3 привязки с дисками на одном из них, и вы должны переместить все диски с одной привязки на другую, следуя приведенным правилам. Вы также должны сделать это с минимальным количеством ходов.
Здесь рекурсивный алгоритм, который решает проблему:
void Hanoi3(int nDisks, char source, char intermed, char dest)
{
if( nDisks > 0 )
{
Hanoi3(nDisks - 1, source, dest, intermed);
cout << source << " --> " << dest << endl;
Hanoi3(nDisks - 1, intermed, source, dest);
}
}
int main()
{
Hanoi3(3, 'A', 'B', 'C');
return 0;
}
Теперь представьте ту же проблему, только с 4 привязками, поэтому мы добавляем еще одну промежуточную привязку. Когда вы сталкиваетесь с проблемой выбора того, какую промежуточную привязку выбрать в любой точке, мы выберем самый левый, если более 1 свободен.
У меня есть следующий рекурсивный алгоритм для этой проблемы:
void Hanoi4(int nDisks, char source, char intermed1, char intermed2, char dest)
{
if ( nDisks == 1 )
cout << source << " --> " << dest << endl;
else if ( nDisks == 2 )
{
cout << source << " --> " << intermed1 << endl;
cout << source << " --> " << dest << endl;
cout << intermed1 << " --> " << dest << endl;
}
else
{
Hanoi4(nDisks - 2, source, intermed2, dest, intermed1);
cout << source << " --> " << intermed2 << endl;
cout << source << " --> " << dest << endl;
cout << intermed2 << " --> " << dest << endl;
Hanoi4(nDisks - 2, intermed1, source, intermed2, dest);
}
}
int main()
{
Hanoi4(3, 'A', 'B', 'C', 'D');
return 0;
}
Теперь, мой вопрос заключается в том, как бы я обобщил этот рекурсивный подход для работы с привязками K? Рекурсивная функция получит char[], которая будет содержать метки каждого стека, поэтому функция будет выглядеть примерно так:
void HanoiK(int nDisks, int kStacks, char labels[]) { ... }
Я знаю о алгоритме Frame-Stewart, который, скорее всего, оптимален, но не доказан, и который дает вам число ходов. Однако меня интересует строго рекурсивное решение, которое следует за образцом рекурсивных решений для 3 и 4 привязок, что означает, что он печатает фактические ходы.
Для меня, по крайней мере, псевдокод алгоритма Frame-Stewart, представленный в Википедии, довольно абстрактен, и мне не удалось преобразовать его в код, который печатает ходы. Я бы согласился с эталонной реализацией этого (для случайного K) или даже более подробного псевдокода.
Я попытался придумать какой-то алгоритм, который соответствующим образом изменяет массив меток, но мне не удавалось заставить его работать. Любые предложения приветствуются.
Update:
Кажется, что намного проще решить на функциональном языке. Здесь реализация F #, основанная на решении LarsH Haskell:
let rec HanoiK n pegs =
if n > 0 then
match pegs with
| p1::p2::rest when rest.IsEmpty
-> printfn "%A --> %A" p1 p2
| p1::p2::p3::rest when rest.IsEmpty
-> HanoiK (n-1) (p1::p3::p2::rest)
printfn "%A --> %A" p1 p2
HanoiK (n-1) (p3::p2::p1::rest)
| p1::p2::p3::rest when not rest.IsEmpty
-> let k = int(n / 2)
HanoiK k (p1::p3::p2::rest)
HanoiK (n-k) (p1::p2::rest)
HanoiK k (p3::p2::p1::rest)
let _ =
HanoiK 6 [1; 2; 3; 4; 5; 6]
И без обработки 3 привязок в качестве краевого случая:
let rec HanoiK n pegs =
if n > 0 then
match pegs with
| p1::p2::rest when rest.IsEmpty
-> printfn "%A --> %A" p1 p2
| p1::p2::p3::rest
-> let k = if rest.IsEmpty then n - 1 else int(n / 2)
HanoiK k (p1::p3::p2::rest)
HanoiK (n-k) (p1::p2::rest)
HanoiK k (p3::p2::p1::rest)
Заметим, что это не обрабатывает вырожденные случаи, для которых нет решения, например HanoiK 2 [1; 2]
