Алгоритм решения Ханойская башня

Я решал проблему Ханойской башни, чтобы больше узнать о рекурсии. Я смог реализовать это с помощью случая с 3 колышками, однако, когда я хотел использовать больше колышков (чтобы генерировать меньше ходов), я понимаю решение Frame-Stewart, где мне нужно разбить количество дисков, которые у меня есть, и установить их на стек один peg и никогда не трогайте этот колышек, пока я пересылаю диски из колышка источника в колышки назначения со всеми промежуточными колышками. Тем не менее, я не понимаю, как написать что-то вроде перемещения (диски, 1, я, {2 … K}) в качестве функции. Как я могу написать имена все колышки в прототипе функции, когда я даже не знаю их с самого начала? Ниже я привел то, что я разработал для решения с 3 дисками, но мне нужна помощь в более общем случае.

// private member function: primitive/basic move of the top disk
// from the source peg to the destination peg -- and legality-check
void move_top_disk(int source, int dest)
{
cout << "Move disk " << towers[source].front() << " from Peg ";
cout << source+1 << " to Peg " << dest+1;
towers[dest].push_front(towers[source].front());
towers[source].pop_front();
if (true == is_everything_legal())
cout << " (Legal)" << endl;
else
cout << " (Illegal)" << endl;
}

// private member function: recursive solution to the 3 Peg Tower of Hanoi
void move(int number_of_disks, int source, int dest, int intermediate)
{
if (1 == number_of_disks)
{
moves++;
move_top_disk (source, dest);
}
else
{
moves++;
move (number_of_disks-1, source, intermediate, dest);
move_top_disk (source, dest);
move (number_of_disks-1, intermediate, dest, source);
}
}

Я не понимаю, какие изменения мне нужно было бы внести в мою функцию перемещения, чтобы решить ее для случая с 6 колышками. Спасибо

1

Решение

Вам нужно будет изменить последний блок кода, куда он перемещается, перемещать-верх-диск, перемещать.

А вот статья о решении Ханойских башен для N колышков: Башни Ханоя с K колышками

2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]