时间戳

首页 > 解决方案 > 查找小于或等于一个数字的所有斐波那契数

javascript - 查找小于或等于一个数字的所有斐波那契数

问题描述

我正在尝试在 JavaScript 中实现一个函数，该函数返回一个包含所有斐波那契数的数组，直到某个数字（num）。在我的研究过程中，我遇到了这个答案：计算至少 n 的斐波那契数。我用 JavaScript 和 Python 实现了他们的解决方案，但发现他们的解决方案有一个错误。问题是最后一个元素有时是错误的。这是我根据上面链接的答案中找到的解决方案编写的代码。

function findFibs(num) {
  
  if (num < 2) {
    return [1,1];
  } else {
    var fibs = findFibs(num - 1)
    if ((fibs[fibs.length - 1]) < num ) {
      fibs.push(fibs[fibs.length - 1] + fibs[fibs.length - 2])
    }
    return fibs;
  }
}

console.log(sumFibs(20));

此代码的预期输出为：[ 1, 1, 3, 5, 13 ] ，但实际输出为[ 1, 1, 3, 5, 13, 21 ]。我错过了什么？

标签： javascriptarraysrecursionfibonacci

解决方案

功能性的

递归是一种函数式遗产，因此将其与函数式风格一起使用会产生最佳结果。这意味着要避免诸如突变、变量重新分配和其他副作用之类的事情。考虑一种更实用的方法 -

给定一个limit和两个种子，a并且b-

  1. 如果种子a大于输入limit，则返回空结果
  2. （感应）a小于或等于极限。重复子问题(limit, b, a + b)并将其附加到单例[a]

这编码为纯函数表达式 -

const fibs = (limit, a = 1, b = 1) =>
  a > limit
    ? []                                 // #1
    : [ a, ...fibs(limit, b, a + b) ]    // #2
    
console.log(fibs(20))
// [ 1, 1, 2, 3, 5, 8, 13 ]

至关重要的

如果我要对这个程序使用命令式风格，我想我会使用生成器 -

function* fib (a, b)
{ yield a
  yield *fib(b, a + b)
}

function* fibs (limit)
{ for (const n of fib(1, 1))
    if (n < limit)
      yield n
    else
      return
}

console.log(Array.from(fibs(20)))
// [ 1, 1, 2, 3, 5, 8, 13 ]

堆栈安全

如上所示fib，我们可以使用具有命令式风格的递归，但因为它会溢出堆栈，所以在这种情况下使用循环会更有意义 -

function* fib (a, b)
{ let t
  while (true)    // stack-safe, but not recursive
  { yield a
    t = a
    a = b
    b = t + a
  }
}

function* fibs (limit)
{ for (const n of fib(1, 1))
    if (n < limit)
      yield n
    else
      return
}

console.log(Array.from(fibs(20)))
// [ 1, 1, 2, 3, 5, 8, 13 ]

大整数

斐波那契数列快速生成大量数字，JavaScript 将使用科学记数法进行近似。第 102项是927372692193079200000，第 103项是1.5005205362068963e+21。这是由于 JavaScript 数字的大小限制。使用较新的BigInt我们可以轻松解决这个问题 -

function* fib (a, b)
{ let t
  while (true)
  { yield a
    t = a
    a = b
    b = t + a
  }
}

function* fibs (limit)
{ for (const n of fib(1n, 1n)) // <- bigint
    if (n < limit)
      yield n
    else
      return
}

for (const n of fibs(1e70))
  console.log(String(n))       // <- bigint to string

StackOverflow.com 会截断输出以仅显示最后 50 行。检查浏览器的控制台以获取完整输出 -

...
426547842461739379460149980002442288124894678853713953114433
690168906931029935139391829792095612517948949963798093315456
1116716749392769314599541809794537900642843628817512046429889
1806885656323799249738933639586633513160792578781310139745345
2923602405716568564338475449381171413803636207598822186175234
4730488062040367814077409088967804926964428786380132325920579
7654090467756936378415884538348976340768064993978954512095813
12384578529797304192493293627316781267732493780359086838016392
20038668997554240570909178165665757608500558774338041350112205
32423247527351544763402471792982538876233052554697128188128597
52461916524905785334311649958648296484733611329035169538240802
84885164052257330097714121751630835360966663883732297726369399
137347080577163115432025771710279131845700275212767467264610201
222232244629420445529739893461909967206666939096499764990979600
359579325206583560961765665172189099052367214309267232255589801
581811569836004006491505558634099066259034153405766997246569401
941390895042587567453271223806288165311401367715034229502159202
1523202464878591573944776782440387231570435521120801226748728603
2464593359921179141398048006246675396881836888835835456250887805
3987795824799770715342824788687062628452272409956636682999616408
6452389184720949856740872794933738025334109298792472139250504213
10440185009520720572083697583620800653786381708749108822250120621
16892574194241670428824570378554538679120491007541580961500624834
27332759203762391000908267962175339332906872716290689783750745455
44225333398004061429732838340729878012027363723832270745251370289
71558092601766452430641106302905217344934236440122960529002115744
115783425999770513860373944643635095356961600163955231274253486033
187341518601536966291015050946540312701895836604078191803255601777
303124944601307480151388995590175408058857436768033423077509087810
490466463202844446442404046536715720760753273372111614880764689587
793591407804151926593793042126891128819610710140145037958273777397
1284057871006996373036197088663606849580363983512256652839038466984
2077649278811148299629990130790497978399974693652401690797312244381
3361707149818144672666187219454104827980338677164658343636350711365
5439356428629292972296177350244602806380313370817060034433662955746
8801063578447437644962364569698707634360652047981718378070013667111
14240420007076730617258541919943310440740965418798778412503676622857
23041483585524168262220906489642018075101617466780496790573690289968
37281903592600898879479448409585328515842582885579275203077366912825
60323387178125067141700354899227346590944200352359771993651057202793
97605290770725966021179803308812675106786783237939047196728424115618
157928677948851033162880158208040021697730983590298819190379481318411
255533968719576999184059961516852696804517766828237866387107905434029
413462646668428032346940119724892718502248750418536685577487386752440
668996615388005031531000081241745415306766517246774551964595292186469
1082459262056433063877940200966638133809015267665311237542082678938909
1751455877444438095408940282208383549115781784912085789506677971125378
2833915139500871159286880483175021682924797052577397027048760650064287
4585371016945309254695820765383405232040578837489482816555438621189665
7419286156446180413982701248558426914965375890066879843604199271253952

推荐阅读