用C 语言实现斐波那契数列

斐波那契数列（Fibonacci sequence），又称“黄金分割”数列，比如这样一个数列：1，1，2，3，5，8，13，21，34，55，89… …数列从第3项开始，每一项都等于前两项之和。在C语言中，我们可以用多种方式来实现斐波那契数列。本文针对以下三种方式来体现每种方法的效率：1）递归，2）非递归，3）数组。

1. 递归。该递归属于多分支递归，会造成栈溢出。

//递归#includeint Fib(int n){if(n==1||n==2)//数列前两项{return 1; }else//从第三项开始{return Fib(n - 1) + Fib(n - 2);}return 0;}int main(){int n = 0;scanf("%d", &n);//输入一个数int ret = Fib(n);//计算斐波那契数列printf("%d\n", ret);//打印结果return 0;}

2）非递归。非递归较递归效率更高，避免了重复计算的时间和空间。

//非递归int main() {int n = 0;printf("请输入一个整数：");scanf("%d", &n);if (n == 1||n==2) {return 1;}else {int f1 = 1;int f2 = 1;int f3 = -1;for (int i = 3; i <= n; i++) {f3 = f1 + f2;f1 = f2;f2 = f3;}printf("该整数的Fib数列为%d", f3);}return 0;}

3）数组。

//数组法#includeint Fib(int n){int i;int arr[100] = {0,1,1};for (i = 2; i <= n; i++)//从第一项开始{arr[i] = arr[i - 1] + arr[i - 2];}return arr[n];}int main(){int n;scanf("%d", &n);printf("%d", Fib(n));return 0;}