Код работает крайне медленно и не печатает вывод

Question

Я работаю над Project Euler problem # 2 :

Каждый новый термин в последовательности Фибоначчи генерируется путем добавления двух предыдущих терминов.Начиная с 1 и 2, первые 10 терминов будут:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Найтисумма всех четных членов в последовательности, которые не превышают четырех миллионов.

Мой код:

public class Two {
    public static void main(String[] args) {
        Two obj = new Two();
        int sum = 0, i = 1;

        while (obj.fibonacci(i) < 4000001) {    
            if (obj.fibonacci(i) % 2 == 0) {
                sum += obj.fibonacci(i);
                i++;
            }
        }
        System.out.println(sum);
    }

    public int fibonacci(int n) {
        if (n == 0) {
            return -1;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 3;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }
}

Пожалуйста, помогите мне, что не так с этим кодомэто когда я запускаю это.Он не показывает вывод на консоль, и общее время будет более 5 минут

Спасибо

Answer 1

Вы застряли в бесконечном цикле, поскольку увеличиваете i только тогда, когда его мод 2 равен 0. Вам нужно переместить i ++ ниже.

while (obj.fibonacci(i) <= 4000000) {
    if (obj.fibonacci(i) % 2 == 0) {
        sum += obj.fibonacci(i);
    }
    i++;
}

Как уже упоминалось в других комментарияхЭто не лучший способ решить проблему Фибоначчи, но она решает вашу ошибку / проблему.Вам следует пройти через отладчик, если вы не понимаете, почему, и вы заметите, что используете много рекурсивных вызовов, которые уже были решены.Поскольку вы вызываете его много раз в коде, (в операторе while и в операторе if) вы увеличили время обработки.

Вот пример ваших вызовов Фибоначчи, обратите внимание, как вы вызываетеметод Фибоначчи на одном и том же числе несколько раз:

1
2
3
2
1
4
3
2
1
2
5

Answer 2

Как уже упоминалось, i ++ необходимо вывести за пределы проверки на равномерность, иначе вы застрянете в цикле.

Но у вас есть немного большая проблема.Последовательность Фибоначчи начинается с

... 1, 2, 3, ...

, где вместо этого у вас есть ... 1,3, ... что означает, что вы получите неправильные результаты.Вы должны иметь:

// ...
if (n == 2) {
    return 2;
// ...

Answer 3

Улучшение решения @ Blastfurnace заключается в том, что каждое третье значение четное.

public static void main(String[] args) {
    long sum = 0;
    int runs = 30000;
    for (int i=0;i< runs;i++) {
        sum = sumEvenFib();
    }
    long start = System.nanoTime();
    for (int i=0;i< runs;i++) {
        sum = sumEvenFib();
    }
    long time = System.nanoTime() - start;
    System.out.println(sum+" took "+time/runs+" ns avg");
}

private static long sumEvenFib() {
    int sum = 0;
    for(int f1 = 1, f2 = 2;f2 < 4000001;) {
        sum += f2;
        int f3 = f1 + f2;
        f1 = f3 + f2;
        f2 = f1 + f3;
    }
    return sum;
}

На моем старом labtop это занимает около 40 нс. или 0,000000040 секунд.

Answer 4

Нет смысла хранить всю последовательность чисел Фибоначчи в этом случае. Вы можете просто «пройтись» по последовательности с несколькими локальными переменными, суммируя их по ходу.

int fib2 = 0, fib1 = 1, fib0 = fib1 + fib2;
int sum = 0;

while (fib0 <= N)
{
    if (fib0 % 2 == 0) sum += fib0;
    fib2 = fib1;
    fib1 = fib0;
    fib0 = fib1 + fib2;
}

Answer 5

Хотя ваше решение может работать, оно довольно дорогое, поскольку пересчитывает уже полученные результаты.

Используя рекурсию в этом случае, чтобы иметь значение fibonacci(4), вы рекурсивно добавляете значения fibonacci(3) и fibonacci(2), которые вы уже рассчитали ранее.

Попробуйте сохранить значения в списке, а не пересчитывать их постоянно:

List<Long> fibonacci = new ArrayList<Long>();

// First terms
fibonacci.add(-1L); // 0 is dummy, sequence starts at 1
fibonacci.add(1L);
fibonacci.add(2L);

for (int i = 3; fibonacci.get(i - 1) + fibonacci.get(i - 2) < 4000001; i++) {
    long u = fibonacci.get(i - 1) + fibonacci.get(i - 2);
    fibonacci.add(i, u);
}

Используя эту технику, вы можете вычислить последовательность Фибоначчи до 4000000 менее чем за 2 секунды (как я пытался на моем компьютере).

Затем просто добавьте некоторый код для вычисления суммы внутри цикла: -)

Answer 6

Одна из ваших проблем в том, что вы чрезмерно используете рекурсию. Вы должны попытаться сохранить результаты, чтобы не пересчитывать все каждый раз.

Answer 7

Я думаю, что вы можете улучшить Фибоначчи следующим образом:

def fib(x)
        if(x==0 or x==1) then
                return x;
        end
        a,b = 0,1
        (x-1).times{ a,b = b,a+b; }
        return b;
end

Другими словами, преобразовать рекурсию в итерацию.

Answer 8

Я думаю, что вопрос уже неоднозначен. Сумма всех четных значений должна быть ниже 4 миллионов, или же наибольшее четное число должно быть ниже 4 миллионов?