斐波那契数列

斐波那契数列的几种不同的算法实现：
 1 #include "stdio.h"
 2 #include "math.h"
 3 
 4 
 5 int Fibonacci1(int n,int acc1,int acc2)//另一种新的递归方法T(n)=O(n)
 6 {
 7     if(n==0)return 0;
 8     if (n < 2)
 9         return acc1;
10     else
11         return Fibonacci1(n-1,acc2,acc1+acc2);
12 }
13 
14 int Fibonacci2(int n)//以前用的递归T(n)=O(2^n)
15 {
16     if(n==0)return 0;
17     if(n<=2)
18         return 1;
19     else
20         return Fibonacci2(n-1)+Fibonacci2(n-2);
21 }
22 
23 int Fibonacci3(int n){//直接使用迭代，T(n)=O(n)
24     int a,b,k,s;
25     a=0;b=1;s=0;
26     if(n==0)return 0;
27     if(n==1)return 1;
28     for(k=2;k<=n;k++){
29         s=a+b;
30         a=b;
31         b=s;
32     }
33     return s;
34 }
35 int Fibonacci4(int n){//公式法，其中含有幂函数，估计T(n)=O(n);
36     double i,j,s;
37     i=(1+sqrt(5))/2;
38     j=(1-sqrt(5))/2;
39     s=(pow(i,n)-pow(j,n))/sqrt(5);
40     return s;
41 }
42 
43 int main(void)
44 {
45     int n, rs;
46 
47     printf("请输入斐波那契数n：");
48     scanf("%d",&n);
49 
50     rs = Fibonacci1(n, 1, 1);
51     //rs=Fibonacci2(n);
52     //rs=Fibonacci3(n);
53     //rs=Fibonacci4(n);
54     printf("%d ", rs);
55 
56     return 0;
57 }