javascript - 斐波那契数列JavaScript的第N个值(超时错误)

Question

我有一个针对此 Kata 的有效解决方案(找到斐波那契数列的第 n 个值)，但是我一直收到超时错误。任何人都可以就如何重构它以更有效地运行提供建议吗？提前致谢!

这是带有描述的链接 - https://www.codewars.com/kata/simple-fun-number-395-fibonacci-digit-sequence/train/javascript

You are given three non negative integers a, b and n, and making an infinite sequence just like fibonacci sequence, use the following rules:

step1: use ab as the initial sequence. step2: calculate the sum of the last two digits of the sequence, and append it to the end of sequence. repeat step2 Your task is to complete function find. Return nth digit(0-based) of the sequence.

function find(a,b,n){
  let start = ("" + a + b);
  let next = a + b;
  let seq = start + next;
  
  while (seq.length <= n) {
    seq += (parseInt(seq[seq.length-2]) + parseInt(seq[seq.length-1]));
  }
  return parseInt(seq[n]);
}

console.log(find(7,8,9))

// should return 5

Answer 1

首先。 . .不要使用字符串，不要使用 parseInt，不要一次保留整个序列。你只需要数字，你只需要最后两位数字。给定一个介于 10 和 18 之间的数字 x(这是两位数的最大可能和)，它的十位是 1 而它的个位是 x - 10。仅此一项就将是一项重大改进。

其次。 . .由于给定点之后的整个序列由该点的前两位数决定，¹ 并且只有 100 个可能的两位数序列，每个序列必须在 200 位数字内重复；也就是说，在最多 200 位数字内，它必然会进入一个永远不会退出的重复数字循环，其中该循环的长度小于 200 位数字。² 所以如果 n 大于几百，您可以通过查找此循环的长度并“跳过”该长度的大倍数来进行大规模优化。

<子>1。实际上，这并不像所写的那样真实。例如，序列 69156… 和 79167… bot 包含 91，但后面跟着不同的东西。这是因为“1”属于两位数，均的位数由前两位决定。我不确定如何更好地表达这一点，但希望你明白我的意思。它不会影响整体论点，但在应用该想法时需要注意这一点。
<子>2。实际上少得多；测试 a 和 b 的所有可能值，我发现序列总是进入循环 and 仅在 25 位数字内完成它的第一次迭代!但是除了详尽的测试之外，我不确定如何严格地证明这个小得多的数字是合理的；所以以依赖它的方式编写代码可能是作弊。