1

本で次の質問に遭遇しました：

N 段の階段があるとき、一度に 1 段、2 段、3 段のいずれかを使用すると、いくつの方法で登ることができますか?

以下は本が与えたコードです：

 int countWays(int n){

    if(n<0)
        return 0;

    if(n == 0)
        return 1;

    else return countWays(n-1) + countWays(n-2) + countWays(n-3);
  }

このコードを理解する上で、次の懸念があります。

  1. n=0 に対して 1 が返される理由がわかりません。歩数が 0 の場合、明らかに登る必要はなく、0 が返されます。

  2. n=3 の場合、関数は 4 を返しますが、(1,1,1)、(1,2)、(3) の 3 つのケースしか確認できません。

4

3 に答える 3

2

n=0で1が返される理由がわかりません。ステップが0の場合、明らかに登る必要はなく、0を返す必要があります。

階段がないときは、登らずにただ通り抜けるだけです。これが唯一の方法です。コメントの1つで指摘されているように、それはとして表すことができます()。

n = 3の場合、関数は4を返しますが、（1,1,1）、（1,2）、（3）の3つのケースしか表示できません。

実際には、（1,1,1）、（1,2）、（2,1）、（3）の4つのケースがあります。

于 2013-03-10T02:46:26.037 に答える
0

Geobitsが言ったように、3つの階段を上るには4つの方法があります

(1,1,1),(1,2),(2,1),(3)

n==0のときに1が返される理由n==0は、階段を上る方法が1つだけ見つかったということです。

最後に、このアルゴリズムは、大きな数値を入力すると非常に長い時間がかかります。動的プログラミングアプローチを探している場合は、nサイズ変更された配列を作成し、最初の3つのエントリをとして初期化して1,2,4から、配列の開始とインデックス3を反復処理する必要があります。毎回インデックスをに設定しますarray[i-1] + array[i-2] + array[i-3]。これにより、最小限の計算が実行されますが、大量のメモリが使用されます。

1x3サイズの配列のみを使用するより良い方法がありますが、それを行う方法はユーザーの演習として残しておきます。

于 2013-03-10T02:44:49.987 に答える
0

n=0 に対して 1 が返される理由がわかりません。歩数が 0 の場合、明らかに登る必要はなく、0 が返されます。

Terry による回答を補足するために、問題に対する一般的な回答はtribonacci(n+2)シーケンスです。したがって、 の場合n=0、つまりtribonacci(2)の値は 1 です。より詳細な調査については、この回答を参照してください。

もちろん、拒否することもできますf(n=0) = 1。そうする場合は、次の基本ケース値を使用するだけで、より快適に使用できます。すべてn>3がこれらの基本ケースに再帰されます。

  • f(n=1) = 1
  • f(n=2) = 2
  • f(n=3) = 4
于 2016-12-05T09:35:09.643 に答える