この記事では、「タイリング問題」という非常に興味深い問題を理解します。
まず、この問題で何を達成したいかを理解しましょう。
タイリング問題を理解する
タイル貼り問題では、大きさ4*nの壁が与えられる。
これは壁の高さが4で、壁の長さがn（ユーザーから与えられる）であることを意味します。
ここで、サイズ4*1のタイルが無限にあり、それを2通りの方法で壁に並べることができる。
下図はその例です。
|
1
2
3
4
5
6
7
8
|
def find_count_arrangements(n):
if(n<=3):
return 1
return find_count_arrangements(n-1) + find_count_arrangements(n-4)
n = int(input())
print(find_count_arrangements(n))
|
我々の目的は、上記のどちらかの方法で小さなタイルを使って、壁一面を埋めるために可能なすべてのパターンを数えることです。
Pythonによるタイリング問題の解決策
ループとif-else条件を使った素朴なアプローチを手作業でコーディングすることもできますし、より高速なアプローチである再帰的アプローチをとることもできます。
もし、再帰についてもっと知りたいなら、以下のチュートリアルを読んでください。
再帰についてもっと読む。
再帰を使用すると、大きな問題を小さな問題に分割することができます。
ではここで、両方のアレンジで小さな問題を見てみましょう。
- アレンジメント1：最初のタイルは、壁の長さが4減少し、現在のタイルの上に残っているスペースは、1つの方法でしか埋めることができない方法1に従って置かれます（方法1に従って3タイル）。
- アレンジメント2：次に、壁の長さを1減らす方法2に従って、最初のタイルを置くことができます。
最初の配置が終わった後。
残りの壁についても、同じ関数を再帰的に呼び出すが、nの値は減少します。
最終的な解は、それぞれの再帰的な呼び出しで、両方の配置で可能な方法の合計となる。
以下に示す小さな図を通して、いくつかの例について理解しよう。
Pythonでタイリング問題の解を実装する
コードの実装は再帰を使ってとても簡単です。
ただ、先に説明した解決策を理解しているかどうか確認してください。
タイリング問題の問題文、解決策、コードの実装を理解していただけたでしょうか？お読みいただきありがとうございました。
それでは、よい勉強を
この記事もチェック：Pythonで再帰を使った0-1ナップザック問題の実装を解説する