Q:

Stair Case: C++ program to solve the staircase problem

0

A child is running up a staircase with N steps, and can hop 1 step, 2 steps or 3 steps at a time. Implement a method to count how many possible ways the child can run up to the stairs? You need to return number of possible ways W.

Input format: Line 1: Integer N (No. of steps)

Output Format: Line 1: Integer W i.e. Number of possible ways

Constraint: (1 <= N <= 30)

Sample Input 1: 4

Sample Output: 7

Explanation:

In this question, to find out the number of ways to we can climb the stairs, we can use a recursive method to solve it. We can call the recursive function thrice in our code with parameters of (N-1)(N-2) and (N-3) steps (the decrease in steps show the number of steps climbed). And add and return them.

It is one of the typical questions for recursive algorithms.

All Answers

need an explanation for this answer? contact us directly to get an explanation for this answer

Algorithm:

  1. Step 1: Declare a recursive function staircase with one parameter (int steps).
  2. Step 2: Base Case:
    if(steps <0) // No steps to climb
    return 0;
  3. Step 3: Base Case 2:
    if(steps ==0) //Already reached top
    return 1;
  4. Step 4: Return staircase (steps -1) + staircase (steps – 2) + staircase (steps -3).
    i.e. the total ways in which we can climb the steps.

Example:

    For stairs = 3.
    Ways to climb are,
    1 1 1
    1 2
    2 1
    3
    Hence there are four ways to climb.

C++ program:

#include<bits/stdc++.h>

using namespace std;

//Recursive Function
int staircase(int n){
    if(n<0){            //Base Case 1
        return 0;
    }

    if(n==0){           //Base Case 2
        return 1;
    }

    int count = 0;
    count += staircase(n-1);    //Stepping 1 step
    count += staircase(n-2);    //Stepping 2 step
    count += staircase(n-3);    //Stepping 3 step

    return count;
}


//Main 
int main(){
    int n;
    cout<<"Enter number of stairs"<<endl;
    cin>>n;
    
    cout<<"No of ways to climb stairs are ";
    cout<<staircase(n)<<endl;

    return 0;

}

Output

 
Enter number of stairs
5
No of ways to climb stairs are 13

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Similar questions


need a help?


find thousands of online teachers now