1と2の可能な組み合わせを一定の和で見つけること

Question

これはCで実行するタスクです。これにアプローチする方法を教えてください。

列車の長さはnメートルです。それは1または2メートルの長さの個々のコンパートメントで構成されています。特定の長さの列車には、どのように多くの組み合わせが存在しますか？これを計算する関数Train (n)を書く。

Answer 1

スタートとの答えを推測最も単純なケースと規則性を探します。

1. Train (1)は明らかに1：（1）です。
2. Train (2)は、明らかに2：（1 1）および（2）である。
3. Train (3)は、3：（1 1 1）、（1 2）、（2 1）である。最初の2つを結合（1）と（1 1）resp（2）に組み合わせることができます。後者はまさにTrain (2)の組み合わせです。したがって、Train (3)はTrain (2) + 1です。
4. Train (4)は、（1 1 1 1）（1 2 1）（2 1 1）（2 2）である。再び、最初のものをTrain (3)の組み合わせである（1）と（1 1 1）、（1 2）、（2 1）を組み合わせることができます。最後は（1）と（2）との組み合わせで、（2）はTrain (2)の組み合わせです。したがって、Train (4)はTrain (3) + Train (2)です。さて、Train (3)を振り返ると、+ 1はTrain (1)です。

Train (n)は常にTrain (n - 1) + Train (n - 2)です。フィボナッチシーケンスの定義とまったく同じです。 Trainは、1つの整数引数を取り、整数を返します：私たちは働い

int Train (int n) { 
} 

定義

今、私たちはそれが機能スケルトンC.

1. に変換される方法を見てみましょう：

   int Train (int n) { 
       return Train (n - 1) + Train (n - 2); 
   } 
   

2. これは、infini私たちは基本ケースでそれを停止する必要があります。一つのベースケースは明確である：Train (1)は1：

   int Train (int n) { 
       if (n == 1) { 
        return 1; 
       } else { 
        return Train (n - 1) + Train (n - 2); 
       } 
   } 
   

3. これはまだ十分ではありません。 Train (2)が何をするのか想像してください：それはTrain (1) + Train (0)を計算します。Train (1)は問題ありませんが、Train (0)はTrain (-1) + Train (-2)と計算され、無限に繰り返されます。そこで、我々は別の基本ケースが必要になります。

   int Train (int n) { 
       if (n < 3) { 
        return n; 
       } else { 
        return Train (n - 1) + Train (n - 2); 
       } 
   } 
   

4. あなたが今ちょうどあなたにその最後のコードスニペットを貼り付けた場合：Train (2)これは動作しますが、我々は基本例を簡素化することができます。2.

   int Train (int n) { 
       if (n == 1) { 
        return 1; 
       } else if (n == 2) { 
        return 2; 
       } else { 
        return Train (n - 1) + Train (n - 2); 
       } 
   } 
   

5. です「あまりにも長い、読まなかった」予選を経ずに宿題をすると、私はあなたの教育をうまく損なうことになり、あなたはプログラムを学ぶことは決してありません。どういたしまして。

6. これはフィボナッチ数を計算する最良の方法ではありません。どうして？努力の重複を避けるためにコードをどのように修正するべきですか？想像できる別のアプローチがありますか？どれ？

Answer 2

これは簡単なfibonacci sequenceです。
長さがnの電車の場合、最初のカートの長さは1または2です。これはf(n) = f(n - 1) + f(n - 2)の式になります。

おそらくフィボナッチ数を計算する方法を教える必要はありません。

Answer 3

私はこの再帰式が質問

（N < = 2）リターンの場合のn
トレイン（N）=電車（N-1）+列車（N-2）