一个测试用例由于运行时错误而失败

Question

我正在 HackerRank 上尝试 Project Euler problem 25。

我尝试使用 Binet 的 Formula.

的蛮力方法

import math

for _ in range(int(input())):
    numLen = int(input())
    for x in range(1, 5000):
        fib = 1/pow(5,.5)*(pow(((1+pow(5,.5))/2),x) - pow(((1-pow(5,.5))/2),x))
        if(numLen == len(str(int(fib)))):
            print(x)
            break

这里 5000 是一个任意数字，基于假设输入不超过这个数字，问题不在这里，因为它是运行时错误，我认为是因为它超出了整数范围（不确定）。

它还可以在不到 0.25 秒的时间内计算出其他测试用例。

我进行了一些搜索，找到了 this。

但是通过那个递推方法：

import math

for _ in range(int(input())):
    a = 1
    b = 0
    n = int(input())
    term = 1
    while len(str(a)) != n:
        a, b = a+b, a
        term+=1
    print (term)

超过 10 秒时超时。

能不能帮我想办法改进第一种方法，优化第二种方法

注意：我尝试将 pow() 值存储在变量中而不是重新计算，但没有太大帮助。

Answer 1

pow(x, y) 总是比 x**y 慢，而且 pow() 方法不能用于长整数。

试试x**y，会快一点

Answer 2

只需在您的示例中使用第二种方法，而不是为输入中的每一行分别计算值，计算值 1...5000 一次并缓存它们：

res = [0]
a = 0
b = 1
term = 1

while len(res) <= 5000:
    a, b = b, a + b
    if len(str(a)) >= len(res):
        res.append(term)
    term += 1

print('\n'.join(str(res[int(input())]) for _ in range(int(input()))))

对于输入 2 3 4，它将产生预期的输出 12 17。在我的机器上预计算这些值大约需要 3 秒。

一个测试用例由于运行时错误而失败

One test case fails due to runtime error

python

math

fibonacci