c++ - 河内递归塔无法正常工作

Question

我正在尝试使用递归为学校项目做 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

温度

目标

三钉结束条件：开始 76543

温度 2

目标 1

总共采取了 127 步。

标签： c++c++11recursiontowers-of-hanoi

Answer 1

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);

    // ...    
}