如何计算卢卡斯号？

Question

Lucas数是按如下顺序定义的数字：

L(n) = 2 if n = 0

L(n) = 1 if n = 1

否则

L(n) = L(n - 1) + L(n - 2)

这是我的代码：

public class Lucas {
    public static int lucasnum(int n) {
        if (n >= 0) {
            if (n == 0)
                return 2;
            else if (n == 1)
                return 1;
            else
                return lucasnum(n - 1) + lucasnum(n - 2);
        }
        else{
            if (n == 0)
                return -2;
            else if (n == -1)
                return -1;
            else
                return lucasnum(n + 1) - lucasnum(n + 2);
        }
    }

    public static void main(String[] args) {
        System.out.println(Lucas.lucasnum(-5));
    }
}

但我对负数有些问题。如果是n == -5，它必须返回-11，但是我上面的代码返回3。

Answer 1

我想你向后得到了负指数的公式。

既然，

L(n+2)=L(n+1)+L(n) => L(n)=L(n+2)-L(n+1)

所以，改变

return lucasnum(n + 1) - lucasnum(n + 2);

至

return lucasnum(n + 2) - lucasnum(n + 1);

快速算法

你的算法是O( n )算法，对于大的n是慢的，你可以做得更快。

• O(1)。然而，使用卢卡斯数的比内公式，由于固定精度的浮点算法，这不能给出n的大值的精确结果。
• O(log n)使用递归： 设f(n)是Fibonacci序列

f(0) = 0，f(1) = 1，f(n) = f(n-1) + f(n-2)

用递归方法在O(log )时间内计算Fibonacci数：

f(2n-1) = f(n)^2 + f(n-1)^2 f(2n) = f(n)^2 + 2*f(n-1)*f(n)

然后用以下方法计算Lucas数：

L(n) = f(n-1) + f(n+1)

您可以在这里找到公式：

- [http://mathworld.wolfram.com/FibonacciNumber.html](http://mathworld.wolfram.com/FibonacciNumber.html)
- [http://mathworld.wolfram.com/LucasNumber.html](http://mathworld.wolfram.com/LucasNumber.html)
- [https://en.wikipedia.org/wiki/Fibonacci\_number#Matrix\_form](https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form)
- [https://en.wikipedia.orgwiki/Lucas\_number#Relationship\_to\_Fibonacci\_numbers](https://en.wikipedia.orgwiki/Lucas_number#Relationship_to_Fibonacci_numbers)

​

Answer 2

变化

return lucasnum(n + 1) - lucasnum(n + 2);

至

return lucasnum(n + 2) - lucasnum(n + 1);