Đếm số cách lát nền có kích thước n x m bằng cách sử dụng gạch có kích thước 1 x m trong C ++

Cho hai số n và m đại diện cho chiều dài và chiều rộng của tầng của một căn phòng. Mục đích là để đếm số cách có thể lát sàn này bằng cách sử dụng gạch có kích thước 1Xm.

Ví dụ

Đầu vào

n=3 m=2

Đầu ra

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

Giải thích

Các cách sẽ là ba ô 1x2 được sắp xếp như hình bên dưới -

Đầu vào

n=3 m=3

Đầu ra

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

Giải thích

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

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -

Trong cách tiếp cận này, chúng tôi kiểm tra giá trị của n. Nếu n nhỏ hơn m và có giá trị 1 thì sẽ chỉ có một viên gạch được đặt trên toàn sàn có kích thước 1Xm.

Nếu n bằng m thì sẽ có 2 cách đặt n viên gạch 1xm theo chiều dọc và theo chiều ngang. Nếu n lớn hơn m thì chúng ta sẽ tính các cách bằng các cách trước đó - cách [n − 1] + cách [m − 1].

• Lấy số nguyên m và n cho kích thước của sàn và gạch.

• Hàm styles_tile_floor (int N, int M) nhận các kích thước và trả về số lượng các cách lát nền nhà có kích thước n x m bằng cách sử dụng các viên gạch kích thước 1 x m.

• Lấy một mảng arr [] có độ dài N + 1 để lưu trữ số lượng ô cho chỉ số i =giá trị hiện tại của N.

• Đối với arr [0] ô sẽ là 0. Vì vậy, arr [0] =0.

• Traverse arr [] sử dụng vòng lặp for từ i =1 đến i =N. Đối với mỗi arr [i], nếu i> M thì tính số đếm bằng cách sử dụng các giá trị trước đó. arr [i] =arr [i - 1] + arr [i - M].

• Trong trường hợp i =1 và hoặc i

• Trong trường hợp i =M, hãy đặt arr [i] =2.

• Ở cuối vòng lặp for, arr [N] sẽ có một số cách sắp xếp các ô.

• Kết quả là trả về arr [N].

Ví dụ

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

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