4

我可以执行递归函数来计算第 n 个斐波那契项，如下所示：

int rec (int i)
{
  if(i == 1 || i == 2)
    return i;
else return rec(i-1)+rec(i-2);

}

但我想使用黄金数字 1.618 来计算斐波那契；但我的尝试失败了，我得到了错误的数字：

int rec (int i)
{
  if(i == 1 || i ==  2)
    return i;

  else return 1.618*rec(i-1);

 }

我怎样才能让它工作？

4

5 回答 5

8

黄金比例是一个无理数，因此您不必期望能够将其近似值插入公式中以获得准确的结果。

如果你想知道如何快速计算n斐波那契数，这里有一个页面，列出了各种方法，按运行时降序排列（但按实现难度递增）： http: //www.nayuki.io/page /快速斐波那契算法

于 2013-02-23T22:56:14.990 回答
2

如果您指的是比内公式，请执行以下操作：

long fib(int i) {
    double phi = // Golden Ratio
    return Math.round((Math.pow(phi, i) - Math.pow(-phi, -i)) / Math.sqrt(5));
}

请注意，上述公式不是递归的。我不知道任何用于计算 fib 的递归公式。使用黄金比例排序。

于 2013-02-23T22:59:15.777 回答
0

你的数学似乎有缺陷，而且你四舍五入的频率太高了。我用了这个公式。

这有效：

double gr = 1.618033988749895;
int rec (int i)
{
   return (int)round(rec2(i)/(gr+2));
}

double rec2 (int i)
{
  if (i == 1)
    return gr;

  else return gr*rec2(i-1);
}

此外，它实际上并不需要递归：

static int rec (int i)
{
  return (int)round(pow(gr, i)/(gr+2);
}

我没有检查太多数字，但它似乎非常准确 (Java)。

于 2013-02-23T23:03:27.880 回答
0

这是你如何做到这一点：

double gr = 1.618033988749895;
        double FibGoldenRatio(int i)
        {
            if (i == 1 )
                return 1;

            return  Math.Round(gr * FibGoldenRatio(i - 1));

        }

这里的输出示例：

1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
102334155
165580141
267914296
433494437
701408733
1134903170
1836311903
2971215073
4807526976
7778742049
12586269025
20365011074
32951280099
53316291173
86267571272
139583862445
225851433717
365435296162
591286729879
956722026041
1548008755920
2504730781961
4052739537881
6557470319842
10610209857723
17167680177565
27777890035288
44945570212853
72723460248141
117669030460994
190392490709135
308061521170129
498454011879264
806515533049393
1.30496954492866E+15
于 2013-02-24T09:58:32.160 回答
0

您可以自己计算黄金比例并用它来找到第 n 个斐波那契数。

long long fib(int n) {
    double phi = (1 + sqrt(5))/2.0; // golden ratio
    double phi_hat = (1 - sqrt(5))/2.0; // fraction part of golden ratio

    return (pow(phi, n) - pow(phi_hat, n))/sqrt(5);
}
于 2017-12-25T10:58:58.680 回答