遞歸問題幫助C++

我試圖編寫代碼以檢查是否可以通過遵循特定規則來到達數組的末尾。您從整數數組的第一個元素開始，存儲在該位置的數字是您可以向前或向後進行多少次跳躍。目標是到達由0值表示的Vector的末尾。遞歸問題幫助C++

bool Solvable(int start, Vector<int> & squares) { 
     int steps = squares[start]; 
     int prev = start - steps; 
     int forward = start + steps; 
     if (prev >= 0) { 
      if (squares[prev] != squares[start]) { 
       return Solvable(prev, squares); 
      } 
     } 
     if (forward < squares.size()) { 
      if (squares[forward] == 0) return true; 
      if (squares[forward] != squares[start]) { 
       return Solvable(forward, squares); 
      } 
     } 
     return false; 
    }

的代碼似乎並沒有工作，因爲我覺得我缺少的基本情況，但我似乎無法找出其他的基本情況，我需要。

謝謝！

來源

2011-08-17 user871303

當你說「似乎沒有工作」時，你是什麼意思？它會達到無限循環嗎？行爲錯誤？你能添加一個正方形矢量和預期結果的例子嗎？ – NirMH

存在一些問題。首先，你的代碼只會選擇前進或後退，你從不選擇兩者。原因是你總是說return Solvable。你所需的是這樣的事情

// try backwards 
bool found = Solvable(prev, squares); 
// did it work? 
if (found) 
    return true; 
// oh well try forwards 
return Solvable(forward, squares);

有沒有檢查的基本情況，並沒有檢查出在這裏界，但希望你的想法。

第二個問題是您的squares[forward] != squares[start]和squares[prev] != squares[start]測試。正如你所描述的，他們似乎並不是我的問題的一部分。我會放棄他們。

很好的問題來說明遞歸順便說一句。

來源

2011-08-17 05:01:09 john

我越想這個問題，就越喜歡它。一個強大的解決方案還需要檢查你是否在一個循環中。例如，您可以輕鬆地結束在兩個方格之間向前和向後跳躍。更長的週期也是可能的。所以你需要維護一個'visited'布爾數組。最初這將是全部錯誤的，並且當您訪問每個方塊時，您會將其設置爲true。這樣你就可以確保你永遠不會訪問同一個廣場兩次，所以你可以避免陷入無限循環。 – john

檢測循環的一種更簡單的方法是運行另一個循環兩倍的速度;如果這兩個重合而沒有達到終點，你就有一個循環。 – MSN

@MSN：它佔用較少的內存，並且通常建議鏈接列表的長度未知，但我認爲一組bool會更容易理解。 OP已經在遞歸中掙扎，我們不要淹死他！ –

這是一個檢測週期並跟蹤您是否嘗試從特定方塊向前或向後移動的版本。使用具有非遞歸前端的遞歸輔助函數來設置變量（此處爲fwd和bck向量）以跟蹤您正在執行的操作的模式非常常見。

#include <iostream> 
#include <vector> 

using namespace std; 

bool helper(int cur, const vector<int> &squares, 
      vector<bool> &fwd, vector<bool> &bck) 
{ 
    cout << "cur=" << cur << " sq=" << squares[cur] << endl; 
    if (squares[cur] == 0) return true;  // Found. 
    if (fwd[cur] && bck[cur]) return false; // Cycle. 
    if (!fwd[cur]) {      // Try forwards. 
    fwd[cur] = true; 
    int up = cur + squares[cur]; 
    if (up < squares.size()) { 
     cout << "Forwards" << endl; 
     bool found = helper(up, squares, fwd, bck); 
     if (found) return true; 
    } 
    } 
    if (!bck[cur]) {      // Try backwards. 
    bck[cur] = true; 
    int dn = cur - squares[cur]; 
    if (dn >= 0) { 
     cout << "Backwards" << endl; 
     bool found = helper(dn, squares, fwd, bck); 
     if (found) return true; 
    } 
    } 
    return false; 
} 

bool solvable(const vector<int> &squares) 
{ 
    vector<bool> fwd(squares.size(), false); 
    vector<bool> bck(squares.size(), false); 
    return helper(0, squares, fwd, bck); 
} 

int sqs[] = { 2, 3, 1, 1, 4, 3, 4, 0, 1, 3, 1 }; 

int main(void) 
{ 
    vector<int> sq(sqs, sqs + sizeof(sqs)/sizeof(int)); 
    cout << solvable(sq) << endl; 
}

來源

2011-08-17 07:55:46

遞歸問題幫助C++

回答

相關問題