两种方法计算斐波那契数列第n项

百度斐波那契数列定义：

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1) F(n - 2)（n ≥ 2，n ∈ N*）

方法一：递归

思路：创建一个计算第n项斐波那契数的函数，通过不断调用此函数计算(n-1),(n-2),(n-3)....2然后一次返回到第n向。下面展示代码：

1.  
   #define _CRT_SECURE_NO_WARNINGS
2.  
   #include<stdio.h>
3.  
   int Fib(int n)
4.  
   {
5.  
   if (n <= 2)
6.  
   return 1;
7.  
   else
8.  
   return Fib(n - 1) Fib(n - 2); //递归计算(n-1)，(n-2)项
9.  
   }
10.  
    int main()
11.  
    {
12.  
    int n = 0;
13.  
    printf("请输入想要计算的第几项:>");
14.  
    scanf("%d", &n);
15.  
    int ret = Fib(n); //创建Fib()函数并用变量ret接收返回值
16.  
    printf("%d", ret);
17.  
    return 0;
18.  
    }

运行效果：

 这里我们计算第10项的值，那么我们计算第50项值呢？

 这并不是程序崩溃的原因，这是电脑还在计算，那么为什么计算第50项所耗时间这么久呢？

 这里我们画了一个简图描述这个算法，我们计算第50项的话，要不断重复计算第3项，第4项......第48项，且项数越小被计算次数越多。所以这种算法不建议计算较大的数值！！！

方法二：迭代

思路：通过循环(n-2) (n-1)=(n)(n>2)这个表达式计算第n项数值，每循环一次赋值一次如(n-2)->(n-1),(n-1)->(n)然后在计算下一项。下面展示代码：
 

1.  
   #define _CRT_SECURE_NO_WARNINGS
2.  
   #include<stdio.h>
3.  
   int Fib(int n)
4.  
   {
5.  
   int a = 1;
6.  
   int b = 1;
7.  
   int sum = 0;
8.  
   if (n <= 2)
9.  
   return 1;
10.  
    else
11.  
    {
12.  
    while (n > 2)
13.  
    {
14.  
    sum = a b;
15.  
    a = b;
16.  
    b = sum;
17.  
    n--;
18.  
    }
19.  
    return sum;
20.  
    }
21.  
    }
22.  
    int main()
23.  
    {
24.  
    int count = 0;
25.  
    int n = 0;
26.  
    printf("请输入想要计算的第几项:>");
27.  
    scanf("%d", &n);
28.  
    int ret = Fib(n); //创建Fib()函数并用变量ret接收返回值
29.  
    printf("%d", ret);
30.  
    return 0;
31.  
    }

运行效果：

这种方法并不会重复计算某一项的值，所有算法耗时少，效率高。

总结：

     在我们写代码的过程中，递归递归固然能简化代码步骤，但有时候也不一定很合适，所有我们要选择写代码要选择最优的算法去解决问题。如果这篇文章有帮助到大家请大家动动小手点个赞加个关注吧，如果还要不足请大家评论区指出我会改正进步，谢谢大家阅读！

这篇好文章是转载于：学新通技术网