एन सीढ़ियाँ हैं। एक व्यक्ति पहली से नौवीं सीढ़ियों तक जाएगा। वह एक कदम में अधिकतम कितनी सीढ़ियाँ पार कर सकता है, यह भी दिया गया है। इस जानकारी से हमें नौवीं सीढ़ियों तक जाने के संभावित रास्ते तलाशने होंगे। आइए मान लें कि प्रत्येक चरण में अधिकतम दो सीढ़ियां पार की जा सकती हैं। तो हम इस समस्या को हल करने के लिए पुनरावर्ती संबंध पा सकते हैं। कोई भी nth सीढ़ी पर जा सकता है, या तो (n-1)th सीढ़ी से या (n-2)th सीढ़ी से। तो तरीके (एन) =तरीके (एन -1) + तरीके (एन -2)।
मान लीजिए सीढ़ियों की संख्या, मान लीजिए 10, सीढ़ियों की अधिकतम संख्या जो एक कदम में कूदी जा सकती है, मान लीजिए 2, तो आउटपुट 89 संभावित तरीकों से होगा।
इसे हल करने के लिए, इन चरणों का पालन करें -
- सीढ़ी संख्या के समान आकार की सरणी गणना परिभाषित करें
- गिनती[0] :=1
- के लिए मैं :=2 से सीढ़ी -1, करते हैं
- गिनती[i] :=0
- j =1 से i और j <=अधिकतम के लिए; करो
- गिनती[i] :=गिनती[i] + गिनती[i - j]
- वापसी की गिनती[सीढ़ी - 1]
आइए बेहतर ढंग से समझने के लिए कार्यान्वयन देखें
उदाहरण (C++)
#include<iostream>
using namespace std;
int stairClimbWays(int stair, int max){
int count[stair]; //fill the result stair using bottom up manner
count[0] = 1; //when there are 0 or 1 stair, 1 way to climb
count[1] = 1;
for (int i=2; i<stair; i++){ //for stair 2 to higher
count[i] = 0;
for(int j=1; j<=max && j<=i; j++)
count[i] += count[i-j];
}
return count[stair-1];
}
int countWays(int stair, int max){ //person can climb 1,2,...max stairs at a time
return stairClimbWays(stair+1, max);
}
int main (){
int stair, max;
cout << "Enter number of stairs: "; cin >> stair;
cout << "Enter max stair a person can climb: "; cin >> max;
cout << "Number of ways to reach: " << countWays(stair, max);
} इनपुट
Stairs = 10 Max stairs a person can climb: 2
आउटपुट
Enter number of stairs: 10 Enter max stair a person can climb: 2 Number of ways to reach: 89
