Как рассчитать номер Лукаса?

Question

числа Люка являются числами в последовательности, определенной следующим образом:

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 (1). Используйте Binet's Formula for Lucas Numbers. Однако это не дает точных результатов для больших значений n из-за арифметики с фиксированной точностью с плавающей запятой.

• O (журнал N) с помощью рекурсии:

  Пусть F (п) последовательность Фибоначчи

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

  числа Вычислить Фибоначчи в O (Log N) времени с рекурсия:

  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

Answer 2

Изменить

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

в

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