https://www.codechef.com/TNP72021/problems/TNP704

varghesebabu · February 1, 2021, 5:03pm

#PROBLEM LINK:-CodeChef: Practical coding for everyone

QUESTION:
Bonnie is a young stag who is always hungry for more food. Once as he was roaming through the jungle,he saw a stable on a huge tree top, full of the food he loved .He rushed to the stable,but at the entrance he was stopped by a spirit.It told him that,if he answered a question,he could have all the food.

SPIRIT:- There are “N”steps to reach the treetop.If you could hop 1 step,2 steps or 3 steps at a time,then tell me how many possible ways(W) you can reach there.
Please help out our Bonnie to have his favourite food.

INPUT FORMAT: OUTPUT FORMAT:
Line 1: Integer N (No. of steps) Line 1: Integer W i.e. Number of possible ways

CONSTRAINT:
(1 <= N <= 30)

SAMPLE INPUT: SAMPLE OUTPUT:
5 13
10 274

#QUICK EXPLANATION:-
In this question, to find out the number of ways Bonnie 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.
#EXPLANATION:-
It is one of the typical questions for recursive algorithms.The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function. Using recursive algorithm, certain problems can be solved quite easily. Recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. Such problems can generally be solved by iteration, but this needs to identify and index the smaller instances at programming time.Here we 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).This result is then added and returned to give the output.
ALGORITHM:
Step 1: Declare a recursive function staircase with one parameter (int steps).
Step 2: Base Case:
if(steps <0) // No steps to climb
return 0;
Step 3: Base Case 2:
if(steps ==0) //Already reached top
return 1;
Step 4: Return staircase (steps -1) + staircase (steps – 2) + staircase (steps -3).
i.e. the total ways in which we can climb the steps.

CODE:

Setter's Solution

#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;

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

Tester's Solution

Same Person

Editorialist's Solution

Same Person