剑指offer07

剑指offer07：斐波那契数列

题目描述

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

解法一：基于for循环和双标记

class Solution {
public:
    int Fibonacci(int n) {
        if (n == 0)
            return 0;
        else if (n == 1)
            return 1;
        int answer = 0;
        int first = 0, second = 1;
        for (int i = 2; i <= n; i++)
        {
            answer = first + second;
            first = second;
            second = answer;
        }
        return answer;
    }
};

解法二：基于vector的循环

class Solution2 {
public:
    int Fibonacci(int n) {
        vector<int> a(n + 1, 0);
        a[0] = 0;
        a[1] = 1;
        for (int i = 2; i <= n; i++)
        {
            a[i] = a[i - 1] + a[i - 2];
        }
        return a[n];
    }
};

解法三：基于动态规划的方法

class Solution3
{
public:
    int Fibonacci(int n) {
        int f = 0, g = 1;
        while (n-->0) {
            g += f;
            f = g - f;
        }
        return f;
    }
};

main函数

#include "stdafx.h"
#include <vector>
#include <iostream>
using namespace std;

int main()
{
    int n;
    cout << "请输入n：" << endl;
    cin >> n;
    Solution a;
    cout << "斐波那契数数列第" << n << "项是：" << a.Fibonacci(n)<<endl;

    system("pause");
    return 0;
}