นับวิธีปูกระเบื้องพื้นขนาด n x m ด้วยกระเบื้อง 1 x m ใน C++

ได้รับตัวเลขสองจำนวน n และ m แทนความยาวและความกว้างของพื้นห้อง เป้าหมายคือนับจำนวนวิธีที่สามารถปูพื้นนี้ได้โดยใช้กระเบื้องขนาด 1×m

ตัวอย่าง

Input

n=3 m=2

Output

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

Explanation

วิธีการจะเป็นการจัดกระเบื้อง 1x2 สามชิ้น ตามรูปด้านล่าง

Input

n=3 m=3

Output

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

Explanation

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

วิธีการที่ใช้ในโปรแกรม

วิธีนี้ตรวจสอบค่า n ถ้า n น้อยกว่า m และมีค่า 1 จะมีเพียงหนึ่งชิ้นที่จะวางทั่วพื้นขนาด 1×m

ถ้า n เท่ากับ m จะมี 2 วิธี คือ วาง n ชิ้น 1×m แนวตั้งทั้งหมด และแนวนอนทั้งหมด ถ้า n มากกว่า m จะคำนวณวิธีจากวิธีก่อนหน้า: ways[n-1] + ways[m-1]

• รับจำนวนเต็ม m และ n สำหรับขนาดพื้นและกระเบื้อง
• ฟังก์ชัน ways_tile_floor(int N, int M) คืนค่าจำนวนวิธีปูพื้น
• สร้างอาร์เรย์ arr[] ความยาว N+1 เก็บจำนวนวิธีสำหรับ index i = ค่า N ปัจจุบัน
• สำหรับ arr[0] จำนวนกระเบื้องเป็น 0 ดังนั้น arr[0]=0
• วนลูป arr[] จาก i=1 ถึง N สำหรับแต่ละ arr[i] ถ้า i > M คำนวณจากค่าก่อนหน้า arr[i] = arr[i-1] + arr[i-M]
• กรณี i=1 หรือ i < M ตั้ง arr[i] = 1
• กรณี i=M ตั้ง arr[i] = 2
• เมื่อลูปจบ 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;
}

Output

หากรันโค้ดข้างต้นจะได้ผลลัพธ์ดังนี้:

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