求第n个斐波那契数

斐波那契数

斐波那契数，亦称之为斐波那契数列（意大利语： Successione di Fibonacci)，又称黄金分割数列、费波那西数列、费波拿契数、费氏数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，斐波那契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=Fn-1+Fn-2（n>=2，n∈N*），用文字来说，就是斐波那契数列由 0 和 1 开始，之后的斐波那契数列系数就由之前的两数相加。

首先介绍斐波那契数列，斐波那契数列的排列是：1，1，2，3，5，8，13，21，34，55，89，144……

递归法

递归即函数自己调用自己的方法

话不多说直接上代码

//1 1 2 3 5 8 13 21 34 55…

如上，当输入的n为前两位是结果为1，第n个斐波那契数等于它前边两个数之和，所以当n<=2时，返回值为1，n>2时就返回它之前的两位数求和，一直调用直到n为1或2时，这样就实现了自身调用自身的作用。

总结递归法求斐波那契数的思路：要求第n个斐波那契数就要先求它的n-1,n-2个斐波那契数，一直到我们给定的第一个第二个斐波那契数1，1，然后在加回去，依次来求解第n个斐波那契数。整体思路：倒序求解。

由此看来，当n过大时，代码的计算量还是很大的！

if (n <= 2)return 1;elsereturn fib(n - 1) + fib(n - 2);

完整代码

#include <stdio.h>#include <stdlib.h>int fib(int n){if (n <= 2)return 1;elsereturn fib(n - 1) + fib(n - 2);}int main(){int n = 0;scanf("%d", &n);int ret = fib(n);printf("第%d个斐波那契数是：%d \n", n,ret);system("pause");return 0;}

迭代法

关于迭代的百度定义如下：迭代法-百度百科本体思路如图：

先给定第一个第二个斐波那契数数值，第三个即为前两者之和。依次类推。

总结顺序求解！

while (n>2){c = a + b;a = b;b = c;n--;}

完整代码

#include <stdio.h>#include <stdlib.h>int fib(int n){int a = 1;int b = 1;int c = 0;while (n>2){c = a + b;a = b;b = c;n--;}return c;}int main(){int n = 0;scanf("%d", &n);int ret = fib(n);printf("第%d个斐波那契数是：%d \n", n,ret);system("pause");return 0;}