Произведение двух последовательных чисел Фибоначчи - время ожидания кода

Question

Я пытаюсь решить Произведение последовательных чисел Фибоначчи на Codewars в Java.Образцы тестов работают нормально, но когда я нажимаю «Попытка», время ожидания истекает.

В чем может быть моя ошибка?

Подробную информацию о задаче можно найти здесь: https://www.codewars.com/kata/product-of-consecutive-fib-numbers

public class ProdFib { 
public static long[] productFib(long prod) {

int a = 0;
int ta, ta2= 0;
int a2 = 1;

while (a * a2 <= prod){
    ta = a;
    ta2 = a2;
    a2 = a + a2;
    a = ta2;

    if(a * a2 == prod){
    long[] re = new long[]{a,a2,1};
    return re;
    }
    if(a * a2 > prod){
    long[] re = new long[]{a,a2,0};
    return re;
    }
}
return null;
   }
 }

Answer 1

Ваша проблема в том, что вы определяете свои переменные как int вместо long.

Если вы попытаетесь запустить вашу программу с помощью prod 44361286907595736L, она пойдет в бесконечный цикл.Причина этого заключается в том, что при умножении двух int s результат также равен int.Этот продукт является результатом умножения 165580141 и 267914296. Это допустимые числа, но при умножении их число слишком велико для целочисленного переполнения.Таким образом, вы получите число, которое намного ниже, чем 44361286907595736L.и ваш цикл не останавливается.

Если вы определите свои переменные как long, этого не произойдет.Вот немного более читаемая версия вашей программы.

public static long[] productFib(long prod) {

    long prev = 0;
    long curr = 1;
    long multiplied = prev * curr;

    while (multiplied < prod) {
        long temp = curr;
        curr += prev;
        prev = temp;
        multiplied = prev * curr;
    }

    return new long[] { prev, curr, multiplied == prod ? 1 : 0 };

}

Answer 2

Определение проблемы: Вход: продукт - искомый продукт Выход: массив из 3 элементов: {F1, F2, результат}

Где F1 - первое число Фибоначчи, F2 - второе число Фибоначчи, результат равен1, если F1 * F2 = произведение, в противном случае: результат = 0

Эту проблему можно решить более эффективно, используя следующие формулы: 1. Прямая формула для получения n-го числа Фибоначчи.2. Прямая формула для получения индекса заданного числа Фибоначчи.

Вы можете получить соответствующие формулы и пояснения по следующей ссылке: https://en.wikipedia.org/wiki/Fibonacci_number

Идея состоит в том, чтобы получить индексчисло Фибоначчи: sqrt (product)

Затем мы можем перейти к следующему и предыдущему числам Фибоначчи и сравнить их продукты с данным продуктом

Это соответствующий код Java:

private static double phi = (1 + Math.sqrt(5)) / 2;

public static void main(String[] args) { 
  System.out.println(Arrays.toString(fibProd(800))); // [34, 55, 0]
  System.out.println(Arrays.toString(fibProd(714))); // [21, 34, 1]
  System.out.println(Arrays.toString(fibProd(15))); // [3, 5, 1]
  System.out.println(Arrays.toString(fibProd(40))); // [5, 8, 1]
  System.out.println(Arrays.toString(fibProd(2))); // [1, 2, 1]
  System.out.println(Arrays.toString(fibProd(3))); // [2, 3, 0]
}

private static long[] fibProd(long product) {
    long currentIndex = getFibIndex(Math.round(Math.sqrt(product)));
    long currentElement = getFibElement(currentIndex);
    long previousElement = getFibElement(currentIndex - 1);
    long nextElement = getFibElement(currentIndex + 1);

    int c1 = Long.compare(previousElement * currentElement, product);

    if(c1 == 0) {
        return new long[] {previousElement, currentElement, 1};
    }

    int c2 = Long.compare(currentElement * nextElement, product);

    if(c2 == 0) {
        return new long[] {currentElement, nextElement, 1};
    }

    if (c1 < c2) {
        return new long[] {currentElement, nextElement, 0};
    } else {
        return new long[] {previousElement, currentElement, 0};
    }
}

private static long getFibIndex(long item) 
{ 
    double m = item * Math.sqrt(5) + 0.5;
    return Math.round(Math.log(m) / Math.log(phi));
}

private static long getFibElement(long index) {
    return Math.round(Math.pow(phi, index)  / Math.sqrt(5)); 
}

Answer 3

Попробуйте это

public class ProdFib {
public static long[] productFib(long prod) {
    int i = 0;
    int f1 = 0;
    int f2 = 0;
    while ((f(i) * f(i + 1) != prod && f(i) * f(i + 1) < prod)) {
        i += 1;
        f1 = f(i);
        f2 = f(i + 1);
    }
    if (f1 * f2 == prod)
        return new long[] { f1, f2, 1 };
    else
        return new long[] { f1, f2, 0 };
}

public static int f(int i) {
    if (i == 0) {
        return 0;
    }
    if (i == 1) {
        return 1;
    }
    return f(i - 2) + f(i - 1);
}

public static void main(String[] args) {
    long[] r = productFib(1000);
    System.out.println(r[0] + " " + r[1] + " " + r[2]);
}

}