20

私はフィボナッチ数の反復アルゴリズムに興味があるので、wiki で式を見つけました...簡単に見えるので、Python で試してみました...コンパイルに問題はなく、式は正しく見えます...そうではありませんなぜ間違った出力を与えるのか...私はそれを正しく実装していませんでしたか?

def fib (n): 
    if( n == 0):
        return 0
    else:
        x = 0
        y = 1
        for i in range(1,n):
            z = (x + y)
            x = y
            y = z
            return y

for i in range(10):
    print (fib(i))

出力

0
なし
1
1
1
1
1
1

4

13 に答える 13

63

問題はreturn y、関数のループ内にあることです。そのため、最初の反復の後、既に停止して最初の値 1 を返します。 ただし、nis 0 の場合は関数が0それ自体を返すように作成されn、 is 1 の場合は for ループが 1 回も繰り返されない場合を除きます。いいえreturnが実行されています（したがって、None戻り値）。

これを修正するreturn yには、ループの外側を移動します。

代替実装

KebertX の例に従って、私が個人的に Python で作成するソリューションを次に示します。もちろん、多くのフィボナッチ値を処理する場合は、これら 2 つのソリューションを組み合わせて、数値のキャッシュを作成することもできます。

def f(n):
    a, b = 0, 1
    for i in range(0, n):
        a, b = b, a + b
    return a
于 2013-02-23T23:56:53.823 に答える
5

ループ内で値を返しているため、y の値が 1 より大きくなる前に関数が終了します。

より短く、よりpythonfulなものを提案する場合：

def fibs(n):                                                                                                 
    fibs = [0, 1, 1]                                                                                           
    for f in range(2, n):                                                                                      
        fibs.append(fibs[-1] + fibs[-2])                                                                         
    return fibs[n]

これはアルゴリズムとまったく同じことを行いますが、3 つの一時変数を作成する代わりに、それらをリストに追加し、インデックスによって n 番目のフィボナッチ数を返します。

于 2013-02-24T00:36:02.797 に答える
1

fib(0) では、次の理由で 0 を返しています。

if (n == 0) {
    return 0;
}

fib(1) では、次の理由で 1 が返されます。

y = 1
return y

図（2）では、次の理由で 1 を返しています。

y = 1
return y

...等々。ループ内にある限りreturn y、関数は毎回 for ループの最初の繰り返しで終了します。

これは別のユーザーが思いついた良い解決策です: How to write the Fibonacci Sequence in Python

于 2013-02-23T23:58:13.670 に答える
0

私は別のスレッドでこれに遭遇しました。これは、私が試した他の何よりも大幅に高速であり、多数でタイムアウトすることはありません。ここに数学へのリンクがあります。

def fib(n):
    v1, v2, v3 = 1, 1, 0  
    for rec in bin(n)[3:]: 
        calc = v2*v2
        v1, v2, v3 = v1*v1+calc, (v1+v3)*v2, calc+v3*v3
        if rec=='1':    v1, v2, v3 = v1+v2, v1, v2
    return v2
于 2016-08-31T05:33:05.770 に答える
-1

フィボナッチ数列に次の値を仮定します。

F(0) = 0;

F(1) = 1;

F(2) = 1;

F(3) = 2

N > 2 の値については、次の式でフィボナッチ値を計算します。

F(N) = F(N-1) + F(N-2)

これに対する反復的なアプローチの 1 つは、N = 0 から N = Target_N までのフィボナッチを計算することです。これにより、N-1 と N-2 のフィボナッチの以前の結果を追跡できます。

public int Fibonacci(int N)
{
    // If N is zero return zero
    if(N == 0)
    {
        return 0;
    }

    // If the value of N is one or two return 1
    if( N == 1 || N == 2)
    {
       return 1;
    }

    // Keep track of the fibonacci values for N-1 and N-2
    int N_1 = 1;
    int N_2 = 1;

    // From the bottom-up calculate all the fibonacci values until you 
    // reach the N-1 and N-2 values of the target Fibonacci(N)
    for(int i =3; i < N; i++)
    {
       int temp = N_2;
       N_2 = N_2 + N_1;
       N_1 = temp;
    }

    return N_1 + N_2; 
}
于 2014-08-21T07:53:20.433 に答える
-3 
import time

a,b=0,1
def fibton(n):
    if n==1:
        time.clock()
        return 0,time.clock()
    elif n==2:
        time.clock()
        return 1,time.clock()
    elif n%2==0:
        read="b"
    elif n%2==1:
        read="a"
    else:
        time.clock()
        for i in range(1,int(n/2)):
            a,b=a+b,a+b
        if read=="b":
            return b,time.clock()
        elif read=="a":
            return.a,time.clock()

免責事項: 私は現在モバイル デバイスを使用しており、これは完全に正しくない可能性があります。

このアルゴリズムは他の人々のギャップを利用しており、今では文字通り 2 倍の速さです。bに等しい、aまたはその逆に設定aしてからに設定する代わりにa+b、あと2文字だけで2回行います。また、他の反復アルゴリズムがどのように行われたかに基づいて、速度テストも追加しました。これは、1 秒で約 200,000 番目のフィボナッチ数に到達できるはずです。また、整数の代わりに数値の長さを返します。これには永遠に時間がかかります。

もう 1 つは、組み込みの時計が示すように、10^-6 秒で 2 番目のフィボナッチ数に到達する可能性があります。これは約5^-6でできます。私はすぐにいくつかのより高度なアルゴリズムを取得し、それらを最高速度で改良する予定です。

于 2015-08-23T08:54:25.073 に答える