C++ में सीढ़ी चढ़ना

n सीढ़ियाँ हैं। एक व्यक्ति 1वीं से nवीं सीढ़ी तक जाएगा। एक चरण में वह अधिकतम कितनी सीढ़ियाँ पार कर सकता है, यह भी दिया गया है। इस जानकारी के साथ, हमें nवीं सीढ़ी तक जाने के संभावित तरीके ढूंढने हैं। आइए मान लें कि कोई एक चरण में अधिकतम दो सीढ़ियाँ पार कर सकता है। तो हम इस समस्या को हल करने के लिए पुनरावर्ती संबंध ढूंढ सकते हैं। कोई nवीं सीढ़ी तक या तो (n-1)वीं सीढ़ी से या (n-2)वीं सीढ़ी से जा सकता है। तो ways(n) = ways(n-1) + ways(n-2)।

मान लीजिए सीढ़ियों की संख्या, मान लें 10, एक चरण में चढ़ी जा सकने वाली अधिकतम सीढ़ियाँ, मान लें 2, तो आउटपुट 89 संभावित तरीके होंगे।

इसे हल करने के लिए, इन चरणों का पालन करें -

• सीढ़ी संख्या के समान आकार का ऐरे count परिभाषित करें
• count[0] := 1
• for i := 2 to stair - 1, do
  • count[i] := 0
  • for j = 1 to i and j <= max; do
    • count[i] := count[i] + count[i - j]
• count[stair - 1] लौटाएं

बेहतर समझ के लिए कार्यान्वयन देखें

उदाहरण (C++)

#include<iostream> 
using namespace std; 

int stairClimbWays(int stair, int max){ 
    int count[stair]; //परिणाम को बॉटम-अप तरीके से भरें 
    count[0] = 1; //जब 0 या 1 सीढ़ी हो, तो चढ़ने का 1 तरीका 
    count[1] = 1; 
    
    for (int i = 2; i < stair; i++){ //सीढ़ी 2 से ऊपर के लिए 
        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){ 
    //व्यक्ति एक बार में 1,2,...max सीढ़ियाँ चढ़ सकता है 
    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