DjangoBB LoFi version

Полная версия: Нужна помощь в оптимизации не очень сложной задачки

Начало » Центр помощи » Нужна помощь в оптимизации не очень сложной задачки

SpyBorgFly

Дек. 28, 2022 17:00:24

 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):
    answer = []
    for n in range(1, 50):
        if prod == Fibonachi(n) * Fibonachi(n+1):
            return [Fibonachi(n), Fibonachi(n+1), True]
            break
        if prod != Fibonachi(n) * Fibonachi(n+1) and ((Fibonachi(n) * Fibonachi(n+1)) < prod) :
            answer.append(Fibonachi(n+1))
            answer.append(Fibonachi(n+2))
            continue
        return [answer[-2], answer[-1], False]

Задача с кодварса 5 кю . https://www.codewars.com/kata/5541f58a944b85ce6d00006a
Набросал такой код, тесты проходит но как я понял выходит из строя на тестах с большими числами(Execution Timed Out (12000 ms)). Так что нужна оптимизация.
Кому лень читать с сайта, тогда условия задачи вкратце

на вход дается число, если это число равняется какому то 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

Прошу помочь c для оптимизацией
Еще есть такой вариант кода

 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):
    answer = []
    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]

py.user.next

Дек. 28, 2022 19:59:01

SpyBorgFly
выходит из строя на тестах с большими числами

Сделай функцию для поиска числа Фибоначчи не через рекурсию, а через цикл.

AD0DE412

Дек. 29, 2022 00:30:45

 import itertools
def Fibonacci(a, b):
    while True:
        yield a
        a, b = b, a + b
def productFib():
    count = 0
    for a, b in itertools.islice(zip(Fibonacci(0, 1), Fibonacci(1, 1)), 2, None):
        print(f'example: {count} ~ {a, b}')
        count += 1
        if count > 10:
            return
'''
example: 0 ~ (1, 2)
example: 1 ~ (2, 3)
example: 2 ~ (3, 5)
example: 3 ~ (5, 8)
example: 4 ~ (8, 13)
example: 5 ~ (13, 21)
example: 6 ~ (21, 34)
example: 7 ~ (34, 55)
example: 8 ~ (55, 89)
example: 9 ~ (89, 144)
example: 10 ~ (144, 233)
'''

xam1816

Дек. 29, 2022 17:09:46

  
def f():
    memory = 0
    a = 0
    b = 1
    def process(n):
        nonlocal a, b, memory
        if n < memory:
            a, b = 0, 1
        memory = n
        while True:
            if a * b == n:
                return a, b, True
            elif a * b > n:
                return a, b, False
            a, b = b, a + b
    return process
productFib = f()
for i in (0, 8, 13, 40, 800, 714, 1000, 1870, 2000):
    print(productFib(i))

AD0DE412

Дек. 29, 2022 17:57:33

эээ фабричные функции … тоже в эту сторону думалось но чет итератор захотелось сделать … у вас неплохо получилось получилось