Home » C++ programs

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

Here, we are going to implement a C++ program to solve the staircase problem.
Submitted by Indrajeet Das, on December 14, 2018

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.

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





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.
Learn PCB Designing: PCB DESIGNING TUTORIAL




Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.