1386 - Fibonacci

The Fibonacci Numbers{0,1,1,2,3,5,8,13,21,34,55...} are defined by the recurrence:

F0=0 F1=1 Fn=Fn-1+Fn-2,n>=2
Write a program to calculate the Fibonacci Numbers.

Input

Each case contains a number n and you are expected to calculate Fn.(0<=n<=30) 。

Output

For each case, print a number Fn on a separate line,which means the nth Fibonacci Number.

Examples

Input

Output

Solution C

#include<stdio.h>
int main()
{   
    int i,n,a[31];
    while(scanf("%d",&n)!=EOF)
	{ 
		a[0]=0;
		a[1]=1;
		for(i=2;i<=n;i++)
			a[i]=a[i-1]+a[i-2];
		printf("%d\n",a[n]);
	}   
  return 0;
}

Solution C++

#include <stdio.h>

int Fibonacci(int n){
	if(n==0){
		return 0;
	}else if(n <= 2){
		return 1;
	}else{
		return Fibonacci(n-1) + Fibonacci(n-2);
	}
}

int main(){
    int f[33] = {0, 1, 1};
    for(int i=3; i<=30; i++){
        f[i] = f[i-1] + f[i-2];
    }
    int n;
    while(scanf("%d", &n) != EOF){
        printf("%d\n", f[n]);
    }

    return 0;
}

Time Limit	1 second
Memory Limit	32 MB

Discuss Stats

上一题下一题