生成给定阶斐波那契类序列的JavaScript函数
高阶Fibonacci数列
n阶Fibonacci序列是一个整数序列，其中每个序列元素是以前的n元素的和(除了序列中的第一个n元素)。通常的Fibonacci数是2阶的Fibonacci序列。对n = 3和n = 4的案件进行了彻底的调查。将非负整数组合成至多为n的部分的数目是n阶的Fibonacci序列。长度为0s和长度为m的D12字符串最多包含n连续0的串数序列也是n阶的斐波纳契序列。Tribonacci数-- tribonacci数与Fibonacci数类似，但序列不是以两个预定项开始，而是以三个预定项开始，之后的每个项都是前三个项的和。前几个tribonacci数是: 0，0，1，1，2，4，7，13，24，44，81,149,274,504,927,1705,3136,5768,10609,19513,35890,66012，…(序列OEIS中的A 000073) Tetranacci数四字数从四个预定项开始，其后的每一个项都是前四个项的和。前几个四字数是: 0，0，0，1，1，2，4，8，15，29，56,108,208,401,773,1490,2872,5536,10671,20569,39648,76424,147312,283953,547337，…(序列OEIS中的A 000078)
函数很简单，你给它两个参数，第一个参数是一个数字数组，第二个参数是术语数。
数组的长度是生成序列的顺序，数组的元素是生成序列的一阶项，函数采用迭代方法生成所需的序列。
示例：
> console.log(fiblike([0, 1], 16))
[
0, 1, 1, 2, 3, 5,
8, 13, 21, 34, 55, 89,
144, 233, 377, 610
]
undefined
> console.log(fiblike([0, 0, 1], 16))
[
0, 0, 1, 1, 2,
4, 7, 13, 24, 44,
81, 149, 274, 504, 927,
1705
]
undefined
> console.log(fiblike([0, 0, 0, 1], 16))
[
0, 0, 0, 1, 1,
2, 4, 8, 15, 29,
56, 108, 208, 401, 773,
1490
]
undefined
> console.log(fiblike([1, 2, 3], 16))
[
1, 2, 3, 6, 11,
20, 37, 68, 125, 230,
423, 778, 1431, 2632, 4841,
8904
]
undefined
> console.log(fiblike([9, 21, 1986], 16))
[
9, 21, 1986,
2016, 4023, 8025,
14064, 26112, 48201,
88377, 162690, 299268,
550335, 1012293, 1861896,
3424524
]
undefined
>代码
function fiblike (array, terms) {
if (isNaN(terms) || !(array instanceof Array)) {
throw 'Arguments have incorrect types'
}
if (array.some(isNaN)) {
throw 'Array should only contain numbers'
}
var result = []
for (let i=0; i s + n, 0))
let first = array.shift()
result.push(first)
}
return result
}
console.log(fiblike([0, 1], 16))
console.log(fiblike([0, 0, 1], 16))
console.log(fiblike([0, 0, 0, 1], 16))
console.log(fiblike([1, 2, 3], 16))
console.log(fiblike([9, 21, 1986], 16))最后一个例子是我最喜欢的Youtuber的生日，我不会告诉你她的名字
密码怎么样了？如何改进呢？
我真的不知道为什么1 instanceof Number会失败。
回答 1
Code Review用户
发布于 2022-04-28 23:27:07
对于n个元素Fibbonacci级数k的算法是O(N*K)，您的JavaScript实现可能效率很低。我把你的算法修改成O(N)。我修改了您的JavaScript实现以提高效率。我使用JSBench.me来比较原始版本和修订版本。
原文：
function fiblike (array, terms) {
if (isNaN(terms) || !(array instanceof Array)) {
throw 'Arguments have incorrect types'
}
if (array.some(isNaN)) {
throw 'Array should only contain numbers'
}
var result = []
for (let i=0; i s + n, 0))
let first = array.shift()
result.push(first)
}
return result
}修订本：
function fiblike(a, n) {
const aLen = a.length;
if (aLen === 0 || aLen >= n) {
return a;
}
const like = new Array(n);
const likeLen = like.length;
like[aLen] = 0;
for (let i = 0; i < aLen; i++) {
let ai = a[i];
like[i] = ai;
like[aLen] += ai;
}
for (let i = aLen + 1; i < likeLen; i++) {
like[i] = 2*like[i-1] - like[i-aLen-1];
}
return like;
}示例：
console.log(fiblike([0, 1], 16));
console.log(fiblike([0, 0, 1], 16));
console.log(fiblike([0, 0, 0, 1], 16));
console.log(fiblike([1, 2, 3], 16));
console.log(fiblike([9, 21, 1986], 16));此基准使用您的示例。
// benchmark
fiblike([0, 1], 16);
fiblike([0, 0, 1], 16);
fiblike([0, 0, 0, 1], 16);
fiblike([1, 2, 3], 16);
fiblike([9, 21, 1986], 16);原来的版本比修改后的版本慢了大约89%。修改后的版本比原来的版本快9倍。
这些基准衡量了增加Fibbonacci级数k阶的效果。
对于原始版本，每个元素都是k值、O(K)或线性时间之和。对于修改后的版本，每个元素都是3个值、O(1)或常数时间之和。
// benchmark setup - k = 2
let a = new Array(2);
a[a.length - 1] = 1;
// benchmark
fiblike(a, a.length+100);对于k=2时，原版本比修订版本慢了大约94%。修改后的版本比原来的版本快16倍。
// benchmark setup - k = 10
let a = new Array(10);
a[a.length - 1] = 1;
// benchmark
fiblike(a, a.length+100);对于k= 10，原始版本比修改后的版本慢97%左右。修订后的版本比原来的版本快33倍。
算法：
对于Fibbonacci级数k阶的元素a(n)，
a(n) = a(n-1) + ... + a(n-k)和
a(n+1) = a(n) + a(n-1) + ... + a(n-(k+1))代替a(n)和简化，
a(n+1) = [a(n-1) + ... + a(n-k)] + [a(n-1) + ... + a(n-(k+1))]
= a(n) + a(n) - a(n-k-1)元素的时间复杂度为常数或O(1)。
对于n元Fibbonacci级数k阶，时间复杂度为线性或O(N)。
https://codereview.stackexchange.com/questions/276083
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号