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，您基本上为内存中的相同数据分配了三个不同的名称。您所做的任何更改都a将反映在b等等c。

对于需要三个单独变量的问题，更改__init__函数的一种方法如下：

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

我不确定您是否需要对这个问题使用矩阵求幂。不幸的是，我对 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 回答
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但你应该返回s.b，s.c否则你会少得到一个斐波那契。

3）该行temp.a=temp.b=temp.c=temp.d=1不是必需的，因为构造函数完成了工作。此外它是错误的，因为d应该是0。

4）如果它们不使用，为什么是mul和类函数。它没有害处，但它们应该是expself@staticmethod

5）同样，它没有害处，但你的第二个递归调用是不必要的复杂。写吧：

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