Сложность: easy
Числа Фибоначчи, обычно обозначаемые как F(n), образуют последовательность, называемую последовательностью Фибоначчи, так что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,
F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1.
Дано n, вычислите F(n).
Пример:
Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
👨💻 Алгоритм:
1⃣Проверка начального условия
Если N <= 1, вернуть N.
2⃣Инициализация переменных
Инициализируйте current значением 0. Инициализируйте prev1 значением 1, что будет представлять fib(N-1) при вычислении текущего значения. Инициализируйте prev2 значением 0, что будет представлять fib(N-2) при вычислении текущего значения.
3⃣Итерация и вычисление
Итерация от 2 до N включительно. На каждой итерации: установите current как сумму prev1 и prev2. Обновите prev2 значением prev1. Обновите prev1 значением current. Вернуть значение current после завершения итерации.
😎 Решение:
class Solution {
func fib(_ N: Int) -> Int {
if N <= 1 {
return N
}
var current = 0
var prev1 = 1
var prev2 = 0
for _ in 2...N {
current = prev1 + prev2
prev2 = prev1
prev1 = current
}
return current
}
}Ставь 👍 и забирай 📚 Базу знаний