4

私はフィボナッチのDPバージョンについて読んでいました。
Sedgewick で私が見た
int[] T = new int[47]; のは、以前の計算の保存用です。他の場所では、フィボナッチの最大入力が 未満でなければならないことがわかりました92。
これらの数値がどのように表示されるかはわかりません。オーバーフローとサイズに関係していることは理解していますがint、これらの制限がどうなるかはわかりません。
何か助けはありますか？

4

5 に答える 5

10

n 番目のフィボナッチ数に対する閉形式の式であるBinet の公式があり、

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 ビット整数型 (1 ビットが符号に使用されるため、正の数を表すために 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)。

于 2013-02-25T17:07:06.803 に答える
9

フィボナッチ数列は、1.618 (黄金比) の比率で (ほぼ) 指数関数的に増加します。

したがって、対数ベース 1.618 を取得するInteger.MAX_VALUEと、オーバーフローするまでに実行できる反復回数がおよそわかります....

または、計算を行うだけでオーバーフローする時期を経験的に判断することもできます....

于 2013-02-25T10:54:44.890 に答える
4

(signed)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))

これは、フィボナッチのマトリックス形式です。

番号の完全なリスト (オーバーフローしていない限り)

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 に答える