ACM 4744 Brute算法

Question

问题的全部上下文可以在这里看到，详细信息。

此外，您还可以尝试我的Sourcecode来绘制小数字的递归：巴斯丁

我用数学的方法来看这个问题，它是一个嵌套递归，如下所示：

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

所以当我们研究函数被调用的频率时，它看起来像是a^( F(n) ) * b^(F(n+1))，F(N)是n-斐波那契数。所以我的问题是:我如何得到非常巨大的斐波那契数模p，我对此做了大量的研究，阅读了斐波纳契的循环长度，尝试了一些递归，

F(a+b) = F(a+1) * F(b) + F(a)*F(b-1)

但是，当将p分割成两个数字时，似乎需要递归深度(log_2(1.000.000.000) ~=30 )，即使是深度第一次递归也是如此。

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

当我有Fib数时，在我看来乘法和指数不应该是一个问题。

不幸的是没有:/

我还是被这个问题缠住了。计算指数中的斐波那契数首先没有正确地解决问题，这是我在那里应用的一个错误的数学公式：

所以我想到了其他计算公式的方法：

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

但是当斐波纳契数变得很大时，我假设肯定有比计算整个斐波那契数更容易的方法，然后用BigInteger/BigFloat应用离散指数函数。有人给我个提示吗，我看不出有什么进展。谢谢

所以这就是我目前所处的地方，也许只是我错过的一件小事，所以期待着你的回复。

谢谢

Answer 1

如果是关于计算斐波纳契数的话，就有一个非递归的、非迭代的公式。它在荷兰语维基百科页面上有关于斐波纳契数字的显着性，但在英语页面上却没有这么多。

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

来源：斐波纳契

也许你可以用这个公式做点什么。

Answer 2

在计算Fibonacci和Lucas数的各种方法上，您可能会发现我的思考很有帮助。在这里，我展示了如何使用基本上是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‘the和Lucas数与n’the这样的数联系起来。它让我们可以向后工作。因此，要计算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

注意:在讨论递归计算Fibonacci数时，我确实对所需的递归调用数作了一些评论。请注意，这个数字确实与斐波纳契序列本身有很好的关联。这是很容易得到的。