3

Sir, these days i am improving my recursion skills but i am stuck in one of the recursion problem of "Cracking the coding skills" book. Problem number 8.2
Problem statement is -- Imagine a robot sitting on the upper hand corner of an N*N grid. The robot can only move in two directions: right and down. How many possible patha are there for the robot ?

I tried a lot but it only shows me a single path. My code is (taking help from solution of book)

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

I put printf statement to check where i am wrong, but i didn't find mistake. Please help me.

I wrote the code given by your instructions. But , if I want to print all the paths, it gives undesired answer.

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;
}

for grid of 3*3 It gives ( findPaths(2, 2) ) :-

d -> d ->r -> r ->
r -> d -> r ->
r -> d->
r -> d -> d -> r ->
r -> d ->
r -> d -> d ->
4

1 回答 1

5

您的问题是，当 时x >= 1，您正在递减x并设置success为 true。这可以防止您的代码探索 decrementing 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;
于 2012-06-12T05:56:37.120 回答