How to solve the staircase problem in C++

So what is the staircase problem? This is a pretty interesting one. let’s start learning how to solve the staircase problem in C++.

Suppose you are standing at the bottom of a staircase and you can take one, two or three steps at a time. How many possible ways are there you can reach the top?

Illustration:

Suppose there are 5 stairs and you have to go to the top. You can either choose to take one step at a time. so the sequence shall be 1, 1, 1, 1, 1. Now if you choose to do two steps at a time, the sequence will be 1,1,1,2 or 2,1,2 or 2,2,1 and so on.  If you choose to do three steps then the sequence will be 3,2 or 2,3 or 1,1,3 or 3,1,1 and so on. Now we have to make a program that helps us to find the number of steps one should take and the number of combinations of the steps we can take.

Example of staircase problem

Input : 4
Output: 
The ways these can be traversed are :
1 1 1 1
2 1 1
1 2 1
1 1 2
1 3
3 1
Hence there are 6 ways to climb the stairs.

Algorithm of the above code :

The program can be done using iteration too, but we are using recursion here.  This will make the program way easier to solve.

Stair_rec( stepsleft , stepsize)

  1. Check If stepsleft<0 then
  2. return 1
  3. end If
  4. Check If (stepsleft<0)
  5. return 0
  6. end if
  7. check if(stepsize =1) then
  8. c=c+Stair_rec(stepsleft-1, stepsize)
  9. end if
  10. check if(stepsize =2) then
  11. c=c+Stair_rec(stepsleft-2, stepsize)
  12. end if and so on….
  13. return c

Program to solve staircase problem in C++

#include<iostream>
using namespace std;
int stairrec(int steps,int stepsize)
{
    int c = 0;
    if(steps==0)            
        return 1;
   if(steps<0)
        return 0;
    if(stepsize==1)
        c=c+stairrec(steps-1,stepsize);      
    else if(stepsize==2)
    {
         c=c+stairrec(steps-1,stepsize);      
          c=c+stairrec(steps-2,stepsize);
    }
    else if(stepsize==3)
    {
         c=c+stairrec(steps-1,stepsize);       
         c=c+stairrec(steps-2,stepsize);       
         c=c+stairrec(steps-3,stepsize);      
    }
    else if(stepsize==3)
    {
         c=c+stairrec(steps-1,stepsize);       
         c=c+stairrec(steps-2,stepsize);       
         c=c+stairrec(steps-3,stepsize);      
         c=c+stairrec(steps-4,stepsize);      
    }
    return c;
}
int main()
{
    
    int n,j;
    cout<<"Enter number of stairs"<<endl;
    cin>>n;
    cout<<"Input the number of steps the person can take at a time(max 4) : ";
    cin>>j;
    cout<<"No of ways to climb stairs are : ";
    cout<<stairrec(n,j)<<endl;
    return 0;
}

The output of the above program:

 

solve staircase problem in C++

Also read:

Leave a Reply

Your email address will not be published. Required fields are marked *