我正在尝试欧拉计划problem 25在 HackerRank 上。
我尝试使用 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() 值存储在变量中而不是重新计算,但没有太大帮助。
最佳答案
只需在示例中使用第二种方法,而不是为输入中的每一行单独计算值,计算值 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 秒。
关于python - 由于运行时错误,一个测试用例失败,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36711359/