1

符号なし整数 x、y を取得し、C で 0,0 からポイント x、y までのパスがいくつあるかを返す再帰関数を作成する方法を知っている人はいますか??

毎回 1 つのステップしかありません。上または右です。ステップの限界は長方形の中にあります: (0,0), (0, x), (0,y), (x,y)

4

2 に答える 2

4

申し訳ありませんが、これは C ではありませんが、よく理解している必要があります. $ で始まるものはすべて変数であり、残りは同様です。

function path($x, $y){
    if($x==0 && $y==0){ /* && is logical AND operator */
        return 1;
    // here's first (and only) edge case. If X and Y is 0, that means were are already where we want to be. We assume there's one path from the position you are on to the same position you are on.
    }

    $count=0;

    if($x>0){
        $count+=path($x-1, $y); // Here, we ask how many paths go from position (x-1, y) to zero, if the X is not zero already..
    }
    if($y>0){
        $count+=path($x, $y-1); // here same stuff for Y, if Y is not zero, let's recurse into (x, y-1)
    }

    return $count; // in those conditions above, the result is added into COUNT variable
}

$x=6; 
$y=4; // some input


print path($x, $y); // here it all starts, with the original input numbers

その背後には数学はなく、再帰です。path() 関数の実行ごとに、パス関数はパス関数の別のインスタンスを実行し、それが別のインスタンスを実行し、それが別のインスタンスを実行し、それが別のインスタンスを実行します..他の次元。再帰がすでに (0,0) の位置に達している場合にのみ、1 が返されます。これは前のインスタンスのカウント変数に追加され、さらに前のインスタンスのカウント変数に追加されます。それが印刷機能に返されるまで。

注: 関数は (0,0) から (x,y) に移動するのではなく、(x,y) から (0,0) に移動します。しかし、結果は同じです。

于 2013-01-08T13:06:18.603 に答える
2

Java ソリューション:

/**
 * Compute the number of ways you can get from 0,0 to x,y
 *
 * @param x grid width
 * @param y grid height
 * @return number of lattice paths
 */
public long compute(int x, int y) {
    // there's only 1 way you can reach a point which is on some edge
    if (x == 0 || y == 0) {
        return 1;
    }
    /* Otherwise apply back recursion, i.e. take the last step (when you reach x,y) :
    you can get there only by moving from x-1,y (right) or from x,y-1 (up).
    So the result would be the number of ways you can get to x-1,y plus the number 
    of ways you can get to x,y-1 */
    return compute(x - 1, y) + compute(x, y - 1);
}

グリッドの領域 (x と y) が大きくなるにつれて、アルゴリズムは非常に遅くなります。これは、再帰のために同じ値を何度も計算するためです。

Map<Pair, Long> cache = new HashMap<>();

public long compute(int x, int y) {
    Pair pair = new Pair(x, y);
    if (cache.containsKey(pair)) {
        return cache.get(pair);
    }
    if (x == 0 || y == 0) {
        return 1;
    }
    long result = compute(x - 1, y) + compute(x, y - 1);
    cache.put(pair, result);
    return result;
}

Pair は、 equals() および hashCode() Contract に続く単純な POJOです。

于 2016-03-01T00:41:02.453 に答える