3

サー、最近私は再帰スキルを向上させていますが、「コーディングスキルのクラッキング」という本の再帰問題の1つで立ち往生しています。問題番号8.2
問題の説明は次のとおりです。ロボットがN*Nグリッドの上部の隅に座っていると想像してください。ロボットは、右と下の2つの方向にしか移動できません。ロボットにはいくつの可能な経路がありますか？

私はたくさん試しましたが、それは私に単一のパスしか示していません。私のコードは（本の解決策から助けを借りて）

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

1 に答える 1

5

あなたの問題は、のとき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の実行を妨げます）。

編集

パス自体を出力する必要がある場合は、パスを繰り返して累積し、宛先に到達したときにのみ出力する必要があります。（あなたがそれをしている方法-あなたが降りるときに各ステップを印刷する-は機能しません。（1,1）を通過する（2,2）から（0,0）までのすべてのパスを考慮してください。）（2からの各パスセグメント、2）から（1,1）は、複数回印刷する必要があります。（1,1）から（0,0）までのパスセグメントごとに1回です。繰り返しながら印刷する場合、これはできません。）

これを行う1つの方法は、予想されるパスの長さに等しい長さの配列でパスをエンコードし（すべてのパスは正確にx + yステップ長になります）、移動した方向のコードを入力することです。これが1つの方法です：

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 に答える