修正的Fibonacci序列的迭代版本

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

将这种直觉转换为代码是一个很好的练习,所以我将把这些细节留给你.

这就是说-是有很多,很多计算斐波那契和"Tribonacci"序列的第n项更快的方式. 本文描述了一个非常聪明的技巧,使用矩阵乘法比上述循环更快地计算项,并且这里有可用于实现此算法的代码.

希望这可以帮助!