Программа Java последовательность Fibonacci

Проблема в том, что из-за того, что вы используете простую рекурсию, вы многократно переоцениваете F (n), поэтому время выполнения экспоненциально.

Есть два простых способа исправить это. :

1) Кэшировать значения F (n), когда они оцениваются в первый раз. Прежде чем оценивать F (n), проверьте кеш, чтобы убедиться, что вы уже рассчитали его для этого n.

2) Используйте итерационный подход: вычислите F (1), F (2), F (3) и т. Д. .. пока не наберете нужный номер.

Если вы воспользуетесь наивным подходом, вы получите огромное количество одинаковых вычислений, т.е. для вычисления fib (n) вам нужно вычислить fib (n-1) и fib (n-2). Затем, чтобы вычислить fib (n-1), вы должны вычислить fib (n-2) и fib (n-3) и т. Д. Лучше сделать обратное. Вы вычисляете, начиная с fib (0), fib (1), fib (2), и сохраняете значения в таблице. Затем для вычисления последующих значений используются значения, хранящиеся в таблице (массиве). Это также называется мемоизацией. Попробуйте это, и вы сможете вычислять большие числа Фиби.

Проблема в не JAVA, а то, как вы реализуете свой алгоритм Фибоначчи. Вы вычисляете одни и те же значения много раз, что замедляет вашу программу.

Попробуйте что-нибудь вроде этого: Фибоначчи с мемоизацией

Создайте массив со 100 значениями, затем, когда вы вычисляете значение для Fib (n), сохраните его в массиве и используйте этот массив для получения значений Fib (n-1) и Fib (n-2).

Если вы вызываете Fib (100) без сохранения каких-либо ранее вычисленных значений, вы заставите свою среду выполнения Java взорваться.

Псевдокод:

array[0] = 0;
array[1] = 1;
for 2:100
array[n] = array[n-1] + array[n-2];

Есть несколько решений. Самый простой - использовать мемоизацию . Также существует формула Бине , которая даст вам n-е число Фибоначчи за постоянное время.

Для мемоизации вы сохраняете свои результаты для F [a_i] на карте или в каком-либо списке. В наивной рекурсии, например, вы вычисляете F [4] сотни тысяч раз. Сохраняя все эти результаты по мере их нахождения, рекурсия перестает развиваться как дерево и выглядит как простое итеративное решение.

Если это не домашнее задание, используйте формулу Бине. Это самый быстрый из доступных методов.

Проблема в том, что ваш алгоритм, хотя и математически чистый (и красивый), не очень хорош.
Для каждого числа, которое он хочет вычислить, он должен вычислить два меньших, которые, в свою очередь, должны вычислить два меньших, и т.д. Ваш текущий алгоритм имеет нотацию Big O сложность примерно O (1.6 ⁿ ) , поэтому для очень больших чисел (например, 100) это занимает много времени.

В этой книге, Структура и интерпретация компьютерных программ есть хорошая диаграмма : показывает, что происходит, когда вы генерируете fib 5 с помощью вашего алгоритма

_{(источник: mit.edu )}

Самый простой способ - сохранить F - 1 и F - 2, чтобы не приходилось каждый раз рассчитывать их с нуля. Другими словами, вместо рекурсии используйте цикл. Тогда означает, что сложность алгоритма изменяется от O (1,6 ⁿ ) до O (n).

Попробуйте этот пример, он вычисляет миллионное число Фибоначчи за разумный промежуток времени без какой-либо потери точности.

import java.math.BigInteger;

/*
250000th fib # is: 36356117010939561826426 .... 10243516470957309231046875
Time to compute: 3.5 seconds.
1000000th fib # is: 1953282128707757731632 .... 93411568996526838242546875
Time to compute: 58.1 seconds.
*/
public class Fib {
    public static void main(String... args) {
        int place = args.length > 0 ? Integer.parseInt(args[0]) : 1000 * 1000;
        long start = System.nanoTime();
        BigInteger fibNumber = fib(place);
        long time = System.nanoTime() - start;

        System.out.println(place + "th fib # is: " + fibNumber);
        System.out.printf("Time to compute: %5.1f seconds.%n", time / 1.0e9);
    }

    private static BigInteger fib(int place) {
        BigInteger a = new BigInteger("0");
        BigInteger b = new BigInteger("1");
        while (place-- > 1) {
            BigInteger t = b;
            b = a.add(b);
            a = t;
        }
        return b;
    }
}

Это код на Python, который можно легко преобразовать в C / Java. Первое рекурсивное, второе - итеративное решение.

def fibo(n, i=1, s=1, s_1=0):
    if n <= i: return s
    else: return fibo(n, i+1, s+s_1, s)


def fibo_iter_code(n):
    s, s_1 = 1, 0
    for i in range(n-1):
       temp = s
       s, s_1 = s+s_1, temp
       print(s)