3

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]

私がテストしたすべての数 (いくつかの大きなものを含む) は一致しますが、Project Euler は私が得た答えを受け入れていません。

答えは 4782 番目の数字だと読みましたが、1000 桁を超える最初の数字は 4787 番目であることがわかりました。

11867216745258291596767088485966669273798582100095758927648586619975930687764095025968215177396570693265703962438125699711941059562545194266075961811883693134762216371218311196004424123489176045121333888565534924242378605373120526670329845322631737678903926970677861161240351447136066048164999599442542656514905088616976279305745609791746515632977790194938965236778055329967326038544356209745856855159058933476416258769264398373862584107011986781891656652294354303384242672408623790331963965457196174228574314820977014549061641307451101774166736940218594168337251710513138183086237827524393177246011800953414994670315197696419455768988692973700193372678236023166645886460311356376355559165284374295661676047742503016358708348137445254264644759334748027290043966390891843744407845769620260120918661264249498568399416752809338209739872047617689422485537053988895817801983866648336679027270843804302586168051835624516823216354234081479331553304809262608491851078404280454207286577699580222132259241827433

Project Euler は、私が試したすべての答えが間違っていると言っています。(明らかに、私はまだ 4782 を試していません。それはチートになるからです。)

私は興味をそそられるほど近づいており、明らかに何かが間違っていますが、何ですか?

4

6 に答える 6

2

25番目の問題の解決者向けのprojecteulerフォーラムによると、あなたは正しいです。

1322 で始まる 2 番目の大きな数字は... フィボナッチ数ではありません。

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))
于 2013-04-16T00:59:52.500 に答える
1

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
于 2013-04-16T01:17:33.983 に答える
1

質問 (および問題) に加えて、Generating Functionology Fibonnaci Function を使用して、直接的な方法でフィボナッチ数を取得できます。

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].

生成関数を使用したフィボナッチ公式についてhttp://www.math.ufl.edu/~joelar/generatingfibonacci.pdf

于 2013-04-16T01:29:15.760 に答える
0

このジェネレーターは整数を与え、私はそれをテストしました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

于 2013-10-20T21:15:16.680 に答える