斐波那契数

什么是斐波那契数？

斐波那契数列（Fibonacci sequence），又称黄金分割数列。斐波那契数列的排列是：1，1，2，3，5，8，13，21，34，55，89，144…

依次类推下去，你会发现，它后一个数等于前面两个数的和。在这个数列中的数字，就被称为斐波那契数。例如：2是第3个斐波那契数。

实现方法

非递归方法

#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>Feibona(int n){int k = 0;int a1 = 1;int a2 = 1;if (n == 1 || n == 2) //n=1或n=2是的斐波那契数为1{k = 1;}elsewhile (n > 2) //n>2时循环，直到n<=2结束{k = a1 + a2;a1 = a2;a2 = k;n--;}return k;}int main(){int n = 0;scanf("%d",&n);Feibona(n);printf("%d\n", Feibona(n));return 0;}

递归方法

#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>Feibona(int n){if (n == 1 || n == 2){return 1;//返回1}elseif (n > 2){n--;Feibona(n);return Feibona(n) + Feibona(n - 1);//返回前两个数之和}}int main(){int n = 0;scanf("%d",&n);Feibona(n);printf("%d\n", Feibona(n));}

小结

求斐波那契数有两种方法，两种方法有优劣之分。用递归的方法比较简单，代码也少，但是计算时间长，因为要不停的调自身函数，所以需要的时间多，效率低下，不建议使用；用非递归的方法虽然代码多，但效率更高