17

次の問題を解決するためのアルゴリズムを思い付くことができないようです。一連のforループを使用してみましたが、非常に複雑になりました。

はしごにはn階段があり、1の階段または2の階段の任意の組み合わせを使用してはしごを登ることができます。はしごを登る方法はいくつありますか。

したがって、たとえば、ラダーに3つのステップがある場合、これらは可能なパスになります。

  • 1-1-1
  • 2-1
  • 1-2

そして4つのステップのために

  • 1-1-1-1
  • 2-1-1
  • 1-2-1
  • 1-1-2
  • 2-2

これをどのように行うことができるかについての洞察をいただければ幸いです。また、私はJavaで作業しています。

編集：私は確かに小さなn値を使用するつもりでしたが、大きな値で管理する方法を知っていることは確かに素晴らしいでしょう。

4

5 に答える 5

28

興味深いことに、この問題には簡単な解決策があります。再帰を使用できます：

public static int countPossibilities(int n) {
    if (n == 1 || n == 2) return n;
    return countPossibilities(n - 1) + countPossibilities(n - 2);
}

この種の「トリッキーな」問題に直面したときはいつでも、解決策は非常に洗練されていることが多いことを念頭に置き、再帰で何かができるかどうかを常に確認してください。

編集：この問題では比較的小さなn値を処理すると想定していましたが、大きな値を処理する場合は、上記の方法が完了するまでにかなりの時間がかかる可能性があります。Map1つの解決策は、にマップnされるを使用することですcountPossibilities(n)。このように、すでに実行した計算を実行するために時間を無駄にすることはありません。このようなもの：

private static Map<Integer, Integer> map = new HashMap<Integer, Integer>();
static {
    map.put(1, 1);
    map.put(2, 2);
}

public static int countPossibilities(int n) {
    if (map.containsKey(n))
        return map.get(n);

    int a, b;

    if (map.containsKey(n - 1))
        a = map.get(n - 1);
    else {
        a = countPossibilities(n - 1);
        map.put(n - 1, a);
    }

    if (map.containsKey(n - 2))
        b = map.get(n - 2);
    else {
        b = countPossibilities(n - 2);
        map.put(n - 2, b);
    }

    return a + b;
}

でこれを試してくださいn = 1000。2番目の方法は、最初の方法よりも文字通り桁違いに高速です。

于 2012-09-03T23:53:46.177 に答える
8

これは、これまでのコメントの1つで簡単に述べたように、実際にはフィボナッチ数列と密接に関連しています。各ステップnは、2ステップ下（n-2）または1ステップ下（n-1）のいずれかから到達できるため、到達する可能性の数そのステップは、これらの他の2つのステップに到達する可能性の合計です。最後に、最初のステップ（およびゼロ番目、つまり地面にとどまる）に到達する可能性は1つだけです。

また、stepの可能性の数は、 stepとnの結果にのみ依存するため、これらの中間値をすべてマップまたは配列に格納する必要はありません。最後の2つで十分です。n-1n-2

public static long possForStep(int n) {
    // current and last value, initially for n = 0 and n = 1
    long cur = 1, last = 1;
    for (int i = 1; i < n; i++) {
        // for each step, add the last two values and update cur and last
        long tmp = cur;
        cur = cur + last;
        last = tmp;
    }
    return cur;
}

これにより、コードの量が大幅に削減されるだけでなく、すべての中間値を格納するときの時間と空間のO（n）とは対照的に、時間と空間のO（1）の複雑さが増します。 。

ただし、いずれにせよ100に近づくlongと型もすぐにオーバーフローするため、 O（n）のスペースの複雑さは実際には問題ではないため、読みやすいこのソリューションを使用することもできます。n

public static long possForStep(int n) {
    long[] values = new long[n+1];
    for (int i = 0; i <= n; i++) {
        // 1 for n==0 and n==1, else values[i-1] + values[i-2];
        values[i] = (i <= 1) ?  1 : values[i-1] + values[i-2];
    }
    return values[n];
}

更新：これはフィボナッチ数列に近いが、これとはまったく同じではないことに注意してください。フィボナッチ数列は、これが進行している間に開始され0, 1, 1, 2, 3,...ます。1, 1, 2, 3, 5, ...possForStep(n) == fibonacci(n+1)

于 2012-09-08T13:59:33.533 に答える
1

私は動的計画法を使用し、ラダーが1ラングまたは2ラング短いという問題を毎回解決します。

def solveLadder(numOfRungs):
  if numOfRungs<=2:
    return numOfRungs
  return solveLadder(numOfRungs-1)+solveLadder(numOfRungs-2)
于 2012-09-03T23:55:33.760 に答える
0

これはフィボナッチ数列です。末尾再帰再帰を使用して、エレガントに解決できます。

    let ladder n =
        let rec aux n1 n2 n =
            if n=0 then (n1 + n2)
            else aux n2 (n1+n2) (n-1)
        aux 1 1 (n-2)

末尾以外の再帰コードを理解しやすくするには、次のようにします。

    let rec ladder n =
        if n<=2 then n
        else ladder (n-1) + ladder (n-2)

これは簡単にJavaに変換できます。

于 2014-10-19T14:10:53.390 に答える
-3
  1. リストアイテム

これは、私たちが取ることができるステップの数が1または2の場合、単純なフィボナッチ数列です。

  • 階段の可能性のあるケースはありません

    1 ----------------- 1

    2------------------2

    3------------------3

    4------------------5

    5------------------8

    6 ------------------ 13

等々

于 2016-09-08T14:01:58.343 に答える