हमें n सीढ़ियाँ और 2 रंग (लाल और पीला) दिए गए हैं जिनसे इन सीढ़ियों को रंगना है। हमारा काम उन तरीकों की संख्या गिनना है जिनसे हम सीढ़ियों को इस तरह से रंग सकते हैं कि कोई भी लगातार दो कदम पीले रंग के न हों।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
3
आउटपुट
5
स्पष्टीकरण
The ways in which stairs can be painted are YRY, RYR, YRR, RRY, RRR. here R denotes red color, Y denotes yellow color.
इस समस्या को हल करने के लिए, आइए देखें कि सीढ़ियों को कितने तरीकों से रंगा जा सकता है।
एन =1, तरीके(1) =2:आर, वाई
एन =2, तरीके (2) =3 :आरवाई, वाईआर, आरआर
एन =3, तरीके(3) =5 :आरवाईआर, वाईआरवाई, आरआरवाई, वाईआरआर, आरआरआर
एन =4, तरीके(4) =8:वाईआरवाईआर, आरवाईआरई, आरवाईआरआर, वाईआरआरवाई, वाईआरआरआर, आरआरवाईआर, आरआरआरआर, आरआरआरई।
तो इन मामलों से, हम यह व्युत्पन्न कर सकते हैं कि यह एक फिबोनाची श्रृंखला है जिसमें 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