什么是Java中Fibonacci类序列的非递归解决方案?

给出这个函数的伪代码

f(0) = 1; f(1) = 3; f(n) = 3 * f(n - 1) - f(n - 2); // for n >= 2. 

有这种非递归方式吗?

是的,所有递归算法都可以转换为迭代算法。 您的问题的递归解决方案类似于(伪代码):

 def f(n): if n == 0: return 1 if n == 1: return 3 return 3 * f(n-1) - f(n-2) 

由于您只需要记住前两个术语来计算当前的术语,您可以使用类似下面的伪代码:

 def f(n): if n == 0: return 1 if n == 1: return 3 grandparent = 1 parent = 3 for i = 2 to n: me = 3 * parent - grandparent grandparent = parent parent = me return me 

这简单地处理“递归”终止条件,然后迭代它通常称之为自身的位置。 在每次迭代中,您计算​​当前术语,然后通过祖父母和父级旋转术语。

一旦你计算了当前的迭代,就不需要保留祖父母了,因为它已经不再使用了。

事实上,可以说迭代解决方案更好(从性能角度来看),因为术语不会像在递归解决方案中那样重新计算。 递归解决方案确实有一定的优雅(递归解决方案一般)。


当然,就像Fibonacci序列一样,你计算的那个值会很快上升,所以,如果你想要什么可能是最快的解决方案(你应该检查所有性能声明,包括我的),预先计算的查找表可能就是这样。

使用以下Java代码创建一个long值表( while条件只是一个偷偷摸摸的技巧来捕获溢出,这是你可以停止构建数组的点):

 class GenLookup { public static void main(String args[]) { long a = 1, b = 3, c; System.out.print ("long lookup[] = { " + a + "L, " + b + "L"); c = 3 * b - a; while ((c + a) / 3 == b) { System.out.print (", " + c + "L"); a = b; b = c; c = 3 * b - a; } System.out.println (" };"); } } 

为您提供了一个数组定义,您可以将其插入查找函数,如下例所示:

 public static long fn (int n) { long lookup[] = { 1L, 3L, 8L, 21L, 55L, 144L, 377L, 987L, 2584L, 6765L, 17711L, 46368L, 121393L, 317811L, 832040L, 2178309L, 5702887L, 14930352L, 39088169L, 102334155L, 267914296L, 701408733L, 1836311903L, 4807526976L, 12586269025L, 32951280099L, 86267571272L, 225851433717L, 591286729879L, 1548008755920L, 4052739537881L, 10610209857723L, 27777890035288L, 72723460248141L, 190392490709135L, 498454011879264L, 1304969544928657L, 3416454622906707L, 8944394323791464L, 23416728348467685L, 61305790721611591L, 160500643816367088L, 420196140727489673L, 1100087778366101931L, 2880067194370816120L, 7540113804746346429L }; if ((n < 1) || (n > lookup.length)) return -1L; return lookup[n-1]; } 

有趣的是,WolframAlpha提出了一种甚至不使用迭代的公式化方法。 如果你去他们的网站并输入f(0)=1, f(1)=3, f(n)=3f(n-1)-f(n-2) ,你将得到公式:

在此处输入图像描述

不幸的是,它可能没有迭代那么快,因为输入值的数量有限导致某些东西可以适合Java long ,因为它使用浮点。 几乎可以肯定(但是,你需要检查一下)比表查找慢。

并且,它在数学世界中可能是完美的,其中像非无限存储这样的现实世界限制不起作用,但是,可能由于IEEE精度的限制,它在较高的n值处分解。

