JS写斐波那契数列的几种方法
2024-08-28 21:31:34
斐波那契数，指的是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，斐波那契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=Fn-1+Fn-2（n>=2，n∈N*），用文字来说，就是斐波那契数列由 0 和 1 开始，之后的斐波那契数列系数就由之前的两数相加。
常用的计算斐波那契数列的方法分为两大类：递归和循环。
递归
方法一：普通递归
代码优美逻辑清晰。但是有重复计算的问题，如：当n为5的时候要计算fibonacci(4) + fibonacci(3)，当n为4的要计算fibonacci(3) + fibonacci(2) ，这时fibonacci(3)就是重复计算了。运行 fibonacci(50) 会出现浏览器假死现象，毕竟递归需要堆栈，数字过大内存不够。
function fibonacci(n) {
if (n == 1 || n == 2) {
return 1
};
return fibonacci(n - 2) + fibonacci(n - 1);
}
fibonacci(30)
方法二：改进递归-把前两位数字做成参数避免重复计算
function fibonacci(n) {
function fib(n, v1, v2) {
if (n == 1)
return v1;
if (n == 2)
return v2;
else
return fib(n - 1, v2, v1 + v2)
}
return fib(n, 1, 1)
}
fibonacci(30)
方法三：改进递归-利用闭包特性把运算结果存储在数组里，避免重复计算
var fibonacci = function () {
let memo = [0, 1];
let fib = function (n) {
if (memo[n] == undefined) {
memo[n] = fib(n - 2) + fib(n - 1)
}
return memo[n]
}
return fib;
}()
fibonacci(30)
方法三1：改进递归-摘出存储计算结果的功能函数
var memoizer = function (func) {
let memo = [];
return function (n) {
if (memo[n] == undefined) {
memo[n] = func(n)
}
return memo[n]
}
};
var fibonacci=memoizer(function(n){
if (n == 1 || n == 2) {
return 1
};
return fibonacci(n - 2) + fibonacci(n - 1);
})
fibonacci(30)
循环
方法一：普通for循环
function fibonacci(n) {
var n1 = 1, n2 = 1, sum;
for (let i = 2; i < n; i++) {
sum = n1 + n2
n1 = n2
n2 = sum
}
return sum
}
fibonacci(30)
方法二：for循环+解构赋值
var fibonacci = function (n) {
let n1 = 1; n2 = 1;
for (let i = 2; i < n; i++) {
[n1, n2] = [n2, n1 + n2]
}
return n2
}
fibonacci(30)
各种方法运行耗时如下图：普通递归>改进递归>for循环
最新文章
- Win.ini和注册表的读取写入
- Visual Studio 2012 Visual C++ 入门
- 【BZOJ-4199】品酒大会 后缀数组 + 并查集合并集合
- 织梦(dedecms)系统常用全局变量调用标签及路径
- 在VMware的虚拟机平台上如何进行网络设置
- Windows 位图
- Cocos2d-x 关于在iOS平台真机测试的一些注意
- 判断浏览器是否IE10
- Delphi使用JSON解析调用淘宝IP地址库REST API 示例
- 运用BeanUtils构建通用的查询 更新方法(个人拙作，不喜勿喷)
- 软体project（四）——一生
- 一步一步学Vue（五）
- mysql 5.7 怎么修改默认密码、随机密码
- Spring Boot 2.0 WebFlux 教程 (一) | 入门篇
- Python批量修改寄存器的值
- Visual Studio 2019 double clicking project(custom behavior)
- 2018-2019-2 学号20175223 实验二《Java面向对象程序设计》实验报告
- 怎么在Mac中的Safari查看网页源码
- postgreSQL使用杂谈
- 【问题与解决】怎么删除TFS云端上的项目