计算Python中斐波那契数列的第n个项

Question

下面的代码是使用t的各种测试案例的矩阵幂计算python中的n项和斐波那契序列。但是该程序给出了荒谬的输出。请告诉我我错了。当我在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

Answer 1

我不确定是否需要使用矩阵幂运算来解决此问题。不幸的是，我对Python类还不太了解。但是，以下代码完成了问题标题所要的操作：查找第n个斐波那契数。下面我将其描述为F_n。注意低n值的初始条件。def fibN( n ):"""fibonacci: int -> intReturns F_n.Note: F_1 = 0, F_2 = 1, F_3 = 1, F_4 = 2"""n = abs( int( n ))if n == 0:&nbsp; &nbsp; fib = 0elif n == 1:&nbsp; &nbsp; fib = 1else:&nbsp; &nbsp; counter = 2&nbsp;&nbsp;&nbsp; &nbsp; f0 = 0&nbsp; &nbsp; f1 = 1&nbsp; &nbsp; fib = f0 + f1&nbsp; &nbsp; while counter <= n:&nbsp; &nbsp; &nbsp; &nbsp; fib = f0 + f1&nbsp; &nbsp; &nbsp; &nbsp; f0 = f1&nbsp; &nbsp; &nbsp; &nbsp; f1 = fib&nbsp; &nbsp; &nbsp; &nbsp; counter += 1return fib