斐波那契数列

[编程题]斐波那契数列

热度指数：1292900 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。

斐波那契数列是一个满足 $fib(x)=\left\{ \begin{array}{rcl} 1 & {x=1,2}\\ fib(x-1)+fib(x-2) &{x>2}\\ \end{array} \right.$ 的数列

数据范围： $1\leq n\leq 40$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$ ，本题也有时间复杂度 $O(logn)$ 的解法

输入描述:

一个正整数n

输出描述:

输出一个正整数。

示例1

输入

输出

说明

根据斐波那契数列的定义可知，fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3，所以答案为3。

示例2

输入

输出

示例3

输入

输出

算法知识视频讲解

推荐

fanhk

c++动态规划版

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

编辑于 2015-06-19 17:21:55 回复(110)

Typescript

神奇的小白离上岸不远了

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * @param n int整型
 * @return int整型
 */
export function Fibonacci(n: number): number {
    // write code here
    //if (n <= 2) return 1;
    let f1 = 1;
    let f2 = 1;
    for (let i = 3; i <= n; i++) {
        if (f1 > f2) f2 += f1;
        else f1 += f2;
    }
    return Math.max(f1, f2);
}

发表于 2023-02-11 17:21:48 回复(0)

Typescript

`twinkle

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param n int整型 
 * @return int整型
 */
export function Fibonacci(n: number): number {
    // write code here
    if(n === 1 || n === 2) return 1
    return Fibonacci(n -1) + Fibonacci(n - 2)
}

发表于 2022-07-15 13:40:33 回复(0)

Typescript

写前端的刻猫猫

export function Fibonacci(n: number): number {
    // write code here
    if(n<=1) {
        return n;
    }
    
    const cache:number[] = [];
    cache[0] = 0;
    cache[1] = 1;
    for(let i = 2; i<=n; i++ ) {
        cache[i] = cache[i-1] + cache[i-2];
    }
    return cache[n];
}

发表于 2022-03-26 00:52:29 回复(0)