剑指Offer-斐波那契数列

发表于 | 分类于

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39

解题思路

根据以往经验可以知道，计算斐波那契数列不适合用递归的写法，因此我并没有考虑写递归，而是书写了for循环的版本来替代。最开始的写法如下。这样的写法也对，但是相比另一种for循环版本而言，需要耗费一点点的存储空间，因此也有了第二种写法。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int Fibonacci(int n) {
        int temp[40];
        temp[0] = 0, temp[1] = 1;
        for(int i=2; i<=n; i++){
            temp[i] = temp[i-1] + temp[i-2];
        }
        return temp[n];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int Fibonacci(int n) {
        int first = 0, second = 1;
        int result=n; //!!!
        for(int i=2; i<=n; i++){
            result = first + second;
            first = second;
            second = result;
        }
        return result;
    }
};

这里需要注意的是，result应该要初始化，因为n可能等于0或1，而导致无法进入for循环。而n=0时result为0，n=1时result为1，因此比较适合于将result初始值设置为n。