0

Задача с кодварса 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

Не совсем понимаю в чем ошибка и как можно оптимизировать код, молю о помощи.

4
  • 2
    для вычисления чисел фибоначчи лучше использовать цикл, а не рекурсию. либо для рекурсии использовать декоратор functools.lru_cache
    – Danis
    28 дек 2022 в 18:06
  • 2
    Ну это уже не смешно, десятки ответов и других источников есть, как считать фибоначчи за нормальное время, а не этот изврат.
    – MBo
    28 дек 2022 в 18:07
  • Благодарю,lru_cache помог
    – zxc inside
    28 дек 2022 в 18:30

1 ответ 1

3

Если у вас есть пара последовательных чисел Фибоначчи (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. Есть решение ещё быстрее, но поля книги слишком узки для него.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.