我正在阅读有关斐波那契的 DP 版本。
在 Sedgewick 我看到：
int[] T = new int[47]; 用于存储以前的计算。在其他地方，我看到斐波那契的最大输入应该小于92.
我不清楚这些数字是如何得出的？我知道它与溢出和大小有关，int但我不清楚我们如何最终得到这些限制。
有什么帮助吗？
问问题
6952 次
5 回答
10
第 n 个斐波那契数有一个封闭式表达式，即比内公式，
F(n) = (φ^n - ψ^n) / (φ - ψ)
在哪里
φ = (1 + √5)/2; ψ = 1 - φ = -1/φ
现在|ψ| < 1，所以该ψ^n术语很快收敛到 0，因此在估计它的大小时，F(n)除了前几个数字之外可以忽略不计。
因此，如果您有一个整数类型，其b位用于表示正整数，您可以用
F(n) < 2^b
（因为可以表示的最大数是2^b - 1）。忽略ψ^n术语并使用φ - ψ = √5，我们找到条件
φ^n < 2^b * √5
<=> n*log φ < b*log 2 + 1/2*log 5
<=> n < b*(log 2 / log φ) + 1/2*(log 5 / log φ)
log 2 / log φ ≈ 1.44042009和1/2*(log 5 / log φ) ≈ 1.672275938，因此对于带符号的 32 位整数类型（它有 31 位表示正数，因为一位用于符号），您可以表示 Fibonacci 数
n < 31*(log 2 / log φ) + 1/2*(log 5 / log φ) ≈ 44.65 + 1.67 ≈ 46.32
即索引在 0 到 46（含）之间的 47 个斐波那契数。使用无符号 32 位整数类型，您还可以表示F(47).
使用有符号的 64 位整数类型，您可以将斐波那契数表示为
n < 63*(log 2 / log φ) + 1/2*(log 5 / log φ) ≈ 90.75 + 1.67 ≈ 92.42
并且使用无符号 64 位整数类型还可以表示F(93).
于 2013-02-25T17:07:06.803 回答
9
好吧，斐波那契数列（大约）以 1.618（黄金比例）的比率呈指数增长。
因此，如果您采用 1.618 的对数基数，Integer.MAX_VALUE它将告诉您在溢出之前大约可以进行多少次迭代....
或者，您可以通过计算来凭经验确定它何时溢出......
于 2013-02-25T10:54:44.890 回答
4
(有符号)int的值范围为−2.147.483.648 ... 2.147.483.647，因此无法存储大于 2.147.483.647 的斐波那契数。
现在的问题是：第一个大于该值的斐波那契数是多少？
电子表格 说：
n fib(n)
1 0
2 1
3 1
4 2
5 3
6 5
7 8
8 13
9 21
10 34
11 55
12 89
13 144
14 233
15 377
16 610
17 987
18 1597
19 2584
20 4181
21 6765
22 10946
23 17711
24 28657
25 46368
26 75025
27 121393
28 196418
29 317811
30 514229
31 832040
32 1346269
33 2178309
34 3524578
35 5702887
36 9227465
37 14930352
38 24157817
39 39088169
40 63245986
41 102334155
42 165580141
43 267914296
44 433494437
45 701408733
46 1134903170
47 1836311903
48 2971215073
49 4807526976
所以你可以看到：#47 之后的斐波那契数不适合 (signed) int。
澄清一下：与 C 不同，Java 没有unsigned类型。所以强调signed int有点过时了。
于 2013-02-25T10:52:20.747 回答
2
您可以使用以下公式：
F(2n) = F(n)* (2*F(n-1) + F(n))
n=46
F(92) = F(46) * (2*F(45) +F(46))
这是斐波那契的矩阵形式。
完整的号码列表（ulong 未溢出）
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55
11 89
12 144
13 233
14 377
15 610
16 987
17 1597
18 2584
19 4181
20 6765
21 10946
22 17711
23 28657
24 46368
25 75025
26 121393
27 196418
28 317811
29 514229
30 832040
31 1346269
32 2178309
33 3524578
34 5702887
35 9227465
36 14930352
37 24157817
38 39088169
39 63245986
40 102334155
41 165580141
42 267914296
43 433494437
44 701408733
45 1134903170
46 1836311903
47 2971215073
48 4807526976
49 7778742049
50 12586269025
51 20365011074
52 32951280099
53 53316291173
54 86267571272
55 139583862445
56 225851433717
57 365435296162
58 591286729879
59 956722026041
60 1548008755920
61 2504730781961
62 4052739537881
63 6557470319842
64 10610209857723
65 17167680177565
66 27777890035288
67 44945570212853
68 72723460248141
69 117669030460994
70 190392490709135
71 308061521170129
72 498454011879264
73 806515533049393
74 1304969544928657
75 2111485077978050
76 3416454622906707
77 5527939700884757
78 8944394323791464
79 14472334024676221
80 23416728348467685
81 37889062373143906
82 61305790721611591
83 99194853094755497
84 160500643816367088
85 259695496911122585
86 420196140727489673
87 679891637638612258
88 1100087778366101931
89 1779979416004714189
90 2880067194370816120
91 4660046610375530309
92 7540113804746346429
正如我们所见
45 1134903170
46 1836311903
92 7540113804746346429
7540113804746346429 = 1836311903*(2*1134903170 + 1836311903)
于 2013-02-25T11:01:59.457 回答
0
首先，已经完成了一些类来表示超出某些原始类型限制的大数，例如使用 long long 类型的某些 C 修饰符。要查看最大的术语，请查看最大的已知斐波那契数。
于 2013-02-25T11:52:16.843 回答