以下函数等效于该表达式和查找解决方案:

 class CheckWolf { public static long fn2 (int n) { return (long)( (5.0 - 3.0 * Math.sqrt(5.0)) * Math.pow(((3.0 - Math.sqrt(5.0)) / 2.0), n-1) + (5.0 + 3.0 * Math.sqrt(5.0)) * Math.pow(((3.0 + Math.sqrt(5.0)) / 2.0), n-1) ) / 10; } public static long fn (int n) { long lookup[] = { 1L, 3L, 8L, 21L, 55L, 144L, 377L, 987L, 2584L, 6765L, 17711L, 46368L, 121393L, 317811L, 832040L, 2178309L, 5702887L, 14930352L, 39088169L, 102334155L, 267914296L, 701408733L, 1836311903L, 4807526976L, 12586269025L, 32951280099L, 86267571272L, 225851433717L, 591286729879L, 1548008755920L, 4052739537881L, 10610209857723L, 27777890035288L, 72723460248141L, 190392490709135L, 498454011879264L, 1304969544928657L, 3416454622906707L, 8944394323791464L, 23416728348467685L, 61305790721611591L, 160500643816367088L, 420196140727489673L, 1100087778366101931L, 2880067194370816120L, 7540113804746346429L }; if ((n < 1) || (n > lookup.length)) return -1L; return lookup[n-1]; } 

现在我们需要一条主线来比较它们:

  public static void main(String args[]) { for (int i = 1; i < 50; i++) if (fn(i) != fn2(i)) System.out.println ("BAD: " + i + ": " + fn(i) + ", " + fn2(i) + " (" + Math.abs(fn(i) - fn2(i)) + ")"); else System.out.println ("GOOD: " + i + ": " + fn(i) + ", " + fn2(i)); } } 

这将输出:

 GOOD: 1: 1, 1 GOOD: 2: 3, 3 GOOD: 3: 8, 8 GOOD: 4: 21, 21 GOOD: 5: 55, 55 GOOD: 6: 144, 144 GOOD: 7: 377, 377 GOOD: 8: 987, 987 GOOD: 9: 2584, 2584 GOOD: 10: 6765, 6765 GOOD: 11: 17711, 17711 GOOD: 12: 46368, 46368 GOOD: 13: 121393, 121393 GOOD: 14: 317811, 317811 GOOD: 15: 832040, 832040 GOOD: 16: 2178309, 2178309 GOOD: 17: 5702887, 5702887 GOOD: 18: 14930352, 14930352 GOOD: 19: 39088169, 39088169 GOOD: 20: 102334155, 102334155 GOOD: 21: 267914296, 267914296 GOOD: 22: 701408733, 701408733 GOOD: 23: 1836311903, 1836311903 GOOD: 24: 4807526976, 4807526976 GOOD: 25: 12586269025, 12586269025 

看起来很好,还有更多:

 GOOD: 26: 32951280099, 32951280099 GOOD: 27: 86267571272, 86267571272 GOOD: 28: 225851433717, 225851433717 GOOD: 29: 591286729879, 591286729879 GOOD: 30: 1548008755920, 1548008755920 GOOD: 31: 4052739537881, 4052739537881 GOOD: 32: 10610209857723, 10610209857723 GOOD: 33: 27777890035288, 27777890035288 GOOD: 34: 72723460248141, 72723460248141 GOOD: 35: 190392490709135, 190392490709135 GOOD: 36: 498454011879264, 498454011879264 

但后来事情开始出现问题:

 BAD: 37: 1304969544928657, 1304969544928658 (1) BAD: 38: 3416454622906707, 3416454622906709 (2) BAD: 39: 8944394323791464, 8944394323791472 (8) BAD: 40: 23416728348467685, 23416728348467705 (20) BAD: 41: 61305790721611591, 61305790721611648 (57) BAD: 42: 160500643816367088, 160500643816367232 (144) BAD: 43: 420196140727489673, 420196140727490048 (375) 

事实上,上述非常接近,并且错误中的位数与结果中的位数成正比,这表明它可能是精度损失问题。

在此之后,公式函数才开始返回最大长值:

 BAD: 44: 1100087778366101931, 922337203685477580 (177750574680624351) BAD: 45: 2880067194370816120, 922337203685477580 (1957729990685338540) BAD: 46: 7540113804746346429, 922337203685477580 (6617776601060868849) 

然后我们的查找函数也会崩溃,因为数字太长了很长时间:

 BAD: 47: -1, 922337203685477580 (922337203685477581) BAD: 48: -1, 922337203685477580 (922337203685477581) BAD: 49: -1, 922337203685477580 (922337203685477581) 

这里的答案是正确的,但它们在O(n)中工作,而你可以在O(log n)中执行,指数级更快。 观察那个

 [f(n) ] = [3 -1] [f(n-1)] [f(n-1)] [1 0] [f(n-2)] 

设v n为向量[f(n),f(n-1)],A为上述矩阵,因此得到v n = A v n-1 ,因此v n = A n-1 v 1 。 使用二进制求幂计算矩阵A的幂 (n-1)次幂并将其乘以v 1 。 有关线性重现的更多信息,请参见此处 。

