I really need help with this problem please. Must be written in C++ Suppose a st
ID: 3844480 • Letter: I
Question
I really need help with this problem please.
Must be written in C++
Suppose a stair way has N steps where N is a positive integer. How many different ways can you up the stair way if, as you up, sometimes you go up one stair step with one step or you go up two stair step with one step.
Suppose the stair way has 3 steps then you can up the stair way
three different ways:
1,1,1 = 3 steps
1,2 = 3 steps
2, 1 = 3 steps
Suppose the stair way has 4 steps then you can up the stair way
five different ways
1,1,1,1 = 4 steps
1,1,2 = 4 steps
1,2,1 = 4 steps
2, 1,1, = 4 steps
2,2 = 4 steps
Write a recursive function to solve the problem.
The function, f, will contain statements that will look like,
...
return f(N-1) + f(N-2)
Write a program to test the function with many, different values of N.
Explanation / Answer
Before I give away the code, lets look it logically, if I can reach to a stair n from n-1 stair for n-2 stair, for n =1, we have got only one way, for n = 2 we have got 2 ways, directly or from step one, for n =3 three ways as given in the question, so this as you see closely is generating a fibonnaci sequence, 1,1,2,3.. i.e. if number of stair is 2 then fibonacci(3) is the answer. The same logic has been applied in the program. Have a look and let me know if you have any doubts:
#include<iostream>
using namespace std;
int num(int a)
{
if (a <= 1)
return a;
return num(a-1) + num(a-2); //returning the fibonacci number
}
int stairs(int b)
{
return num(b + 1); //counting number of ways
}
int main ()
{
int check = 4; //write as many values as you can
cout <<"For "<<check<<" stairs: ";
cout<<"Number of ways = " <<stairs(check) << " "; //directly prints the number of way
return 0;
}