Условие

Числа Фибоначчи, обычно обозначаемые как F(n), формируют последовательность, в которой каждое число является суммой двух предыдущих чисел, начиная с 0 и 1. То есть:

F(0) = 0, F(1) = 1

F(n) = F(n - 1) + F(n - 2), для n >= 2

Требуется реализовать функцию, вычисляющую F(n).

Примеры

Input: n = 2 Output: 1 Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1

Input: n = 3 Output: 2 Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2

Input: n = 4 Output: 3 Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3

Решение

fun fib(n: Int): Int {
    // Если n меньше 2, то это либо F(0) = 0, либо F(1) = 1
    // В этом случае сразу возвращаем n
    if (n < 2) return n

    // Инициализируем два предыдущих значения:
    // prev1 соответствует F(n-2), а prev2 — F(n-1)
    var prev1 = 0 // F(0) = 0
    var prev2 = 1 // F(1) = 1

    // Цикл для вычисления F(n) от 2 до n
    for (i in 2..n) {
        // Текущее значение числа Фибоначчи — это сумма двух предыдущих
        val current = prev1 + prev2
        // Обновляем prev1 и prev2 для следующей итерации
        prev1 = prev2 // Теперь prev1 становится F(n-1)
        prev2 = current // А prev2 становится текущим значением F(n)
    }

    // Возвращаем n-е число Фибоначчи
    return prev2
}

Временная сложность

O(n) — Проходим по числам от 2 до n один раз.

Пространственная сложность

O(1) — Используются только три переменные для хранения текущих и предыдущих значений.