दो नंबर 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 के बराबर है, तो n 1xm टाइलों को सभी लंबवत और सभी क्षैतिज रूप से रखकर 2 तरीके होंगे। अगर n, m से बड़ा है तो हम पिछले तरीकों का उपयोग करके तरीकों की गणना करेंगे - तरीके[n−1]+तरीके[m−1]।
-
फर्श और टाइलों के आयामों के लिए पूर्णांक m और n लें।
-
Functionways_tile_floor(int N, int M) आयाम लेता है और 1 x m आकार की टाइलों का उपयोग करके n x m आकार के फर्श को टाइल करने के तरीकों की संख्या देता है।
-
अनुक्रमणिका i=N के वर्तमान मान के लिए टाइलों की संख्या संग्रहीत करने के लिए लंबाई N+1 की एक सरणी arr[ ] लें।
-
गिरफ्तारी के लिए [0] टाइलें 0 होंगी। तो गिरफ्तार करें [0] =0।
-
ट्रैवर्स एआर [] लूप के लिए i =1 से i =N तक का उपयोग कर रहा है। प्रत्येक गिरफ्तारी [i] के लिए, यदि i>M तो पिछले मानों का उपयोग करके गणना की गणना करें। arr[i]=arr[i − 1] + arr[i − M].
-
मामले में i=1 और या i
-
मामले में i=M, arr[i]=2 सेट करें।
-
लूप के अंत में, 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