башни Ханой рекурсии не работает правильно - PullRequest
Новая
       33

башни Ханой рекурсии не работает правильно

0 голосов
/ 29 сентября 2018

Я пытаюсь сделать Ханойские башни с 7 дисками, используя рекурсию для школьного проекта, я не уверен, в чем проблема, но вывод совершенно неправильный.Я предполагаю, что это как-то связано с функцией moveDisk (), но я не могу найти проблему.Количество ходов правильное.Любая помощь приветствуется.Вот мой код, и, если у вас есть какие-либо вопросы, оставьте комментарий: 

//#include "stdafx.h"
#include <iostream>
#include <string>
#include <vector>
#include <cassert>

using namespace std;

struct Peg
{
    vector<int> peg;
    string name;
};

void loadDisk(int diskNum, vector<int> &startPeg)
{
assert(startPeg.size() == 0);
for (int i = diskNum; i > 0; i--)
{
    startPeg.push_back(i);
}
}

void printPeg(int diskNum, vector<int> peg, string name)
{
cout << name << endl;
assert(peg.size() >= 0);
if (peg.size() > 0)
{
    for (unsigned int i = 0; i < peg.size(); i++)
    {
        cout << peg[i];
    }
}
cout << endl << endl;
}

void moveDisk(vector<int> &startPeg, vector<int> &goalPeg)
{
if (goalPeg.size() == 0)
{
    int temp = startPeg.back();
    startPeg.pop_back();
    goalPeg.push_back(temp);
}
}

int hanoi(int diskNum, vector<int> &startPeg, vector<int> &goalPeg, vector<int> &tempPeg)
{
int count = 0;
if (diskNum == 0)
{
    moveDisk(startPeg, goalPeg);
}
else
{
    count = hanoi(diskNum - 1, startPeg, tempPeg, goalPeg);
    moveDisk(startPeg, goalPeg); 
    count++;
    count += hanoi(diskNum - 1, tempPeg, goalPeg, startPeg);
}
return count;
}



int main()
{
Peg startPeg, tempPeg, goalPeg;
startPeg.name = "Start";
tempPeg.name = "Temp";
goalPeg.name = "Goal";
int diskNum = 7;

loadDisk(diskNum, startPeg.peg);

cout << "Starting Conditions with three pegs: " << endl;

printPeg(diskNum, startPeg.peg, startPeg.name);
printPeg(diskNum, tempPeg.peg, tempPeg.name);
printPeg(diskNum, goalPeg.peg, goalPeg.name);

int moveCount = hanoi(diskNum, startPeg.peg, tempPeg.peg, goalPeg.peg);

cout << "End Conditions with three pegs: " << endl;

printPeg(diskNum, startPeg.peg, startPeg.name);
printPeg(diskNum, tempPeg.peg, tempPeg.name);
printPeg(diskNum, goalPeg.peg, goalPeg.name);

cout << moveCount << " total moves were taken." << endl;

system("pause");
return 0;
}

и текущий вывод: Начальные условия с тремя колышками: Старт 7654321

Temp

Цель

Конечные условия с тремя колышками: Старт 76543

Темп 2

Цель 1

Всего было сделано 127 ходов.

1 Ответ

0 голосов
/ 30 сентября 2018 
void moveDisk(vector<int> &startPeg, vector<int> &goalPeg)
{
    // if (goalPeg.size() == 0) better only do that if
    if(startPeg.size() > 0)
    {
        int temp = startPeg.back();  // would fail otherwise
        startPeg.pop_back();
        goalPeg.push_back(temp);
    }
}

int hanoi(int diskNum, vector<int> &startPeg, vector<int> &goalPeg, vector<int> &tempPeg)
{
    int count = 0;
    if (diskNum == 0)
    {
        // moveDisk(startPeg, goalPeg);  you want to do absolutely nothing
        //                               when there are no discs.
    }
    else
    {
        count = hanoi(diskNum - 1, startPeg, tempPeg, goalPeg);
        moveDisk(startPeg, goalPeg);
        count++;
        count += hanoi(diskNum - 1, tempPeg, goalPeg, startPeg);
    }
    return count;
}

int main()
{
    // ... 
    // int moveCount = hanoi(diskNum, startPeg.peg, tempPeg.peg, goalPeg.peg);
    // folowing the paramter names of your hanoi() it should be:
    int moveCount = hanoi(diskNum, startPeg.peg, goalPeg.peg, tempPeg.peg);

    // ...    
}
...