2 个斐波那契数的乘积

Question

我的任务：

给定一个数字，比如说 prod（对于产品），我们搜索两个斐波那契数 F(n) 和 F(n+1) 验证

F(n) * F(n+1) = prod if F(n) * F(n+1) = prod

您的函数 productFib 接受一个整数 (prod) 并返回一个数组：

[F(n), F(n+1), True] else 

F(m) 是最小的，例如 F(m) * F(m+1) > prod

[F(m), F(m+1), False] 

例子：

productFib(714) # should return [21, 34, True], 
            # since F(8) = 21, F(9) = 34 and 714 = 21 * 34

productFib(800) # should return [34, 55, False], 
            # since F(8) = 21, F(9) = 34, F(10) = 55 and 21 * 34 < 800 < 34 * 55

我的代码：

def f(i):
    if i == 0 :
        return 0
    if i == 1 :
        return 1
    return f(i-2) + f(i-1)

def productFib(prod):
    i=1
    final1 = 0
    final2 = 0
    while(f(i)*f(i+1) != prod and f(i)*f(i+1) < prod):
        i += 1
        final1 = f(i)
        final2 = f(i+1)
    if(final1*final2 == prod):
        return [final1,final2,True]
    else:
        return [final1,final2,False]

我是编程新手；这对于大量运行非常缓慢。如何降低时间复杂度？

Answer 1

def productFib(prod):
    a, b = 0, 1
    while prod > a * b:
        a, b = b, a + b
    return [a, b, prod == a * b]