2011-10-03 51 views
1

基本上,我必須編寫一個基本程序來解決我已經完成的n皇后問題,但是如果輸入任何數字> = 11,它會引發分段錯誤。在遞歸n皇后程序中獲取C++分割錯誤

從我在線閱讀的內容來看,這個錯誤通常是由處理內存時錯誤的邏輯引起的,但我似乎無法弄清楚我做錯了什麼。

void generateBoard(int board[],int column,int length,int count) 
{ 
    if(column == 0 && board[0]<length) //prevents outputting the results infinitely 
    { 
     ++board[0]; 
     generateBoard(board, ++column, length, count); 
    } 
    else 
    { 
     bool lineNotFound = true; 
     int row = board[column]; 
     while(lineNotFound && row < length) 
     { 
      ++row; //temporary value for a column value candidate 
      lineNotFound = false; 
      for(int i = 0; i < column && !lineNotFound; ++i) 
      { 
       if(board[i] == row || (board[i]+column-i) == row || (board[i]-column+i) == row) // check diagonal and horizontal 
       { 
        lineNotFound = true; 
       } 
       else 
       { 
        board[column] = row; 
       } 
      } 
     } 
     if(column == length-1 && !lineNotFound) // at last column and valid board 
     { 
      output(board,length,++count); 
      generateBoard(board,column,length,count); 
     } 
     else if(!lineNotFound) // not at last column, but valid position found 
     { 
      generateBoard(board,++column,length,count); 
     } 
     else if(column != 0) //no valid columns, go back a step 
     { 
      board[column] = 0; 
      generateBoard(board,--column,length,count); 
     } 
    } 
} 

我意識到是代碼一大塊,但我覺得有必要將它張貼所有獲得問題的想法。

任何想法? :s

我是新來的編程C++,所以我不知道從哪裏開始調試。

+0

你能寫出你用來調用引起分段錯誤的函數的參數的值嗎? –

+0

「我是編程C++的新手,所以我不知道從哪裏開始調試。」開始在調試器下運行你的程序!有了這個,你可以找出哪條線爆炸。這應該提供一些信息來弄清楚出了什麼問題。 –

+0

int board [boardSize]; 填充(board,board + boardSize,0); generateBoard(board,0,boardSize,0);因此,在這種情況下,generateBoard(board,0,11,0); –

回答

6

開始調試,然後讓它運行,直到出現分段錯誤。發生故障時 - 查看堆棧。我猜你會用遞歸來超越你的堆棧 - 這是遞歸程序的主要問題。

您可以放大您的堆棧,然後故障不會發生在輸入11上,而是發生在其他數字上,但遞歸程序總是會在輸入足夠大的堆棧問題上崩潰。順便說一句 - 確保遞歸是有界的,即:在某些時候,你的函數應該退出而不進一步調用它自己。恕我直言,這最好在開始時做(儘管它是一種風格和方便),因爲那樣你會清楚地看到遞歸結束的條件,並且它將更容易調試無限遞歸(這也會導致段錯誤因爲堆棧耗盡)。在你的情況下,遞歸如何結束並不是很清楚,我不會驚訝於它不適用於某些輸入。

澄清

雖然在某些系統上你得到一個「堆棧溢出」錯誤,對別人,你會得到「段錯誤」同樣的事情。我猜你是在「其他人」之一。

要說明的是,我剛剛編譯並運行這段代碼:

int foo(long a) 
{ 
    return foo(a-1); 
} 


int main() 
{ 
    return foo(9999999999L); 
} 

在我的GCC/Ububtu機。該程序具有無限遞歸,最終以「段錯誤」崩潰結束。

您可以將任何遞歸算法轉換爲迭代。不要用新變量遞歸調用函數,而是使用STL std::stack來推送和彈出它們並在循環中運行。這裏的細節:http://www.cplusplus.com/reference/stl/stack/

+0

我能夠在VC++上獲得堆棧溢出,板子大小爲8 :-) – xanatos

+0

也許他應該只使用堆而不是堆棧? – mydogisbox

+1

@mydogisbox:使用堆?調用堆而不是調用堆棧?這聽起來很有趣:P –