递归解决方案不按预期工作/遇到错误

Question

我正在寻找一些问题的帮助，我之前模糊地询问过，它是递归地解决15-peg纸牌问题。当我编译并运行它时，我总是收到奇怪的错误，其中大部分都是“堆栈溢出”，或者说我遇到了seg错误。这就是我迄今为止的情况，其中“board [15]”代表15个挂钩板，“moves [36]”代表可以进行的所有可能的移动。当只剩下一个挂钩时，递归应该被发现。

#include <iostream> 

using namespace std;        

void solveGame(int a[15], int b[36][3], int c[15][4]); 

void chooseMove (int a[15], int b[36][3], int openSpace, int c[15][4]); 

int findEmpty (int a[15]); 

int pegCount (int a[15]); 

bool isPeg (int peg, int a[15]); 

int usedVals[15] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}; 

int d = 0; 

int index = 0; 

int main() 
{ 
    int openSpace = 5; 

    int board[15]= {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}; 

    board[openSpace] = 0; 

    int alreadyMoved[15][4];                           

    int moves[36][3] = {{0, 1, 3}, 
         {0, 2, 5}, 
         {1, 3, 6}, 
         {1, 4, 8}, 
         {2, 4, 7}, 
         {2, 5, 9}, 
         {3, 6, 10}, 
         {3, 7, 12}, 
         {3, 1, 0}, 
         {3, 4, 5}, 
         {4, 7, 11}, 
         {4, 8, 13}, 
         {5, 9, 14}, 
         {5, 8, 12}, 
         {5, 2, 0}, 
         {5, 4, 3}, 
         {6, 3, 1}, 
         {6, 7, 8}, 
         {7, 4, 2}, 
         {7, 8, 9}, 
         {8, 4, 1}, 
         {8, 7, 6}, 
         {9, 5, 2}, 
         {9, 8, 7}, 
         {10, 6, 3}, 
         {10, 11, 12}, 
         {11, 7, 4}, 
         {11, 12, 13}, 
         {12, 7, 3}, 
         {12, 8, 5}, 
         {12, 11, 10}, 
         {12, 13, 14}, 
         {13, 8, 4}, 
         {13, 12, 11}, 
         {14, 9, 5}, 
         {14, 13, 12}}; 


    solveGame(board, moves, alreadyMoved); 

    for (int i = 0; i < 13; i++) 
     cout << alreadyMoved[i][0] << " " << alreadyMoved[i][1] << " " < <alreadyMoved[i][2] << endl; 

    return 0; 
} 

// main recursive function 
void solveGame (int a[15], int b[36][3], int c[15][4] 
{ 
int empSpace; 
int moveIndex; 

    if (pegCount(a) < 2) { 
     cout<<"game over"<<endl; 
    } else { 
     empSpace = findEmpty(a); 
     chooseMove(a, b, empSpace, c); 
     solveGame(a, b, c); 
    } 
} 

// supposed to pick a move that is applicable to the board otherwise it find a new move 
void chooseMove (int a[15], int b[36][3], int openSpace, int c[15][4]) 
{ 
int i = 0; 

    while (1) { 
     if (i < 36 && b[i][2] == openSpace && isPeg(b[i][0],a) && isPeg(b[i][1],a)) { 
      a[b[i][0]] = 0; 
      a[b[i][1]] = 0; 
      a[b[i][2]] = 1; 

      c[d][0] = b[i][0]; 
      c[d][1] = b[i][1]; 
      c[d][2] = b[i][2]; 
      c[d][3] = i; 

      d++; 

      index = 0; 

      for (int v = 0; v < 15; v++) 
       usedVals[v] = -1; 

      break; 
     } else if (i > 35) { 
      a[b[c[d-1][3]][0]] = 1; 
      a[b[c[d-1][3]][1]] = 1; 
      a[b[c[d-1][3]][2]] = 0; 

      c[d-1][0] = 0; 
      c[d-1][1] = 0; 
      c[d-1][2] = 0; 
      c[d-1][3] = 0; 

      usedVals[index] = openSpace; 

      index++; 

      int newOpen = findEmpty(a); 

      chooseMove(a, b, newOpen, c); 
     } 

     i++; 
    } 
} 

// counts the pegs on the board in order to cancel recursion 
int pegCount (int a[15]) 
{ 
    int count = 0; 
    for (int i = 0; i < 15; i++) 
     if (a[i] == 1) 
      count++; 
    return count; 
} 

// finds an empty space that hasn't already been found faulty 
int findEmpty (int a[15]) 
{ 
    for (int i = 0; i < 15; i++) { 
     for(int j = 0; j < 15; j++) { 
      if(a[i] == 0 && i != usedVals[j] && usedVals[j] > -1) 
       return i; 
     } 
    } 
} 


// tests if current index is a peg 
bool isPeg (int peg, int a[15]) 
{ 
    return a[peg] == 1; 
} 

Answer 1

快速浏览显示了很多潜在的问题，但我认为它可能归结为您传递数组的方式。数组通过引用而不是按值传递，所以递归函数与数组的单个副本一起工作，我不认为这是你想要的。因此，你永远不会发现结局的举动，这将使你获得无限递归的堆栈。

尝试在递归的每个级别分配数组的新副本。有些人会希望你使用new或malloc，因为他们觉得对C++的介绍应该是一场试火，你必须掌握内存管理来做任何有用的事情。相反，我会建议你不要使用数组;使用一个集合类，它可以在通过值传递时正常工作（我认为POD的std :: vector将执行此操作），集合类将按照您的代码所期望的方式创建阵列的副本。

如果您确实需要进行广度优先搜索，您可能还会遇到在selectionMove中执行深度优先搜索的问题。

Answer 2

使用递归性时堆栈溢出很常见。这是由于函数调用的返回值存储在堆栈中，并且只要函数没有返回，堆栈就会继续填充。如果递归性太深，最终会填满整个堆栈并溢出，这也会导致SEGV。

Answer 3

当退出条件不起作用时，通常会出现堆栈溢出，但在这里您还将按值传递参数，即使在正常操作中，堆栈可能会使您的堆栈溢出。

我建议你通过引用或更好地在std :: vector中传递数组。 std :: vector是一个小对象，它将真实数据保存在堆分配空间中。你甚至可以返回这些。

我也建议你在调试器中启动你的程序，这是最简单和最有效的方法来找出究竟是哪里出了问题。

HTH。