Задача: 509. Fibonacci Number
Числа Фибоначчи, обычно обозначаемые как 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 после завершения итерации.
😎 Решение:
public class Solution {
public int Fib(int N) {
if (N <= 1) return N;
int current = 0, prev1 = 1, prev2 = 0;
for (int i = 2; i <= N; i++) {
current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return current;
}
}👉Новости 👉База вопросов