Java программа: числа Фибоначчи

Описание задачи

Последовательность Фибоначчи — это ряд чисел, в котором каждое следующее число равно сумме двух предыдущих, а первые два числа равны 0 и 1:

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

Формально: F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) при n ≥ 2.

Программа должна вывести первые n чисел последовательности.

Что нужно знать

Переменные и литералы — переменные и присваивание
Типы данных в Java — целые типы данных
Операторы в Java — арифметические операторы
Hello World на Java — структура программы

Решение

Итеративный вариант — самый эффективный, со сложностью O(n) по времени и O(1) по памяти:

public class Fibonacci {
    public static void main(String[] args) {
        int count = 10;

        long first = 0;
        long second = 1;

        System.out.print("Первые " + count + " чисел Фибоначчи: ");
        for (int i = 0; i < count; i++) {
            System.out.print(first + " ");

            long next = first + second;
            first = second;
            second = next;
        }
        System.out.println();
    }
}

Ожидаемый вывод:

Первые 10 чисел Фибоначчи: 0 1 1 2 3 5 8 13 21 34

Как это работает

Заводим две переменные first и second, которые хранят два последних числа последовательности. В начале они равны 0 и 1.
На каждой итерации: - выводим текущее значение first (это очередной элемент последовательности); - вычисляем next = first + second — следующее число; - сдвигаем окно на одну позицию: first принимает старое значение second, second принимает next.
Цикл выполняется count раз — выводится count элементов.

Совет

Тип long нужен потому, что F(46) уже не помещается в int. Для очень больших n (более 90) понадобится BigInteger.

Альтернативные решения

Рекурсивный вариант (неэффективный, для понимания):

public class FibonacciRecursive {
    public static void main(String[] args) {
        int count = 10;
        for (int i = 0; i < count; i++) {
            System.out.print(fib(i) + " ");
        }
        System.out.println();
    }

    static long fib(int n) {
        if (n < 2) {
            return n;
        }
        return fib(n - 1) + fib(n - 2);
    }
}

Ожидаемый вывод:

0 1 1 2 3 5 8 13 21 34

Предупреждение

Прямая рекурсия имеет экспоненциальную сложность O(2ⁿ) — для n > 40 будет работать недопустимо медленно. На практике используйте итеративный вариант или мемоизацию.

Большие числа через ``BigInteger``:

import java.math.BigInteger;

public class FibonacciBig {
    public static void main(String[] args) {
        int count = 100;
        BigInteger a = BigInteger.ZERO;
        BigInteger b = BigInteger.ONE;

        System.out.println("F(" + (count - 1) + ") =");
        for (int i = 0; i < count - 1; i++) {
            BigInteger next = a.add(b);
            a = b;
            b = next;
        }
        System.out.println(a);
    }
}

Ожидаемый вывод:

F(99) =
218922995834555169026

Примечание

Лицензия и источники