рекурсия — Solve Towers of Hanoi с 10 пластинами рекурсивного переполнения стека
Пытаюсь решить Башни Ханоя, и я действительно не могу понять, почему моя функция не работает. Я проверил каждое решение C ++ здесь.
bool CPlayer::MoveTop(int n, int from, int to)
{
if (n == 0)
{
m_towers.MoveDisc(to, 1);
return true;
}
MoveTop(n -1 , from , 1);
m_towers.MoveDisc(1,from);
MoveTop(n - 1, 1, to);
}// MoveTop
Где 1 — средний колышек. И m_tower.MoveDisc (to, from) перемещает один диск из одного колышка в другой.
А вот и первый вызов функции MoveTop.
void CPlayer::OnRun()
{
bool ok = MoveTop(10,0,2);
}// OnRun
У меня также есть функция высоты, которая возвращает количество пластин на колышках, но я не думаю, что мне это нужно.
ДОБАВЛЕНО БОЛЬШЕ ОПИСАНИЯ ПРОБЛЕМЫ
Все ходы показаны в графическом окне, где я вижу результат перемещения пластин от колышка к колышку. И теперь он не просто сделает то, что должен. При запуске кода первая платформа перемещается в колышек 1 (колышек посередине) и «прыгает» вверх и вниз.
Доступны следующие функции:
Функция высоты:
int CTowers::Height(int tower)
{
ASSERT( torn>=0 && torn<3 );
return m_height[torn];
}
Возвращает высоту на конкретной башне.
int CTowers::TopSize(int tower)
{
int h = Height(tower);
if (h==0)
return 1000;
else return DiscSize(torn, h-1);
}
Возвращает размер вершины на колышке.
int CTowers::DiscSize(int tower, int place)
{
ASSERT( place < Height(torn) );
return m_pinne[tower][place];
}
Возвращает указанное значение.
bool CTowers::MoveDisc(int to, int from)
{
if (m_abort)
return false; //
m_pView->DrawAnimation( from, to );
if (TopSize(from)>=TopSize(to))
return false;
m_numMoves++;
int ds = Pop(from);
Push(to, ds );
m_pView->Invalidate();
return true;
}
Перемещает диск с одного колышка на другой.
Решение
Это старая школа 🙂 делим & победить проблему.
Попробуйте посмотреть на этот код:
void hanoi(int diskSize, int source, int dest, int spare)
{
//This is our standard termination case. We get to here when we are operating on the
//smallest possible disk.
if(diskSize == 0)
{
std::cout << "Move disk " << diskSize << " from peg " << source << " to peg " << dest << endl;
}
else
{
//Move all disks smaller than this one over to the spare.
//So if diskSize is 5, we move 4 disks to the spare. This leaves us with 1 disk
//on the source peg.
//Note the placement of the params.
//We are now using the dest peg as the spare peg. This causes each recursion to ping-pong
//the spare and dest pegs.
hanoi(diskSize - 1, source, spare, dest);
//Move the remaining disk to the destination peg.
std::cout << "Move disk " << diskSize << " from peg " << source << " to peg " << dest << endl;
//Move the disks we just moved to the spare back over to the dest peg.
hanoi(diskSize - 1, spare, dest, source);
}
}
Идея иметь 3 аргумента (source, dest, spare) состоит в том, чтобы каждый раз знать, какой колышек является запасным, чтобы вы могли использовать его для размещения на нем дисков.
Как указано в комментариях, настольные пинг-понги между запасным и дест.
Ваш код не может соответствовать правилу, где Вы не можете поместить больший диск поверх меньшего (увидеть Вот). Так что вам нужна переменная, чтобы сохранить целевой колышек, который не всегда 1 как в вашем коде.
Вот почему вам нужно 3 аргумента.
Ура!
Другие решения