如果您的问题是关于是否可以找到函数的等效非递归定义,则应搜索Fibonacci序列的属性。

您的序列可以通过写Fibonacci(没有前2个数字)并删除每个第2个数字来找到:1,3,8,21,55,144,……

 sqrt5 = sqrt(5) phi = ( 1 + sqrt5 ) / 2 fibonacci(n) = round( power( phi, n ) / sqrt5 ) f(n) = fibonacci( 2*n + 2 ) 

这很简单,在Java中,解决方案看起来像这样:

 public int f(int n) { int tmp; int a = 3; int b = 1; for (int i = 0; i < n; i++) { tmp = a; a = 3 * a - b; b = tmp; } return b; } 

所有递归解决方案都可以转换为迭代解决方案(反之亦然,请参阅此文章 ),尽管如果递归解决方案以尾递归forms更容易。

上述算法可以理解为原始递归的动态编程解决方案,它非常有效,因为它只需要在迭代中的每个点保存前两个值。

[糟糕,我认为这是一个Perl问题。 尽管如此,代码应该对Java开发人员足够可读。 ]

这实际上只是将递归移动到userland,但您可以使用:

 sub f { my ($n) = @_; my @f = (1,3); $f[$_] = 3 * $f[$_-1]- $f[$_-2] for 2 .. $n; return $f[$n]; } 

当然,这需要缓存。 没有必要重新计算我们已经知道的值。

 my @f = (1,3); sub f { my ($n) = @_; $f[$_] = 3 * $f[$_-1]- $f[$_-2] for @f .. $n; return $f[$n]; } 

函数是根据自身定义的,所以在某种意义上,任何实现都是递归的,除非有一些数学家来告诉我们f(n)可以在不评估f(n-1)f(n-2)情况下进行求值。 正如其他人所表明的那样,有一种方法可以在Java函数中实现它,而不会调用自身。

 def func(n): f= array(n+1) f[0]=1 f[1]=3 for i in 2:n : f[i] = 3*f[i-1]-f[i-2] return f[n] 

Fibonacci系列数字序列开头为:0,1,1,2,3,5,8,13,21,34,55 ….

对于n> 1和两个初始条件,F(0)= 1和F(1)= 1,这可以通过简单递归关系F(n)= F(n-1)+ F(n-2)来定义

算法Fibonacci

//计算第n个Fibonacci数

//输入:非负整数

//输出:第n个Fibonacci数

 1. Begin Fibo 2. integer n, i; 3. if n<=1 then 4. return n; 5. else 6. F(0)<-0; F(1)<-1; 7. for i<-2 to n do 8. F(i)<-F(i-1)+F(i-2); 9. F(i-2)=F(i-2); 10. F(i-1)=F(i); 11. done 12. end if 13. end Fibo 

这里只是一个具有最小代码行和最大灵活性的函数。

您可以简单地添加任何“初始值”和任何其他递归“函数”。

 def fib(n): fibs = [1, 3] # <-- your initial values here if n == 1: return fibs[0] if n == 2: return fibs[:1] for i in range(2, n): fibs.append(3*fibs[-1] - fibs[-2]) # <-- your function here return fibs 

结果是:

 n=10 print(fib(n)) [1, 3, 8, 21, 55, 144, 377, 987, 2584, 6765] 

根据@paxdiablo的要求,我正在回答这个问题。 它是递归关系,可以非递归地求解,类似于另一个答案中提到的斐波纳契序列。 原来是(Python表示法)。

 def f(n): return int((13**0.5-3)/(2*13**0.5)*((3-13**0.5)/2)**n + (0.5+3/(2*13**0.5))*((3+13**0.5)/2)**n) 

然而,由于浮点精度有限这个论坛很可能不适用于大n。 给定的python版本在n = 30时失败:

 >>> print ([f(n) == 3 * f(n-1) + f(n-2) for n in range(2, 30)]) [True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, False] >>> print([f(n) for n in range(30)]) [1, 3, 10, 33, 109, 360, 1189, 3927, 12970, 42837, 141481, 467280, 1543321, 5097243, 16835050, 55602393, 183642229, 606529080, 2003229469, 6616217487, 21851881930, 72171863277, 238367471761, 787274278560, 2600190307441, 8587845200883, 28363725910090, 93679022931153, 309400794703549, 1021881407041801] 

警告:我使用了“+”而不是“ – ”,因此公式错误。 看评论。