首页 > 试题广场 >

斐波那契数列

[编程题]斐波那契数列
  • 热度指数：46963 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
用 JavaScript 实现斐波那契数列函数,返回第n个斐波那契数。 f(1) = 1, f(2) = 1 等
算法知识视频讲解
添加回答
HTML/CSS/JavaScript
小文同学在努力头像 小文同学在努力 
function fibonacci(n) {
    if(n < 1) return -1;
    let a = 1;
    let b = 1;
    for(let i = 2; i < n; i++) {
        b = a + b;
        a = b - a;
    }
    return b;
}

发表于 2022-03-26 17:02:06 回复(0)
JavaScript
🐲龍🐉头像 🐲龍🐉 
function fibonacci(n) {
    if (n <= 2) {
        return 1;
    }
    var a = new Array(n+1);
    a[1] = 1;
    a[2] = 1;
    for (var i = 3; i < n+1; i++) {
        a[i] = a[i-2] + a[i-1];
    }
    return a[n];
}

发表于 2019-05-15 15:05:18 回复(0)
拽是我的个性头像 拽是我的个性 


function fibonacci(n, ac1 = 1, ac2 = 1) {    if(n === 1 || n === 2){  return ac2;  }    return fibonacci(n-1, ac2, ac1 + ac2); }
问问为啥这种方法通过不了，难道不支持es6？
发表于 2018-06-22 23:58:13 回复(2)
牛客594283号头像 牛客594283号
首先对特殊情况进行判断，然后避免使用递归。
function fibonacci(n) {
    if( n < 0 ){
        return 0;
    }
    if( n < 3){
        return 1;
    }
    var start_a = 1, start_b = 1;
    var total = 0;
    for(var i = 2; i < n; i++){
        total = start_a + start_b;
        start_a = start_b;
        start_b = total;
    }
    return start_b;
}
发表于 2017-08-22 14:09:03 回复(0)
Zfirsty头像 Zfirsty 
function fibonacci(n) {
    dp = [0,1,1];
    return (function f(n){
        if(dp[n]) return dp[n];
        dp[n] = f(n-2) + f(n-1);
        return dp[n];
    })(n);
}

发表于 2017-08-18 15:53:56 回复(0)
sunshine193头像 sunshine193
functionfibonacci(n){
    if(n==1||n==2)
        return1;
    returnfibonacci(n-1)+fibonacci(n-2);
}
//考察递归
发表于 2017-08-16 19:53:20 回复(0)
JavaScript
cavi头像 cavi 
function fibonacci(n) {
    return n > 1 ? fibonacci(n-1) + fibonacci(n-2) : n
}
发表于 2017-03-08 12:55:20 回复(0)
牛客(Yangfan)头像 牛客(Yangfan) 
function fibonacci(n) {
    // 1,1,2,3,5,8
    var arr=[0,1];
    var len=arr.length;
    for (var i=0;i<n-1;i++) {
        arr.push(arr[len-1]+arr[len-2]);
        len=arr.length;
        console.log(arr);
    }
    return arr[len-1];
}

