Đếm số cách lát sàn kích thước n x m dùng gạch 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 sàn phòng. Mục tiêu là đếm số cách lát sàn này bằng gạch kích thước 1xm.

Ví dụ

Đầu vào

n=3 m=2

Đầu ra

Số cách lát sàn kích thước n x m dùng gạch 1 x m là: 3

Giải thích

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

Đầu vào

n=3 m=3

Đầu ra

Số cách lát sàn kích thước n x m dùng gạch 1 x m là: 2

Giải thích

Các cách sẽ là ba gạch 1x3 được sắp xếp dọc và ngang. Chỉ có 2 cách.

Phương pháp sử dụng

Trong phương pháp này, chúng ta 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 gạch được đặt trải toàn bộ sàn kích thước 1xm.

Nếu n bằng m thì sẽ có 2 cách: đặt n gạch 1xm toàn bộ dọc và toàn bộ ngang. Nếu n lớn hơn m thì chúng ta sẽ tính số cách dùng các cách trước đó: ways[n-1] + ways[n-m].

• Nhận số nguyên m và n cho kích thước sàn và gạch.
• Hàm ways_tile_floor(int N, int M) nhận kích thước và trả về số cách lát sàn kích thước n x m dùng gạch 1 x m.
• Tạo mảng arr[] độ dài N+1 để lưu số lượng gạch cho chỉ số i=giá trị hiện tại của N.
• Đối với arr[0] số gạch sẽ là 0. Vậy arr[0]=0.
• Duyệt arr[] bằng vòng lặp for từ i=1 đến i=N. Với mỗi arr[i], nếu i > M thì tính số cách dùng giá trị trước. arr[i] = arr[i-1] + arr[i-M].
• Trong trường hợp i=1 hoặc i < M, đặt arr[i] bằng 1.
• Trong trường hợp i=M, đặt arr[i]=2.
• Cuối cùng của vòng lặp for, arr[N] sẽ có số cách sắp xếp gạch.
• Trả về arr[N] làm kết quả.

Ví dụ mã

#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 << "Số cách lát sàn kích thước n x m dùng gạch 1 x m là: " << ways_tile_floor(n, m);
    return 0;
}

Đầu ra

Nếu chạy mã trên, sẽ tạo ra đầu ra sau:

Số cách lát sàn kích thước n x m dùng gạch 1 x m là: 3