2

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

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

4

4 回答 4

6

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

 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 项。 这篇文章描述了一个非常聪明的技巧，它使用矩阵乘法来比上面的循环更快地计算项，这里有实现这个算法的代码。

希望这可以帮助！

于 2012-06-18T21:38:07.950 回答
4

我喜欢递归。叫我虐待狂。

static int rTribonacci (int n, int a, int b, int c) {
    if (n == 0) return a;
    return rTribonacci (n-1, b, c, a + b + c);
}

int Tribonacci (int n) { return rTribonacci(n, 0, 0, 1); }
于 2012-06-19T00:58:50.330 回答
3

我通常不会回答像作业一样“闻起来”的问题，但由于其他人已经回答了这就是我会做的：

int Tribonacci(int n)
{
    int last[3] = { 0, 0, 1 }; // the start of our sequence

    for(int i = 3; i <= n; i++)
        last[i % 3] = last[i % 3] + last[(i + 1) % 3] + last[(i + 2) % 3];

    return last[n % 3];
}

通过将循环更改为：

    for(int i = 3; i <= n; i++)
        last[i % 3] = last[0] + last[1] + last[2];

它可以进一步优化，坦率地说，有更好的方法来计算这样的序列，正如 templatetypedef 所说。

于 2012-06-19T00:18:16.010 回答
0

如果要使用递归，则不需要任何其他参数：

int FibonacciN(int position)
{   if(position<0) throw new ArgumentException("invalid position");
    if(position==0 || position ==1) return position;
    return FibonacciN(position-1) + FibonacciN(position-2);
}
于 2014-02-07T19:01:40.563 回答