5

我制作了这段代码..我需要充分利用它..我真的需要计算斐波那契数的最佳性能..请帮助..

我已经阅读了一些此类计算的代码，我认为我得到了最好的..

帮我解决这个问题.. plz ..

ps：我真的需要BigInteger ..我将计算大量数字的斐波那契

ps2：我用这个算法计算了一些大数字，我得到了很好的响应时间..但我需要知道它是否可以更好

ps3：要运行此代码，您需要使用此 VM 参数-Xss16384k(StackSize)

public class Fibonacci {

    private static BigInteger[] fibTmp = { BigInteger.valueOf(0), BigInteger.valueOf(1) };

    public static BigInteger fibonacci(long v) {

        BigInteger fib = BigInteger.valueOf(0);

        if (v == 1) {

            fib = BigInteger.valueOf(1);

        } else if (v == 0) {

            fib = BigInteger.valueOf(0);

        } else {

            BigInteger v1 = fibonacci(v - 1);
            BigInteger v2 = fibTmp[(int) (v - 2)];

            fib = v1.add(v2);
        }

        synchronized (fibTmp) {

            if (fibTmp.length - 1 < v)
                fibTmp = Arrays.copyOf(fibTmp, (int) (v + 10));

            fibTmp[(int) v] = fib;
        }

        return fib;
    }
}
4

3 回答 3

7

是的，有更好的方法。这是一种log(n)经过测试且非常有效的方法，用于计算具有任意精度的斐波那契值，给定一个正整数作为输入。该算法改编自SICP练习 1.19的解决方案：

public static BigInteger fibonacci(int n) {

    int count = n;
    BigInteger tmpA, tmpP;
    BigInteger a = BigInteger.ONE;
    BigInteger b = BigInteger.ZERO;
    BigInteger p = BigInteger.ZERO;
    BigInteger q = BigInteger.ONE;
    BigInteger two = new BigInteger("2");

    while (count != 0) {

        if ((count & 1) == 0) {
            tmpP = p.multiply(p).add(q.multiply(q));
            q = two.multiply(p.multiply(q)).add(q.multiply(q));
            p = tmpP;
            count >>= 1;
        }

        else {
            tmpA = b.multiply(q).add(a.multiply(q).add(a.multiply(p)));
            b = b.multiply(p).add(a.multiply(q));
            a = tmpA;
            count--;
        }

    }

    return b;  

}

在本书的链接章节中，解释了它是如何工作的（向下滚动到练习 1.19），并指出：

这是一种以对数步数计算斐波那契数的巧妙算法……此练习由 Joe Stoy 建议，基于安妮 Kaldewaij 中的一个示例。1990.编程：算法的推导。

当然，如果需要一遍又一遍地计算相同的值，可以通过记忆已经计算的结果来进一步提高性能，例如使用映射来存储以前的值。

于 2013-02-26T16:15:38.680 回答
4

您的实现不适用于任何体面的数字，因为它会使堆栈溢出。

我看不出有任何理由在这里使用递归。递归性很漂亮，但通常更重（它取决于语言）。这是一个带有简单for循环的工作实现：

private static BigInteger[] fibTmp = {BigInteger.ZERO, BigInteger.ONE};
private static int maxCached = 1;
public static BigInteger fibonacci(int v) {
    if (fibTmp.length<=v) {
        fibTmp = Arrays.copyOf(fibTmp, v*5/4);
    }
    for (; maxCached<v;) {
        maxCached++;
        BigInteger v1 = fibTmp[maxCached - 1];
        BigInteger v2 = fibTmp[maxCached - 2];
        fibTmp[maxCached] = v1.add(v2);
    }
    return fibTmp[v];
}

这是一种直接实现，无需在文献中寻找有效的斐波那契算法。你最好去找他们。

另请注意，这种基于缓存的实现是内存成本高的，并且只有在多次调用该函数时才有意义。

于 2013-02-26T16:08:47.103 回答
0

首先，您使用的是递归，这在时间和空间复杂性方面都不是很有效。您应该使用迭代方法。

然后，如果额外的内存或空间不会破坏并且性能确实很关键，那么您可能需要预先计算所有您想稍后计算的数字并将它们存储在数组或磁盘中，如果它对您来说太多的话记忆。稍后您可以在恒定时间内获得该值。

于 2013-02-26T16:12:13.000 回答