Напишите функцию, которая возвращает n-е число Фибоначчи:
F(0) = 0, F(1) = 1, F(n) = F(n−1) + F(n−2).
// Fib возвращает n-е число Фибоначчи. Для n < 0 или n > 93 паникует.
func Fib(n int) uint64
Примеры
Fib(0) → 0
Fib(1) → 1
Fib(10) → 55
Fib(50) → 12586269025
Fib(93) → 12200160415121876738 (последнее, что помещается в uint64)
Ограничения
0 ≤ n ≤ 93. F(94) в uint64 уже не помещается: для n > 93 и n < 0
функция должна паниковать, а не молча вернуть переполненное значение.- Наивная рекурсия делает O(φⁿ) вызовов:
Fib(93) она не досчитает никогда.
Ожидается O(n) времени и O(1) памяти.
- Устно: как посчитать
F(n) mod m для n до 10¹⁸?
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.