Генерация ряда Фибоначчи

13. Реализовать последовательности Фибоначчи длиной n

Условие задачи:
Необходимо реализовать метод, который принимает число n и возвращает последовательность Фибоначчи длиной n.

Последовательность начинается с:

0, 1, 1, 2, 3, 5, 8, 13, ...

Каждый следующий элемент равен сумме двух предыдущих.

Пример:

Вход:  n = 7
Выход: [0, 1, 1, 2, 3, 5, 8]

Спойлеры к решению

Подсказки

💡 Для генерации последовательности достаточно хранить два предыдущих числа.
💡 Начальные значения — 0 и 1.
💡 На каждой итерации вычисляй сумму двух предыдущих элементов.
💡 Итеративный подход работает за O(n) и не создаёт лишних рекурсивных вызовов.

Решение

public static List<Integer> generateFibonacci(int n) {
    if (n <= 0) {
        return new ArrayList<>();
    }

    List<Integer> result = new ArrayList<>(n);

    int first = 0;
    int second = 1;

    for (int i = 0; i < n; i++) {
        result.add(first);

        int next = first + second;
        first = second;
        second = next;
    }

    return result;
}

Пример использования:

System.out.println(generateFibonacci(7));

Результат:

[0, 1, 1, 2, 3, 5, 8]

На каждой итерации в результат добавляется текущее число:

result.add(first);

После этого вычисляется следующее:

int next = first + second;
first = second;
second = next;

Таким образом, для вычислений достаточно хранить только два последних значения.

Временная сложность — O(n). Дополнительная память для вычислений — O(1), а для результирующего списка — O(n).

При использовании int последовательность переполнится начиная с F(47). Если нужно поддерживать большие значения n, следует использовать long или BigInteger.