java - Java 中类似斐波那契数列的非递归解决方案是什么？

Question

给出函数的伪代码

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

有没有非递归的方法来做到这一点？

Answer 1

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

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

这只是首先处理“递归”终止条件，然后迭代它通常调用自身的位置。在每次迭代中，您计算​​当前项，然后通过祖 parent 和 parent 轮换这些项。

计算完当前迭代后，无需保留祖 parent ，因为它不再使用。

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

<小时/>

当然，就像斐波那契数列一样，您计算的值上升得非常快，因此，如果您想要最快的解决方案(您应该检查所有性能声明，包括我的)，预先计算的查找表可能是最好的选择走吧。

使用以下 Java 代码创建一个长值表(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 提出了一种甚至不使用迭代的公式化方法。如果您转到their site输入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)