题目链接地址： ?pid=1387
题目1387：斐波那契数列
时间限制：1 秒内存限制：32 兆特殊判题：否提交：6515解决：1952 题目描述： 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。斐波那契数列的定义如下：
输入： 输入可能包含多个测试样例，对于每个测试案例， 输入包括一个整数n(1<=n<=70)。 输出： 对应每个测试案例，， 输出第n项斐波那契数列的值。 样例输入： 3 样例输出： 2
思路分析：
效率很低的递归解法： 根据斐波那契数列公式，我们很快就能想到递归的解法并写出以下代码：
long long Fibonacci(int n){if(0 == n)return 0;else if(1 == n)return 1;elsereturn Fibonacci(n – 1) +Fibonacci(n – 2);}
上述递归解法有很严重的效率问题。我测试过n为100时，很久也没有出来结果。同时360加速球迅速暴涨，吃内存了。 为什么递归的效率低？ 因为递归运算中存在着很多“重复计算”同一个函数，计算量会随着n的增大而迅速增大。 同时递归就是函数反复调用自身，需要不断地申请和释放栈空间（保存参数，返回地址等），从而增加了时间和空间开销。而且每个进程的栈空间是有限的，当递归调用的层次太多，就会超过栈的容量，最后导致调用栈溢出。 只能采用循环法来解决问题。 从下往上计算 根据斐波那契数列的第0项和第1项相加得到斐波那契数列的第2项，通过第1项与第2项相加得到第3项，… … 依次类推，我们就可以通过第n – 2项与第n – 1项相加得到第n项的斐波那契数列。这样的时间复杂度是O(n)。 避免了递归算法中的“重复计算”，而且又不需要额外申请和释放栈空间。
时间复杂度为O(n)。 空间复杂度O(1)。
代码：/【剑指Offer面试题】 九度OJ1387：斐波那契数列———————————– Author:牧之丶 Date：2015年Email:bzhou84@163.com */ using namespace std;#define N 75long long fi[N];long long Fibonacci(int n){}int main(){}/***/注意点：1. 用递归会超时，递归解法有很多重复计算。2. 结果要用long long保存，不然会发生结果的溢出3. long long 输出为 %lld。VC++6.0下编译的，long long用_int64代替， %lld用%I64d代替。
记录沿途的心情。那样的生活才是我想要的。
