计算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.dt=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 -> 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