14

問題は

「あなたは階段を上っています。毎回、1 段または 2 段のいずれかを作ることができます。階段には n 段あります。何通りの方法で階段を上ることができますか?」

以下は、この問題のコード ソリューションですが、理解に苦慮しています。誰か説明してくれませんか

int stairs(int n) {
  if (n == 0) return 0;
  int a = 1;
  int b = 1;
  for (int i = 1; i < n; i++) {
    int c = a;
    a = b;
    b += c;
  }
  return b;
 }

ありがとう、

4

3 に答える 3

15

まず、再帰式と、そこから反復式を導き出す方法を理解する必要があります。

再帰式は次のとおりです。

f(n) = f(n-1) + f(n-2)
f(0) = f(1) = 1

( f(n-1)1 ステップ、f(n-2)2 ステップ、合計数はこれらのオプションの 1 つを使用する方法の数、つまり合計です)。

注意深く見ると、これもよく知られている数列であるフィボナッチ数であり、解は再帰を何度も再計算するのではなく、単純に各数値を計算するだけなので、はるかに効率的な解が得られます。

于 2013-03-30T17:38:58.037 に答える