剑指offer刷题笔记之——斐波那契数列

题目描述

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

问题分析

斐波那契额数公式为f(n) = f(n-1) + f(n-2),其中f(0) = 0, f(1) = 1。那么拿到这一题,首先想到的是递归。但是递归很明显会出现空间内存不够的情况。那么根据公式,使用最简单的迭代法即可。

思路

  1. 如果n = 0 或n = 1,返回对应值
  2. 如果n = 2,则遍历到n所有的数,按照公式理解即可

代码

C++代码

class Solution {
public:
    int Fibonacci(int n) {
        if(n == 0)
            return 0;
        if(n == 1)
            return 1;
        int numfn1 = 0, numfn2 = 1;
        int currentnum;
        for(int i = 2; i <= n; i++)
        {
            currentnum = numfn1 + numfn2;
            numfn1 = numfn2;
            numfn2 = currentnum;
        }
        return currentnum;
    }
};
发表新评论