下面的代码是使用各种测试用例t的矩阵求幂来计算python中的第n项fibonacci序列输出。请告诉我我在哪里错了。什么时候我用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
有几个问题,按重要性排序:
1)你的乘法是错的。注意右边有和的乘法):
2)在最后一行中,您执行},否则您将少得到一个斐波那契。在
return s.d
,但您应该返回s.b
或{3)行}。在
temp.a=temp.b=temp.c=temp.d=1
不是必需的,因为构造函数完成了这项工作。另外它是错误的,因为d
应该是{4)如果
mul
和exp
不使用self
类函数,为什么它们是。这没有害处,但应该是@staticmethod
5)同样,这没有什么害处,但您的第二次递归调用是不必要的复杂。写下:
^{pr2}$问题在于您的}中,依此类推。在
__init__
函数。在python中,所谓的变量只是内存中数据的“标记”。与C/C++相比,这些可以被看作指针。当您分配self.a = self.b = self.c
时,您基本上是在为内存中的相同数据分配三个不同的名称。您在a
中所做的任何更改都将反映在b
和{对于需要三个独立变量的问题,更改
__init__
函数的一种方法如下:或者您可以使用
copy
。copy()
告诉python分配一个新的内存位置,然后将右侧的标记分配给该位置。有关更多信息,请阅读有关此http://docs.python.org/2/library/copy.html的官方文档。您也可以在Python Tutorial: Shallow and Deep-copy中阅读关于此问题的简短介绍我不确定是否需要使用矩阵求幂来解决这个问题。不幸的是,我还不太了解Python类。但是,下面的代码执行问题标题想要的:找到第n个Fibonacci数。下面我将其描述为F_n。注意n的低值的初始条件
相关问题 更多 >
编程相关推荐