我正在尝试解决Project Euler中的第25题。以下是我目前得到的:
def fibonacci(length):
fibs = [0,1]
while length > len(fibs):
fibs.append(fibs[-1] + fibs[-2])
return fibs
fibs = fibonacci(5000)
for i in fibs:
if len(str(i)) > 1000:
print i
## The location of the number in the Fibonacci set.
print [j for j, x in enumerate(fibs) if x == i]
我测试的每一个数字(包括一些较大的数字)都是匹配的，但是欧拉项目不接受我得到的答案。
我读到答案是第4782个数字，但我得到的第一个超过1000位的数字是第4787个，
11867216745258291596767088485966669273798582100095758927648586619975930687764095025968215177396570693265703962438125699711941059562545194266075961811883693134762216371218311196004424123489176045121333888565534924242378605373120526670329845322631737678903926970677861161240351447136066048164999599442542656514905088616976279305745609791746515632977790194938965236778055329967326038544356209745856855159058933476416258769264398373862584107011986781891656652294354303384242672408623790331963965457196174228574314820977014549061641307451101774166736940218594168337251710513138183086237827524393177246011800953414994670315197696419455768988692973700193372678236023166645886460311356376355559165284374295661676047742503016358708348137445254264644759334748027290043966390891843744407845769620260120918661264249498568399416752809338209739872047617689422485537053988895817801983866648336679027270843804302586168051835624516823216354234081479331553304809262608491851078404280454207286577699580222132259241827433
欧拉项目说我试过的每个答案都是错的。(显然我还没有尝试4782，因为那将是作弊。)
我非常接近了，很明显有些地方出了问题，但是什么?
您正在检查len(str(i)) > 1000，而根据问题陈述，您应该检查len(str(i)) == 1000。
另外，你把答案中的数字错误地理解为斐波那契数。实际上，如果你仔细阅读，它是fib函数被调用的次数。你的斐波那契数字4782是正确的。
根据第25个问题的解决者论坛，你是正确的。
和第二个以1322开头的大数…不是斐波那契数
检查x是否为斐波那契数的函数:
import decimal
def check_fib(n):
a, b = decimal.Decimal(5*(n**2) + 4), decimal.Decimal(5*(n**2) - 4)
return any(int(x.sqrt())==x for x in (a, b))
正如thkang指出的，男生的数字是错误的，参见wims的评论。你的算法有效。
def fibonacci(length):
fibs = [0,1]
while length > len(fibs):
fibs.append(fibs[-1] + fibs[-2])
return fibs
fibs = fibonacci(5000)
for i,n in enumerate(fibs):
if len(str(n)) >= 1000:
print i
print n
break
这是我用来解决它的方法，我得到的答案和你一样。
def fib():
x, y = 0, 1
while True:
yield x
x += y
x, y = y, x
f = fib()
for i,n in enumerate(f):
if len(str(n)) >= 1000:
print i
print n
break
除了问题(和问题)之外，您还可以使用生成功能斐波那契函数以直接的方式获得斐波那契数。
from decimal import Decimal
from math import sqrt
#sqrt_5 = Decimal(sqrt(5))
sqrt_5 = decimal.Decimal(5).sqrt() # As thkang suggested!
fib = lambda n: (1/sqrt_5)*( (2/(-1+ sqrt_5))**(n+1) - (2/(-1-sqrt_5))**(n+1))
for i in xrange(10000):
if fib(i).adjusted()+1 == 1000:
print i+1
4782是我的代码的第一个1000位数字。
输出:[4782,4783,4784,4785 4786].
关于使用生成函数的fibonnaci公式http://www.math.ufl.edu/~joelar/generatingfibonacci.pdf
不用编程就能得到解决方案。
我们知道，一个数m在十进制表示中至少使用k位数字，如果log_10 (m)> = k - 1。
所以基本上我们要做的就是解出不等式:
999年log_10 (fn)> =
使用F_n的显式形式，你知道它是最接近于((1+Sqrt(5))/2)^n/Sqrt(5)的整数。我们可以用F_n的近似。请记住，这里有一个小错误，但我们稍后会处理它。
所以不等式变成了:
log_10(((1 +√6 (5)/2)^ n/Sqrt (5))> = 999
在使用一些对数恒等式和一些排序之后，它看起来像:
n> = (999 + log_10 (Sqrt (5)))/log_10((1 +√6 (5)/2)~ = 4781.8592
所以我们的最终答案应该在这个附近，让我们讨论一下我之前提到的错误。近似误差是(1-√5)/2)^n/√5。(1-√(5))/2~=-0.68，其绝对值小于1，故取幂后，越来越接近于0。(-0.68)^4781是一个非常小的数字，所以F_n的对数与我们使用的近似值(这些数字大约是1000)之间的差甚至更小。在不精确计算的情况下，考虑到F_n的大小，这种差异可以完全忽略。因此，解是最小的整数n，其中n>=4781.8592，即4782。这个生成器给出整数，我已经测试了它到fib(21)
from decimal import Decimal
from math import sqrt
while True:
#sqrt_5 = Decimal(sqrt(5))
sqrt_5 = Decimal(5).sqrt() # As thkang suggested!
fib = lambda n: (1/sqrt_5)*( (2/(-1+ sqrt_5))**(n) - (2/(-1-sqrt_5))**(n))
a=input()
if a=="x":
break
d=round(fib(int(a)))
print("t"+str(d))
要退出程序，只需键入x