C++で1xmサイズのタイルを使用してサイズnxmの床をタイル張りする方法の数を数えます

部屋の床の長さと幅を表す2つの数字nとmが与えられます。目標は、サイズ1Xmのタイルを使用してこの床をタイル張りできる方法の数を数えることです。

例

入力

n=3 m=2

出力

Count the number of ways to tile the floor of size n x m using 1 x m size tiles
are: 3

説明

方法は、以下に示すように配置された3つの1x2タイルになります-

入力

n=3 m=3

出力

Count the number of ways to tile the floor of size n x m using 1 x m size tiles
are: 2

説明

The ways will be three 1x3 tiles arranged vertically and horizontally. Only
two ways.

以下のプログラムで使用されるアプローチは次のとおりです −

このアプローチでは、nの値をチェックします。 nがm未満で、値が1の場合、サイズ1Xmの床全体に配置されるタイルは1つだけです。

nがmに等しい場合、2つの方法があり、n個の1xmタイルをすべて垂直方向とすべて水平方向に配置します。 nがmより大きい場合は、以前の方法を使用して方法を計算します-way [n-1] +Ways[m-1]。

• 床とタイルの寸法は整数mとnを取ります。

• 関数ways_tile_floor（int N、int M）は、寸法を取得し、1xmサイズのタイルを使用してサイズnxmの床をタイル張りする方法の数を返します。

• 長さN+1の配列arr[]を取得して、インデックスi=現在のNの値のタイルの数を格納します。

• arr [0]の場合、タイルは0になります。したがって、arr [0]=0です。

• i=1からi=Nまでのforループを使用してarr[]をトラバースします。各arr[i]について、i> Mの場合、前の値を使用してカウントを計算します。 arr [i] =arr [i − 1] + arr [i −M]。

• i =1またはi

• i =Mの場合、arr [i]=2を設定します。

• forループの最後に、arr[N]にはタイルを配置する方法がいくつかあります。

• 結果としてarr[N]を返します。

例

#include <bits/stdc++.h>
using namespace std;
int ways_tile_floor(int N, int M){
   int arr[N + 1];
   arr[0] = 0;
   for (int i = 1; i <= N; i++){
      if (i > M){
         arr[i] = arr[i − 1] + arr[i − M];
      }
      else if (i < M || i == 1){
         arr[i] = 1;
      } else {
         arr[i] = 2;
      }
   }
   return arr[N];
}
int main(){
   int n = 3, m = 2;
   cout<<"Count the number of ways to tile the floor of size n x m using 1 x m size tiles are: "<<ways_tile_floor(n, m);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count the number of ways to tile the floor of size n x m using 1 x m size tiles are: 3