Оптимизация задачи на python
Задача с кодварса 5 кю python . https://www.codewars.com/kata/5541f58a944b85ce6d00006a Набросал такой код, тесты проходит но как я понял выходит из строя на тестах с большими числами(Execution Timed Out (12000 ms)).
def Fibonachi(n):
if n == 1:
return 1
if n == 2:
return 1
if n > 2:
return Fibonachi(n - 2) + Fibonachi(n - 1)
def productFib(prod):
n = 1
while Fibonachi(n) * Fibonachi(n+1) < prod:
n += 1
if prod == Fibonachi(n) * Fibonachi(n + 1):
return [Fibonachi(n), Fibonachi(n + 1), True]
break
if Fibonachi(n) * Fibonachi(n+1) > prod:
return [Fibonachi(n), Fibonachi(n+1), False]
Кому лень читать с сайта, тогда условия задачи вкратце
на вход дается число, если это число равняется какому-то n фибоначчи * n+1 фибоначчи нужно вывести
n фибоначи, n+1 фибоначи, True
в противном случае алгоритм такой:
productFib(800) # should return (34, 55, false),
# since F(8) = 21, F(9) = 34, F(10) = 55 and 21 * 34 < 800 < 34 * 55
Не совсем понимаю в чем ошибка и как можно оптимизировать код, молю о помощи.
Ответы (1 шт):
Если у вас есть пара последовательных чисел Фибоначчи (fn-1, fn) следующая за ней пара вычисляется как (fn, fn-1 + fn). На Питоне получается особенно компактно:
def productFib(prod):
a, b = 0, 1
while a * b < prod:
a, b = b, a + b
return [a, b, a * b == prod]
P.S. Это решение одно из самых популярных на codewars. Есть решение ещё быстрее, но поля книги слишком узки для него.