fibonnacci的上限

Question

我正在阅读关于斐波纳西的DP版本.
在Sedgewick我看到:
int[] T = new int[47]; 存储以前的计算.在其他地方,我看到斐波那契的最大输入应该小于92.
我不清楚这些数字是如何出现的？我知道它与溢出和大小有关,int但我不清楚我们如何最终达到这些限制.
有帮助吗？

Answer 1

对于第 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 位来表示正数，因为一位用于符号），您可以表示斐波那契数

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).

Answer 2

那么,斐波那契系列(大约)以1.618(黄金比率)的比例呈指数增长.

如果你采用1.618的日志基数,Integer.MAX_VALUE它将告诉你大约在溢出之前可以进行多少次迭代....

或者,您可以通过计算来凭经验确定何时溢出....

Answer 3

(signed) 的int取值范围为\xe2\x88\x922.147.483.648 ... 2.147.483.647，因此存储大于 2.147.483.647 的斐波那契数不起作用。

\n\n

现在的问题是：第一个大于该值的斐波那契数是多少？
\n电子表格说：

\n\n

n   fib(n)\n1   0\n2   1\n3   1\n4   2\n5   3\n6   5\n7   8\n8   13\n9   21\n10  34\n11  55\n12  89\n13  144\n14  233\n15  377\n16  610\n17  987\n18  1597\n19  2584\n20  4181\n21  6765\n22  10946\n23  17711\n24  28657\n25  46368\n26  75025\n27  121393\n28  196418\n29  317811\n30  514229\n31  832040\n32  1346269\n33  2178309\n34  3524578\n35  5702887\n36  9227465\n37  14930352\n38  24157817\n39  39088169\n40  63245986\n41  102334155\n42  165580141\n43  267914296\n44  433494437\n45  701408733\n46  1134903170\n47  1836311903\n48  2971215073\n49  4807526976\n

\n\n

所以你可以看到： #47 之后的斐波那契数不适合 (signed) int。

\n\n

澄清一下：与 C 不同，Java 没有unsigned类型。所以强调这signed int一点已经过时了。

\n