समस्या विवरण
दो संख्याएं n और m दी गई हैं जो कमरे के फर्श की लंबाई और चौड़ाई दर्शाती हैं। लक्ष्य उन तरीकों की संख्या गिनना है जिनसे इस फर्श को 1xm आकार की टाइलों का उपयोग करके टाइल किया जा सकता है।
उदाहरण
इनपुट
n=3 m=2
आउटपुट
फर्श को टाइल करने के तरीकों की संख्या: 3
व्याख्या
तीन 1x2 टाइलें नीचे दिखाए अनुसार व्यवस्थित होंगी:
इनपुट
n=3 m=3
आउटपुट
फर्श को टाइल करने के तरीकों की संख्या: 2
व्याख्या
तीन 1x3 टाइलें लंबवत और क्षैतिज रूप से व्यवस्थित। केवल दो तरीके।
दृष्टिकोण
इस दृष्टिकोण में हम n के मान की जांच करते हैं। यदि n, m से कम है और इसका मान 1 है तो 1xm आकार के फर्श पर केवल एक टाइल रखी जाएगी।
यदि n, m के बराबर है तो 2 तरीके होंगे: सभी n 1xm टाइलें लंबवत और सभी क्षैतिज रखना। यदि n, m से बड़ा है तो हम पिछले तरीकों का उपयोग करके तरीकों की गणना करेंगे: ways[n-1] + ways[n-m]।
एल्गोरिदम चरण
- फर्श और टाइलों के आयामों के लिए पूर्णांक
mऔरnलें। - फंक्शन
ways_tile_floor(int N, int M)आयाम लेता है और n x m आकार के फर्श को 1 x m आकार की टाइलों से टाइल करने के तरीकों की संख्या लौटाता है। - इंडेक्स
i=Nके वर्तमान मान के लिए टाइलों की गिनती संग्रहीत करने के लिए लंबाईN+1की सरणीarr[]लें। arr[0]के लिए टाइलें 0 होंगी। इसलिएarr[0]=0।forलूप का उपयोग करकेi=1सेi=Nतकarr[]को पार करें। प्रत्येकarr[i]के लिए, यदिi>Mतो पिछले मानों का उपयोग करके गिनती की गणना करें:arr[i] = arr[i-1] + arr[i-M]।- यदि
i=1याi<M, तोarr[i]को 1 से सेट करें। - यदि
i=M, तोarr[i]=2सेट करें। forलूप के अंत में,arr[N]में टाइलों को व्यवस्थित करने के तरीकों की गिनती होगी।- परिणाम के रूप में
arr[N]लौटाएं।
C++ कोड उदाहरण
#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 << "फर्श को टाइल करने के तरीकों की संख्या: " << ways_tile_floor(n, m);
return 0;
}
आउटपुट
फर्श को टाइल करने के तरीकों की संख्या: 3
