java - 如何计算卢卡斯数？

卢卡斯数字是按如下定义的序列中的数字:

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 。

最佳答案

我认为你得到了反向索引的公式。

自从，



所以，改变
return lucasnum(n + 1) - lucasnum(n + 2);
至
return lucasnum(n + 2) - lucasnum(n + 1);
更快的算法

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

O(1)。使用 Binet's Formula for Lucas Numbers ，但是，由于固定精度浮点运算，这不会为大的 n 值提供准确的结果。

O(log n) 使用递归:

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

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

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

你可以在这里找到公式:

http://mathworld.wolfram.com/FibonacciNumber.html

http://mathworld.wolfram.com/LucasNumber.html

https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form

https://en.wikipedia.orgwiki/Lucas_number#Relationship_to_Fibonacci_numbers

关于java - 如何计算卢卡斯数？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/31792906/