हमें n सीढ़ियां और 2 रंग (लाल और पीला) दिए गए हैं जिनसे इन सीढ़ियों को रंगा जाना है। हमारा कार्य उन तरीकों की संख्या गिनना है जिनसे हम सीढ़ियों को इस तरह रंग सकते हैं कि कोई दो लगातार सीढ़ियां पीले रंग की न हों।
उदाहरण
इनपुट
3
आउटपुट
5
व्याख्या
सीढ़ियों को रंगने के तरीके हैं: YRY, RYR, YRR, RRY, RRR. यहां R लाल रंग दर्शाता है, Y पीला रंग दर्शाता है।
इस समस्या को हल करने के लिए, आइए देखें कि सीढ़ियों को कितने तरीकों से रंगा जा सकता है।
N = 1, ways(1) = 2: R, Y
N = 2, ways(2) = 3: RY, YR, RR
N = 3, ways(3) = 5: RYR, YRY, RRY, YRR, RRR
N = 4, ways(4) = 8: YRYR, RYRY, RYRR, YRRY, YRRR, RRYR, RRRR, RRRY.
तो इन मामलों से, हम यह निकाल सकते हैं कि यह एक फिबोनाची श्रृंखला है जो 2 को पहले तत्व और 3 को दूसरे तत्व के रूप में शुरू करती है।
हमारे तर्क के कार्यान्वयन को दिखाने वाला प्रोग्राम:
उदाहरण
#include <iostream>
using namespace std;
int colorSteps(int n) {
int first = 2;
int next = 3;
for (int i = 3; i <= n; i++) {
next = first + next;
first = next - first;
}
return next;
}
int main() {
int n = 6;
cout << "Number of ways to color " << n << " steps is " << colorSteps(n);
return 0;
}
आउटपुट
Number of ways to color 6 steps is 21
