この再帰関数を理解する

Question

こんにちは仲間のプログラマー。

今や、再帰的プログラミングは、私が最小限に理解していることの1つです。そのため、私はいくつかの時間を使い、いくつかの基本的な事例を理解してプログラミングする必要があることを決めました。問題は、私はこの課題を解決したが、それがどのように動作するかをかなり理解していないことである。 -

誰かが私にそれを理解するのを助けることができたら、私はそれを感謝する。

ありがとうございます。

• Teilmann

割付：

dominopieceサイズ2 * 1を有しています。ボードの長さはn、幅は2です。ウェイ数を返す再帰的なメソッドを作成しますが、ボードはdominopiecesで覆うことができます。

私の方法：n = 1ベース場合、

public static int dominobrik(int n){ 
    int sum; 

    if(n >= 0 && n <= 2){ 
     sum = n; 
    } else { 
     sum = dominobrik(n-1) + dominobrik(n-2); 
    } 

    return sum; 

} 

Answer 1

この種の再帰呼び出しを理解するのに役立つように、実際にうまく印刷することが本当に役立つと思います。

プログラムの出力は、再帰の深さに従ってインデントされています。

dominobrik(n-2) + dominobrik(n-1) 

（新しい各パスについて、再帰コールは最初の二つの水平片場合を追加していることに気づく：ここ

を行う5の幅のためのすべてのソリューションに到達するのに要する8回のパスであります可能）

（また、これはあなたが書いたあなたが投稿コードとは異なることに注意してください（n-1）の最初にして（N-2）が、それは本当に多くの変更されません）

So far the board is: 
..... 
..... 

    So far the board is: 
    --... 
    --... 

      So far the board is: 
      ----. 
      ----. 

       Finished board: 
       ----| 
       ----| 


      So far the board is: 
      --|.. 
      --|.. 

       Finished board: 
       --|-- 
       --|-- 


       So far the board is: 
       --||. 
       --||. 

        Finished board: 
        --||| 
        --||| 


    So far the board is: 
    |.... 
    |.... 

      So far the board is: 
      |--.. 
      |--.. 

       Finished board: 
       |---- 
       |---- 


       So far the board is: 
       |--|. 
       |--|. 

        Finished board: 
        |--|| 
        |--|| 


      So far the board is: 
      ||... 
      ||... 

       So far the board is: 
       ||--. 
       ||--. 

        Finished board: 
        ||--| 
        ||--| 


       So far the board is: 
       |||.. 
       |||.. 

        Finished board: 
        |||-- 
        |||-- 


        So far the board is: 
        ||||. 
        ||||. 

         Finished board: 
         ||||| 
         ||||| 

Answer 2

は、ボード上のドミノを配置する唯一の1の方法があり、それは水平方向です。 n = 2の場合、ドミノを配置する方法は2つあります。縦に並べても、横に並べてもどちらでも構いません。 n = 3場合について

、3つの方法は、次のとおり

上部に水平に

1. 1、及び垂直に下に2。
2. 横に1つ下を横切り、2が垂直に上になる。
3. または3つすべて水平に積み重ねられます。 n = 3場合には、あなたがn = 2例配置の両方を繰り返してきたが、これらに、あなたはn = 1ケースから配置を追加したことを

注意。 n = 1の有効な配置は、単一の水平ドミノだけであることを思い出してください。 n = 3の各ケースには、少なくとも1つの水平ドミノがあります。

ケースをn = 4に拡張することができます。上記の可能な組み合わせをすべてn = 3について取ってからn = 2のすべての組み合わせを追加し、問題の制約を受けて適切に積み重ねます。

私はこれを説明することができればよいと思っていますが、それをいくつかの四角い紙に描くのに役立ちます。

Answer 3

あなたはnの回答を知っており、答えはn + 1となりますか？

nのソリューションの一部については、最後のドミノが垂直に立っており、他のドミノは最後の2つのドミノが水平に積み重ねられています。

最後の2つのドミノが水平の場合は、n + 1ドミノを垂直方向に追加してください。しかし、最後のドミノが垂直の場合は、それを垂直に追加することもできますし、前のドミノを水平に反転することもできます。

nのソリューションの数だけでなく、最後のドミノの水平/垂直で終了するソリューションの数も追跡できます。

これは宿題なので、残りの部分を解説します。また、私は本当に完全な解決策を考え出していません。あなたが投稿したソリューションと同等のものになる可能性があります。