什么是Java中Fibonacci类序列的非递归解？
ccl*_*lle 13 java algorithm math recursion
给出这个函数的伪代码
f(0) = 1;
f(1) = 3;
f(n) = 3 * f(n - 1) - f(n - 2); // for n >= 2.
有这种非递归方式吗？
pax*_*blo 43
是的,所有递归算法都可以转换为迭代算法.您的问题的递归解决方案类似于(伪代码):
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)
- @ikegami,_all_递归算法可以迭代,如果只是因为你可以管理自己的数据堆栈而不是使用函数堆栈.我怀疑你的意思是尾部递归更容易让_compiler_转换为迭代. (8认同)
- @ikegami对CS中"递归"的含义有一个明确的定义.你可以使用自己的,但如果大多数人不理解你的目的,也不要感到惊讶.(那不是**说你的定义是错误的 - 但我们对这些事情有约定的原因是我们可以谈论事情而不必每次都从地面开始) (4认同)
- 我喜欢维基百科的引用"如果你已经知道什么是递归,请记住答案,否则,找到一个比你更接近道格拉斯霍夫施塔特的人;然后问他或她是什么递归".话虽如此,我认为我们应该关闭讨论(或将其移至讨论区).(错误)引用BillG:"15条评论应该足够_any_回答":-) (4认同)
sdc*_*vvc 12
这里的答案是正确的,但它们在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.有关线性重现的更多信息,请参见此处.
- 人们也可以找到特征值并使用特征方程来评估矩阵功率的矩阵功率较低......哦等等. (4认同)
ype*_*eᵀᴹ 10
如果您的问题是关于是否可以找到函数的等效非递归定义,则应搜索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;
}
所有递归解决方案都可以转换为迭代解决方案(反之亦然,请参阅此文章),尽管如果递归解决方案以尾递归形式更容易.
上述算法可以理解为原始递归的动态编程解决方案,它非常有效,因为它只需要在迭代中的每个点保存前两个值.