斐波那契数列

[编程题]斐波那契数列

热度指数：15454 时间限制：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。

输出描述:

输出斐波那契数列中第 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

输入

输出

算法知识视频讲解

Javascript_V8

LivingRose

while(n = +readline()){
    var result =1 ;
    for(let i=0,x =0,y=1;i<n-1;i++ ){
        result = x+y;
         x=y;
        y=result;
       
    }
    console.log(result)
}

发表于 2022-09-05 11:02:01 回复(0)

Javascript_V8

菜鸟学习算法

var n = parseInt(readline());

function help(n){
if(n<2){
return n
}
var dp=new Array(n);
dp[1]=1;
dp[2]=1;
for(var i=3;i<=n;i++){
dp[i]=dp[i-2]+dp[i-1];
}

return dp[n]
}
console.log(help(n));

发表于 2022-08-08 23:37:51 回复(0)