我在这次递归中错了

Question

先生,这些天我正在提高我的递归技巧,但我陷入了"破解编码技巧"一书的递归问题之一.问题编号8.2
问题陈述是 - 想象一个机器人坐在N*N网格的上角.机器人只能向两个方向移动:向右和向下.机器人有多少可能的patha？

我尝试了很多,但它只给我一条路径.我的代码是(从书的解决方案中获取帮助)

#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 ->

Answer 1

你的问题是,当x >= 1你减少x并设置success为真时.这可以防止您的代码探索递减y.

正确的递归规则是:

1. 如果x == 0 && y == 0,返回1(空路径是唯一的路径)
2. 将路径数初始化为0
3. 如果x > 0然后添加由x - 1(递归调用)产生的路径数
4. 如果y > 0然后添加由y - 1(递归调用)产生的路径数
5. 返回添加的路径总数

请注意,您必须执行这两个步骤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;