0

問題の完全なコンテキストはここで見ることができます 詳細。

また、私のソースコードを試して、少数の再帰をプロットすることもできます： Pastebin

私はこの問題を数学的な方法で見ており、ネストされた再帰であり、次のようになります。

Function Find(integer n, function func)
If n=1
   For i = 1 to a do func()
Elseif n=2
   For i = 1 to b do func()
Else Find(n-1,Find(n-2,func))

Function Main
   Find(n,funny)

モジュロ演算を使用しないMathematicaでの私の実装は次のとおりです。

$IterationLimit = Infinity
Clear[A]

A [a_, b_, f_, 1] := A [a, b, f, 1, p] = (f a);
A [a_, b_, f_, 2] := A [a, b, f, 2, p] = (f b);
A [a_, b_, f_, n_] := 
A [a, b, f, n, p] = (A[a, b, A[a, b, f, n - 2], n - 1]);

これにより、一般的なaとbの優れた出力が明らかになります。

A[a, b, funny, 1]
a funny
A[a, b, funny, 2]
b funny
A[a, b, funny, 3]
a b funny
A[a, b, funny, 4]
a b^2 funny
A[a, b, funny, 5]
a^2 b^3 funny
A[a, b, funny, 6]
a^3 b^5 funny

したがって、Funcが呼び出される頻度を見ると、n番目のフィボナッチ数としてF（n）を使用したa ^（F（n））* b ^（F（n + 1））のように見えます。だから私の問題は：どうすれば非常に巨大なフィボナッチ数を法として得ることができますか、私はこれについて多くの研究を行い、フィボナッチのサイクル長を読み、いくつかの再帰を試しました：

F（a + b）= F（a + 1）* F（b）+ F（a）* F（b-1）

しかし、pを2つの数値に分割する場合、最初の再帰が深くても、再帰の深さ（log_2（1.000.000.000）〜= 30）のように見えます。

a= floor(n/2)
b= ceiling(n/2)

私がフィボナッチ数を持っているとき、乗算とべき乗は私の観点では問題ではないはずです。

残念ながら違います ：/

私はまだ問題で立ち往生しています。指数のフィボナッチ数を計算しても、最初は問題が正しく解決されませんでした。そこで適用した数学式が間違っていました：/

だから私は式を計算する他の方法を考えました：

(a^(Fibonacci(n-2))*b^(Fibonacci(n-1))) mod p

しかし、フィボナッチ数が非常に大きくなるにつれて、フィボナッチ数全体を計算してから、BigInteger/BigFloatを使用して離散指数関数を適用するよりも簡単な方法があるはずだと思います。誰かが私にヒントを持っていますか、私はそれ以上の進歩は見られません。ありがとう

だから、これは私が今のところいるところです、私が見逃しているほんの少しのことかもしれませんので、あなたの返事を楽しみにしています

ありがとう

4

2 に答える 2

0

フィボナッチ数とルーカス数を計算するためのさまざまな方法について、私の熟考が役に立つかもしれません。そこでは、基本的に O(log2(n)) である再帰スキームを使用して計算を行う方法を示します。大きなフィボナッチ数に対して非常にうまく機能します。そして、それをすべてモジュロで行う場合は、計算に大きな整数ツールを使用する必要さえありません。これは、巨大なフィボナッチ数の場合でも驚くほど高速です。下のこれは適度に大きいだけです。

fibonacci(10000)
ans =
    33644764876431783266621612005107543310302148460680063906564769974680
081442166662368155595513633734025582065332680836159373734790483865268263
040892463056431887354544369559827491606602099884183933864652731300088830
269235673613135117579297437854413752130520504347701602264758318906527890
855154366159582987279682987510631200575428783453215515103870818298969791
613127856265033195487140214287532698187962046936097879900350962302291026
368131493195275630227837628441540360584402572114334961180023091208287046
088923962328835461505776583271252546093591128203925285393434620904245248
929403901706233888991085841065183173360437470737908552631764325733993712
871937587746897479926305837065742830161637408969178426378624212835258112
820516370298089332099905707920064367426202389783111470054074998459250360
633560933883831923386783056136435351892133279732908133732642652633989763
922723407882928177953580570993691049175470808931841056146322338217465637
321248226383092103297701648054726243842374862411453093812206564914032751
086643394517512161526545361333111314042436854805106765843493523836959653
428071768775328348234345557366719731392746273629108210679280784718035329
131176778924659089938635459327894523777674406192240337638674004021330343
297496902028328145933418826817683893072003634795623117103101291953169794
607632737589253530772552375943788434504067715555779056450443016640119462
580972216729758615026968443146952034614932291105970676243268515992834709
891284706740862008587135016260312071903172086094081298321581077282076353
186624611278245537208532365305775956430072517744315051539600905168603220
349163222640885248852433158051534849622434848299380905070483482449327453
732624567755879089187190803662058009594743150052402532709746995318770724
376825907419939632265984147498193609285223945039707165443156421328157688
908058783183404917434556270520223564846495196112460268313970975069382648
706613264507665074611512677522748621598642530711298441182622661057163515
069260029861704945425047491378115154139941550671256271197133252763631939
606902895650288268608362241082050562430701794976171121233066073310059947
366875

トリックは簡単です。単純に、2n 番目のフィボナッチ数とルーカス数を n 番目の数に関連付けます。それは私たちが後方に働くことを可能にします。したがって、F(n) と L(n) を計算するには、F(n/2) と L(n/2) を知る必要があります。明らかに、これは n が偶数である限り機能します。n が奇数の場合、再帰的に下に移動できる同様のスキームがあります。

キックについては、モジュラスを受け入れるように上記のツールを変更しました。したがって、インデックスが 1e15 のフィボナッチ数の下 6 桁を計算するには、約 1/6 秒かかりました。

tic,[Fn,Ln] = fibonacci(1e15,1000000),toc
Elapsed time is 0.161468 seconds.

Fn =
    546875

Ln =
    328127

注: フィボナッチ数を計算するための再帰についての説明で、必要な再帰呼び出しの数についていくつかコメントします。その数が実際にフィボナッチ数列自体に非常にうまく関連していることを確認してください. これは簡単に導き出されます。

于 2012-05-03T17:19:56.537 に答える
0

フィボナッチ数の計算に関するものであれば、非再帰的、非反復的な式があります。フィボナッチ数に関するオランダのウィキペディアのページで目立つように取り上げられていますが、英語のページではあまり取り上げられていません。

F(n) = ( ( 1 + sqrt(5) ) ^ n - ( 1- sqrt(5) ) ^ n ) / (2 ^ n * sqrt(5))

http://upload.wikimedia.org/wikipedia/nl/math/1/7/4/1747ee745fbe1fbf10fb3d9de36b8927.png

ソース: http://nl.wikipedia.org/wiki/Rij_van_Fibonacci

この式で何かできることがあるかもしれません。

于 2012-05-03T10:42:42.193 に答える