ให้ตัวเลขสองตัว 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
คำอธิบาย
ทางจะเป็นแบบเรียงต่อกัน 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
ถ้า n เท่ากับ m จะมี 2 วิธี คือ การวาง n 1xm ไทล์ในแนวตั้งและแนวนอนทั้งหมด ถ้า n มากกว่า m เราจะคำนวณวิธีโดยใช้วิธีก่อนหน้า −ways[n−1]+ways[m−1]
-
ใช้จำนวนเต็ม m และ n สำหรับขนาดของพื้นและกระเบื้อง
-
ฟังก์ชัน way_tile_floor(int N, int M) ใช้ขนาดและส่งคืนจำนวนวิธีในการปูกระเบื้องพื้นขนาด n x m โดยใช้ไทล์ขนาด 1 x ม.
-
ใช้อาร์เรย์ arr[ ] ของความยาว N+1 เพื่อเก็บจำนวนไทล์สำหรับดัชนี i=ค่าปัจจุบันของ N
-
สำหรับกระเบื้อง arr[0] จะเป็น 0 ดังนั้น arr[0]=0.
-
Traverse arr[] ใช้สำหรับการวนซ้ำจาก i=1 ถึง i=N สำหรับแต่ละ 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
