Given 1,2,3,4,...N numbers, count the number of ways to reach N

Given 'N', an integer of the form 1,2,3,4,.....N, You have to count the number of ways to reach N. Note that you can jump either '1' value or '2' values at a time.



Method 1:

To use the (N-1)th Fibonacci series would give the solution.i.e., count of the number of ways to reach N.


Implementation:


#include <stdio.h>
int calfibo(int N)
{
 if(N==0)
 return 0; // Recursive break for N=0 

 if(N==1)
 return 1; // Recursive break for N=1
          /* Recursive tree for 6 would be

         adding recursive breaks of '0' & '1' we get,
         calfibo(6) = calfibo(1) + calfibo(1) + calfibo(1) + calfibo(1) + calfibo(1) +  
                             calfibo(1) + calfibo(1) + calfibo(1)
                         = 8     */
 return calfibo(N-1)+calfibo(N-2);
} 
int main()
{
    int T,out,N;
    scanf("%d",&T); //Number of Test cases
    while(T--)
    {
     scanf("%d",&N); // Total number to reach N
     out=calfibo(N+1);
     printf("%d\n",out);
    }
    return 0;
}

Sample Input

2

2
4

Sample Output


2

5