修正斐波纳契序列的迭代版本 [英] Iterative Version of Modified Fibonacci Sequence

问题描述

我只是经历了斐波那契数列迭代算法的算法。我发现以下代码

I was just going through the iterative version of fibonacci series algorithm. I found this following code

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;
   }
}  

一个愚蠢的问题刚刚提出。上面的函数添加了两个先前的数字，并返回第三个数字，然后获取变量为下一次迭代做好准备。如果它会是这样的东西。 返回一个系列，它是前面三个数字的总和我们如何改变上面的代码来找到这样的数字。

A silly question just raised in my mind. The function above adds two previous numbers and returns the third one and then get variables ready for the next iteration. What if it would be something like this. "Return a number of series which is the sum of previous three numbers" how we can change the above code to find such a number.u

推荐答案

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

As a hint, notice that the above algorithm works by "cycling" the numbers through some variables. In the above code, at each point you are storing

 F_0    F_1
  a      b

然后在循环中将它们移动一步：

You then "shift" them over by one step in the loop:

 F_1    F_2
  a      b

在下一循环迭代中：

 F_2    F_3
  a      b

如果您要更新算法和最后的三个值，请考虑如下存储：

If you want to update the algorithm sum the last three values, think about storing them like this:

 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

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

Converting this intuition into code is a good exercise, so I'll leave those details to you.

也就是说，计算斐波那契数列和Tribonacci序列的第n个项目有更多的方法。 本文介绍了一个非常聪明的技巧，使用矩阵乘法比上述循环更快地计算项，并且有实现此算法的代码此处。

That said - there is a much, much faster way to compute the nth term of the Fibonacci and "Tribonacci" sequences. This article describes a very clever trick using matrix multiplication to compute terms more quickly than the above loop, and there is code available here that implements this algorithm.

希望这有助！

这篇关于修正斐波纳契序列的迭代版本的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！