先生，这些天我正在提高我的递归技能，但我被困在《破解编码技能》一书的递归问题中。问题编号8.2
问题陈述是——想象一个机器人坐在N*N网格的上角。机器人只能向两个方向移动：右和下。机器人有多少种可能的路径？
我尝试了很多，但它只向我显示了一条路径。我的代码是（从书的解决方案中获得帮助）
#include<iostream>
#include<vector>
using namespace std;
struct point {
int x;
int y;
};
vector<struct point *> v_point;
int findPath(int x, int y) {
struct point *p = new point;
p->x = x;
p->y = y;
v_point.push_back(p);
if(x == 0 && y == 0) {
cout << "\n\t" << x << " " << y;
return true;
}
int success = 0;
if( x >= 1 ) {
cout << "\n success = " << success << " x = " << x << " " << " y = " << y;
success = findPath(x-1, y);
cout << "\n success = " << success << " x = " << x << " " << " y = " << y;
}
if(!success && y >= 1) {
cout << "\n\t success = " << success << " x = " << x << " " << " y = " << y;
success = findPath(x, y-1);
cout << "\n\t success = " << success << " x = " << x << " " << " y = " << y;
}
if(!success){
cout << "\n\t\t success = " << success << " x = " << x << " " << " y = " << y;
v_point.pop_back();
cout << "\n\t\t success = " << success << " x = " << x << " " << " y = " << y;
}
return success;
}
main() {
cout << endl << findPath(3, 3);
return 0;
}
我把printf语句检查我错在哪里，但我没有发现错误。请帮助我。
我根据您的说明编写了代码。但是，如果我想打印所有路径，它会给出不希望的答案。
int findPath(int x, int y) {
if(x == 0 && y == 0) { cout << endl; return 1; }
int path = 0;
if(x > 0) { cout << "d -> ";path = path + findPath(x-1, y); } // d = down
if(y > 0) { cout << "r -> ";path = path + findPath(x, y-1); } // r = right
return path;
}
对于3*3的网格，它给出（findPaths（2,2））：-
d -> d ->r -> r ->
r -> d -> r ->
r -> d->
r -> d -> d -> r ->
r -> d ->
r -> d -> d ->
你的问题是，当x
正确的递归规则是：
x==0 请注意，您必须同时执行步骤2和3。您的代码仅执行2（这会成功并阻止执行步骤3）。
编辑
如果你需要输出路径本身，那么你需要在递归时累积路径，只有当你到达目的地时才打印出来。（你这样做的方式——在下降时打印每一步——是行不通的。考虑从（2,2）到（0,0）所有经过（1,1）的路径。从（2,2）到（1,1）的每个路径段都需要打印多次：从（1,1）到（0,0）的每个路径段打印一次。如果你在递归时打印，你不能这样做。）
一种方法是将路径编码为长度等于预期路径长度的数组（所有路径都将正好是x y步长），并在您移动方向的代码中填写它。这是一种方法：
static const int DOWN = 0;
static const int RIGHT 1;
int findPath(int x, int y, int *path, int len) {
if (x == 0 && y == 0) {
printPath(path, len);
return 1;
}
int n = 0;
if (x > 0) {
path[len] = DOWN;
n += findPath(x-1, y, path, len + 1);
}
if (y > 0) {
path[len] = RIGHT;
n += findPath(x, y-1, path, len + 1);
}
return n;
}
void printPath(int *path, int len) {
if (len == 0) {
cout << "empty path";
} else {
cout << (path[0] == DOWN ? " d" : " r");
for (int i = 1; i < len; ++i) {
cout << " -> " << (path[i] == DOWN ? " d" : " r";
}
}
cout << endl;
}
您可以将其称为：
int *path = new int[x + y];
cout << "Number of paths: " << findPath(x, y, path, 0) << endl;
delete [] path;
