java - 修正斐波那契数列的迭代版本

Question

我刚刚经历了斐波那契数列算法的迭代版本。我找到了以下代码

int Fibonacci(int n)
{
   int f1 = 0;
   int f2 = 1;
   int fn;
   for ( int i = 2; i < n; i++ )
   {
      fn = f1 + f2;
      f1 = f2;
      f2 = fn;
   }
}  

一个愚蠢的问题刚刚出现在我的脑海中。上面的函数添加两个前面的数字并返回第三个，然后为下一次迭代准备好变量。如果它会是这样的。 “返回前三个数字之和的系列数”我们如何更改上面的代码来找到这样的数字.u

Answer 1

作为提示，请注意上述算法的工作原理是通过一些变量“循环”数字。在上面的代码中，在您存储的每个点

 F_0    F_1
  a      b

然后在循环中将它们“移动”一步:

 F_1    F_2
  a      b

然后在下一个循环迭代中再次“移动”它们:

 F_2    F_3
  a      b

如果你想更新算法总和最后的三个值，考虑像这样存储它们:

 T_0    T_1    T_2
  a      b      c

然后再次移动它们:

 T_1    T_2    T_3
  a      b      c

然后再次移动它们:

 T_2    T_3    T_4
  a      b      c

将这种直觉转化为代码是一个很好的练习，所以我会把这些细节留给你。

就是说 - 有一种非常、非常 更快的方法来计算 Fibonacci 和“Tribonacci”序列的第 n 项。 This article描述了一个非常聪明的技巧，使用矩阵乘法比上面的循环更快地计算项，并且有代码 available here实现了这个算法。

希望这对您有所帮助!