编辑于 2016-07-21 21:24:07 回复(0)
jonker头像 jonker
function fibonacci (n){
  var arr = [1,1];
  if(n===1 || n===2){
    return arr.slice(0,n);
  }else{
    for(var i=0; i<n-2; i++){
    arr.push(arr[i] + arr[i+1]);
  }
  return arr;
}

编辑于 2015-06-08 09:50:15 回复(0)
sarah_cw头像 sarah_cw 
function fibonacci(n) {
    var one=1;
    var two=1;
    for(var i=3;i<=n;i++){
      var three=one+two; 
        one=two;
        two=three;
        
    }
    return three;
    
}

发表于 2016-01-20 21:04:28 回复(0)
嬉皮士头像 嬉皮士 
function fibonacci(n) {
    if(n===1 || n ===2) return 1;
    else return arguments.callee(n - 1) + arguments.callee(n - 2);
}

发表于 2015-09-29 21:09:52 回复(0)
JavaScript
路人1头像 路人1 
function fibonacci(n) {
        //一、递归解法
        //return n<=2?1:fibonacci(n-1)+fibonacci(n-2);
        
        //二、循环解法
        var num1=1;
        var num2=1;
        for(var i=2;i<n;i++){
                num2+=num1;
                num1=num2-num1;
        }
        return num2;
}
循环体内的计算过程详解：
第一句：将num2的旧值，加上num1，得到num2的新值
第二句：用num2的新值，减去num1，得到num1的新值
当前循环结束，num1和num2的值都获得了更新~
编辑于 2017-02-28 11:34:45 回复(4)
vuji头像 vuji 
function fibonacci(n){
    if(n==1||n==2)
        return 1;
    return fibonacci(n-1)+fibonacci(n-2);
}

编辑于 2015-06-30 12:59:42 回复(3)
O.z.头像 O.z.
闭包存储中间结果，优化多次调用。
空间复杂度：o(n)，时间复杂度：o(n)，最快 o(1) 
var _fib = (function (n) {
	var memory = [0, 1];
	return function (n) {
		for (var i = memory.length; i <= n; i++) {
			memory[i] = memory[i - 1] + memory[i - 2];
		}
		//console.log(memory.length + ' numbers saved.');
		return memory.slice(0,n+1);
	};
})();

var fibonacci = function (n) {
	return _fib(n)[n];
}
运用大数加法： 
var _fib = (function (n) {
	var memory = ['0', '1'];

	function add(a, b) {
		var res = '',
			c = 0;
		a = a.split('');
		b = b.split('');
		while (a.length || b.length || c) {
			c += ~~a.pop() + ~~b.pop();
			res = c % 10 + res;
			c = c > 9;
		}
		return res.replace(/^0+/, '');
	}

	return function (n) {
		for (var i = memory.length; i <= n; i++) {
			memory[i] = add(memory[i - 1], memory[i - 2]);
		}
		//console.log(memory.length + ' numbers saved.');
		return memory.slice(0, n + 1);
	};
})();

var fibonacci = function (n) {
	return _fib(n)[n];
}
优化内存管理： 
var _Fib = (function (n) {
	var memory = ['0', '1'];

	var add = function (a, b) {
		var res = '',
			c = 0;
		a = a.split('');
		b = b.split('');
		while (a.length || b.length || c) {
			c += ~~a.pop() + ~~b.pop();
			res = c % 10 + res;
			c = c > 9;
		}
		return res.replace(/^0+/, '');
	}

	return {
		get: function (n) {
			for (var i = memory.length; i <= n; i++) {
				memory[i] = add(memory[i - 1], memory[i - 2]);
			}
			//console.log(memory.length + ' numbers saved.');
			return memory.slice(0, n + 1);
		},
		clear: function () {
			//console.log('Memories reset.')
			memory = ['0', '1'];
		}
	};
})();

var fibonacci = function (n) {
	if (n < 0) {
		_Fib.clear();
	} else {
		return _Fib.get(n)[n];
	}
}
编辑于 2016-07-01 23:44:19 回复(5)
JavaScript
囧超哥头像 囧超哥
function fibonacci(n) {
    // 高等数学 通项公式
    var sqrt5 = Math.sqrt(5);
    return Math.round((Math.pow((1+sqrt5)/2,n)-Math.pow((1-sqrt5)/2,n))*sqrt5/5);
}
发表于 2017-09-01 17:38:49 回复(6)
希希01头像 希希01 
//使用普通迭代
function fibonacci(n){
	if(n<=2){ 
		return 1;
	}else{
		var first = 1;
		var second = 1;
		var third = 0;
		for(var i=3; i<=n; i++){  
			third = first + second;
			first = second; 
			second = third;
		}
		return third;
	}
}
//使用递归
function fibonacci(n){ 
	if(n<=2){
		return 1;
	}else{
		return fibonacci(n-1) + fibonacci(n-2);		
	}
}
//使用动态规划
function fibonacci(n){
	var val = [];
	if(n<=2){
		return 1;
	}else{
		val[1]=1; //n为2
		val[2]=2; //n为3
		for(var i=3; i<n; ++i){
			val[i] = val[i-1] + val[i-2];
		}
		return val[n-1];
	}
}
//在这里使用普通迭代和动态规划的效率一样，递归效率最低。

编辑于 2017-04-04 17:05:28 回复(0)
Polly_dan头像 Polly_dan 
哈哈，看来这个是最原始的方法了。
function fibonacci(n) {
    var x = 1, //第一项
        y = 1, //第二项
        z = 0; //和
    
    if(n==1){
        return 1;
    }else if(n==2){
        return 1;
    }
    else{ 
        for(var i=1; i<n-1;i++){
            z = x + y;
            x = y;
            y = z;
        }
        return y;
    }
    
}

发表于 2016-08-24 22:22:37 回复(1)
益明头像 益明
// 递归（时间复杂度很高，不好）
function fibonacci(n) {
    if (n === 1) {
        return 1
    }
    if (n === 2) {
        return 1
    }
    return fibonacci(n - 1) + fibonacci(n - 2)
}
// 动态规划备忘录（时间复杂度低）
function fibonacci(n) {
var arr = [1, 1]
for (var i = 2; i <= n - 1; i++) {
arr.push(arr[i - 1] + arr[i - 2])
}
return arr.pop()
}
// 优化递归（时间复杂度最低）
function fibonacci(n) {
var a = 1, b = 1, temp = 0
if (n === 1) {
return 1
}
if (n === 2) {
return 1
}
for (var i = 3; i <= n; i++) {
temp = a + b
b = a
a = temp
}
return temp
}

发表于 2018-09-02 16:10:03 回复(1)
JavaScript
季铵盐头像 季铵盐 
function fibonacci(n) {
    if(n<0){
        return -1;
    }else if(n < 2){
        return n;
    }else{
       return arguments.callee(n-1) +  arguments.callee(n-2); 
    }
}
一个递归完事儿，装逼写法＝。＝
发表于 2016-08-24 15:41:19 回复(3)
我是一只小小小小菜鸟头像 我是一只小小小小菜鸟
代码如下：
function fibonacci(n) {
    if(n ==1 || n == 2){
        return 1
    }else{
         return fibonacci(n - 1) + fibonacci(n - 2);
    }
   
}
发表于 2016-08-15 21:56:37 回复(1)
提交观点

问题信息

Javascript
难度：
177条回答 27926浏览

热门推荐

通过挑战的用户

查看代码

相关试题

斐波那契数列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号