Java教程

七周打卡剑指offer《斐波那契数列》

本文主要是介绍七周打卡剑指offer《斐波那契数列》,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

斐波那契数列

题目描述

输入一个整数 n ,求斐波那契数列的第 n 项。

假定从 0 开始,第 0 项为 0。(n≤39)

样例

输入整数 n=5 

返回 5

题解

斐波那契数列:前两项为1, 从第三项之后,每一项的纸是前两项的和
f ( x ) = { 1 , x = 1 1 , x = 2 f ( x − 1 ) + f ( x − 2 ) , x > 2 f(x) = \begin{cases} 1, &\text{x = 1} \\ 1, &\text{x = 2} \\ f(x-1) + f(x-2), & \text{x > 2} \end{cases} f(x)=⎩⎪⎨⎪⎧​1,1,f(x−1)+f(x−2),​x = 1x = 2x > 2​

直接递推即可,数据量也没有爆, 不用高精度

class Solution {
public:
    int Fibonacci(int n) {
        int f[41] = {0};
        f[1] = 1, f[2] = 1;
        for (int i = 3; i <= n; i ++)
            f[i] = f[i-1] + f[i-2];
        
        return f[n];
    }
};
这篇关于七周打卡剑指offer《斐波那契数列》的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!