0

次のコードは、さまざまなテストケース t の行列累乗を使用して、Python で n 項 og フィボナッチ数列を計算するものです。しかし、プログラムはばかげた出力を返します。どこが間違っているか教えてください。C++ でコードを実行すると、完全に実行されます。

class matrix:
    def __init__(self):
        self.a=self.b=self.c=1
        self.d=0

    def mul(self,e,f):
        ret = matrix()
        ret.a=(e.a*f.a)+(e.b+f.c)
        ret.b=(e.a*f.b)+(e.b+f.d)
        ret.c=(e.c*f.a)+(e.d+f.c)
        ret.d=(e.c*f.b)+(e.d+f.d)
        return ret

    def exp(self,a,p):
        if(p==0):
            temp=matrix()
            temp.a=temp.b=temp.c=temp.d=1
            return temp
        if(p==1):
            return a
        if(p%2==0):
            return self.exp(self.mul(a,a),p/2)
        else:
            return self.mul(a,self.exp(self.mul(a,a),(p-1)/2))

    def fib(self,n):
        if (n==0):
            return 0
        if (n==1):
            return 1
        s=matrix()
        s=self.exp(s,n)
        return s.d

t=int(raw_input())
while(t>0):
    v=matrix()
    n=int(raw_input())
    print v.fib(n)
    t=t-1
4

3 に答える 3

1

問題はあなたの__init__機能にあります。Python では、いわゆる変数は、メモリ内のデータへの単なる「タグ」です。C/C++ と比較すると、これらはポインターと考えることができます。を割り当てるself.a = self.b = self.cと、基本的にメモリ内の同じデータに 3 つの異なる名前を割り当てます。で行った変更は、 などaに反映されます。bc

3 つの個別の変数が必要な問題の場合、__init__関数を変更する 1 つの方法は次のようになります。

self.a, self.b, self.c = 1, 1, 1

または使用できますcopy。copy()新しいメモリ位置を割り当てるように Python に指示し、右側のタグをその位置に割り当てます。詳細については、このhttp://docs.python.org/2/library/copy.htmlの公式ドキュメントを参照してください。これについては、 Python チュートリアル: 浅いコピーと深いコピーで短いウォークスルーを読むこともできます。

于 2013-05-27T07:36:16.927 に答える
0

重要な順にいくつかの問題があります。

1) 掛け算が間違っています。合計がある右側の乗算に注意してください):

def mul(self,e,f):
    ret = matrix()
    ret.a=(e.a*f.a)+(e.b*f.c)
    ret.b=(e.a*f.b)+(e.b*f.d)
    ret.c=(e.c*f.a)+(e.d*f.c)
    ret.d=(e.c*f.b)+(e.d*f.d)
    return ret

2) 最後の行では、そうしますreturn s.dが、戻る必要があります。そうしないと、フィボナッチが 1 つ少なくなりますs.b。s.c

3)temp.a=temp.b=temp.c=temp.d=1コンストラクターが作業を行うため、行は必要ありません。それに、そうあるdべきだから、それは間違っている0。

4)を使用しないのになぜmulとクラス関数なのか。害はありませんが、そうすべきですexpself@staticmethod

5) 繰り返しますが、害はありませんが、2 回目の再帰呼び出しは不必要に複雑です。書くだけ：

    return matrix.mul(a,matrix.exp(a, p-1))
于 2013-05-27T08:27:41.610 に答える
0

この問題に行列指数を使用する必要があるかどうかはわかりません。残念ながら、私は Python のクラスについてまだよく知りません。ただし、次のコードは、質問の見出しが望んでいることを実行します: n 番目のフィボナッチ数を見つけます。以下では、これを F_n と記述します。n の値が小さい場合の初期条件に注意してください。

def fibN( n ):
"""
fibonacci: int -> int
Returns F_n.
Note: F_1 = 0, F_2 = 1, F_3 = 1, F_4 = 2
"""
n = abs( int( n ))
if n == 0:
    fib = 0
elif n == 1:
    fib = 1
else:
    counter = 2  
    f0 = 0
    f1 = 1
    fib = f0 + f1
    while counter <= n:
        fib = f0 + f1
        f0 = f1
        f1 = fib
        counter += 1
return fib
于 2013-08-01T21:43:22.867 に答える