Java 中类斐波那契数列的非递归解决方案是什么? [英] What is a non recursive solution for Fibonacci-like sequence in Java?
问题描述
给定这个函数的伪代码
f(0) = 1;
f(1) = 3;
f(n) = 3 * f(n - 1) - f(n - 2); // for n >= 2.
有没有一种非递归的方式来做到这一点?
Is there a non recursive way of doing this?
推荐答案
是的，所有递归算法都可以转换为迭代算法.您的问题的递归解决方案类似于(伪代码):
Yes, all recursive algorithms can be converted into iterative ones. The recursive solution to your problem is something like (pseudo-code):
def f(n):
if n == 0: return 1
if n == 1: return 3
return 3 * f(n-1) - f(n-2)
由于您只需记住前两项即可计算当前项，因此您可以使用如下伪代码:
Since you only have to remember the previous two terms to calculate the current one, you can use something like the following pseudo-code:
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
这只是先处理递归"终止条件，然后在通常调用自身的地方进行迭代.在每次迭代中，您计算当前项，然后通过祖父项和父项轮换项.
This simply handles the "recursive" termination condition first then iterates where it would normally call itself. At each iteration, you calculate the current term, then rotate the terms through the grandparent and parent.
计算当前迭代后，无需再保留祖父母，因为它不再使用.
There is no need to keep the grandparent around once you've calculated the current iteration since it's no longer used.
事实上，可以说迭代解决方案更好(从性能的角度来看)，因为项不会像在递归解决方案中那样重新计算.递归解决方案确实有一定的优雅(递归解决方案通常如此).
In fact, it could be said that the iterative solution is better (from a performance viewpoint) since terms are not recalculated as they are in the recursive solution. The recursive solution does have a certain elegance about it though (recursive solutions generally do).
当然，就像斐波那契数列一样，您计算的值上升得非常快，因此，如果您想要最快的解决方案(您应该检查所有性能声明，包括我的)，预先计算的查找表可能是方法去.
Of course, like the Fibonacci sequence, that value you calculate rises very quickly so, if you want what's possibly the fastest solution (you should check all performance claims, including mine), a pre-calculated lookup table may be the way to go.
使用以下 Java 代码创建一个长值表(while 条件只是捕捉溢出的狡猾技巧，这是您可以停止构建数组的点):
Using the following Java code to create a table of long values (that while condition is just a sneaky trick to catch overflow, which is the point at which you can stop building the array):
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 (" };");
}
}
为您提供了一个数组定义，您可以将其插入到查找函数中，如下例所示:
gives you an array definition that you can just plug in to a lookup function, as per the following example:
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)，你会得到公式:
Interestingly enough, WolframAlpha comes up with a formulaic approach that doesn't even use iteration. If you go to their site and enter f(0)=1, f(1)=3, f(n)=3f(n-1)-f(n-2), you'll get back the formula:
不幸的是，它可能没有迭代那么快，因为它使用浮点数，因为输入值的数量有限，因此可以放入 Java long 中.几乎可以肯定(但是，您需要再次检查)比表查找慢.
Unfortunately, it may not be as fast as the iteration, given the limited number of input values that result in something that can fit in a Java long, since it uses floating point. It's almost certainly (but, again, you would need to check this) slower than a table lookup.
而且，它在数学世界中可能是完美的，其中非无限存储等现实世界的限制不会发挥作用，但可能由于 IEEE 精度的限制，它会在 的更高值处崩溃n.
And, it's probably perfect in the world of maths where real-world limits like non-infinite storage don't come into play but, possibly due to the limits of IEEE precision, it breaks down at higher values of n.
以下函数等效于该表达式和查找解决方案:
The following functions are the equivalent of that expression and the lookup solution:
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];
}
现在我们需要一个主线来比较它们:
Now we need a mainline to compare them:
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
看起来不错，还有一些:
Looking good up to here, some more:
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)
上述结果非常接近，并且错误中的位数与结果中的位数成正比，这表明这可能是一个精度损失问题.
The fact that the above are tantalisingly close, and that the number of digits in the error is proportional to the number of digits in the result, indicates it's probably a loss-of-precision problem.
此后，公式函数开始返回最大 long 值:
After this point, the formulaic function just starts returning the maximum long value:
BAD: 44: 1100087778366101931, 922337203685477580 (177750574680624351)
BAD: 45: 2880067194370816120, 922337203685477580 (1957729990685338540)
BAD: 46: 7540113804746346429, 922337203685477580 (6617776601060868849)
然后我们的查找功能也崩溃了，因为数字太大了很长时间:
And then our lookup function breaks down as well since the numbers are too big for a long:
BAD: 47: -1, 922337203685477580 (922337203685477581)
BAD: 48: -1, 922337203685477580 (922337203685477581)
BAD: 49: -1, 922337203685477580 (922337203685477581)
这篇关于Java 中类斐波那契数列的非递归解决方案是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
