একটি ঘরের মেঝের দৈর্ঘ্য এবং প্রস্থের প্রতিনিধিত্বকারী দুটি সংখ্যা 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 পূর্ণসংখ্যা নিন।
-
ফাংশন উপায়_টাইল_ফ্লোর(int N, int M) মাত্রা নেয় এবং 1 x m আকারের টাইলস ব্যবহার করে n x m আকারের মেঝে টাইল করার উপায়ের সংখ্যা প্রদান করে।
-
সূচক i=বর্তমান মানের জন্য টাইলসের গণনা সঞ্চয় করতে N+1 দৈর্ঘ্যের একটি অ্যারে অ্যারে নিন।
-
arr[0] টাইলসের জন্য 0 হবে। সুতরাং arr[0]=0.
-
ট্রাভার্স 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.
সেট করুন -
ফর লুপের শেষে, 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
