递归问题帮助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++

回答

相关问题