问题描述
以前，我在这个问题上发布了一个问题，回答得很好. 在python类中实现合并排序功能，错误然而，关于类中的递归，仍有一些让我感到困惑的地方.在上面的链接问题中，如果我在递归子例程中添加了前缀self.，则会得到与类输出中下面产生的错误完全相同的错误(本文中的第三段代码).我知道为什么会这样； object.karatsuba()仅将self作为其输入，但是所编码的方法要求另外2，因此会出现错误.
Previously I posted a question on this subject and it was answered quite well. Implementing merge sort function in python class, errors And yet there is still something that escapes me about recursion in a class. In the linked problem above, if I added prefixive self. to the recursion subroutine, I get the exact same error that is produced below in the class output (third block of code in this post). I understand why this happens; object.karatsuba() only takes self as its input, and yet the method as is coded asks for 2 besides, hence the error.
请查看下面的代码，然后查看我对第三个代码块后面的解决方案的直觉.
例如:我有一个不希望在类中使用的karatsuba乘法的有效实现.标准课堂乘法在课堂上效果很好，但是...
For example: I have a working implementation of karatsuba multiplication that doesn't want to work in a class. Standard classroom multiplication works just fine in a class, but...
这是类之外的工作代码:
This is the working code outside of a class:
def zeroPad(numberString, zeros, left = True):
"""Return the string with zeros added to the left or right."""
for i in range(zeros):
if left:
numberString = '0' + numberString
else:
numberString = numberString + '0'
return numberString
def karatsubaMultiplication(x ,y):
"""Multiply two integers using Karatsuba's algorithm."""
#convert to strings for easy access to digits
x = str(x)
y = str(y)
#base case for recursion
if len(x) == 1 and len(y) == 1:
return int(x) * int(y)
if len(x) < len(y):
x = zeroPad(x, len(y) - len(x))
elif len(y) < len(x):
y = zeroPad(y, len(x) - len(y))
n = len(x)
j = n//2
#for odd digit integers
if (n % 2) != 0:
j += 1
BZeroPadding = n - j
AZeroPadding = BZeroPadding * 2
a = int(x[:j])
b = int(x[j:])
c = int(y[:j])
d = int(y[j:])
#recursively calculate
ac = karatsubaMultiplication(a, c)
bd = karatsubaMultiplication(b, d)
k = karatsubaMultiplication(a + b, c + d)
A = int(zeroPad(str(ac), AZeroPadding, False))
B = int(zeroPad(str(k - ac - bd), BZeroPadding, False))
return A + B + bd
这是一个在第39行失败的类中的代码:
And this is the code inside a class that fails on line 39:
class Karatsuba(object):
def __init__(self, x, y):
self.x = x
self.y = y
def zeroPad(self, numberString, zeros, left = True):
"""Return the string with zeros added to the left or right."""
for i in range(zeros):
if left:
numberString = '0' + numberString
else:
numberString = numberString + '0'
return numberString
def karatsuba(self):
"""Multiply two integers using Karatsuba's algorithm."""
#convert to strings for easy access to digits
self.x = str(self.x)
self.y = str(self.y)
#base case for recursion
if len(self.x) == 1 and len(self.y) == 1:
return int(self.x) * int(self.y)
if len(self.x) < len(self.y):
self.x = self.zeroPad(self.x, len(self.y) - len(self.x))
elif len(self.y) < len(self.x):
self.y = self.zeroPad(self.y, len(self.x) - len(self.y))
n = len(self.x)
j = n//2
#for odd digit integers
if (n % 2) != 0:
j += 1
BZeroPadding = n - j
AZeroPadding = BZeroPadding * 2
a = int(self.x[:j])
b = int(self.x[j:])
c = int(self.y[:j])
d = int(self.y[j:])
#recursively calculate
ac = self.karatsuba(a, c)
bd = self.karatsuba(b, d)
k = self.karatsuba(a + b, c + d)
A = int(self.zeroPad(str(ac), AZeroPadding, False))
B = int(self.zeroPad(str(k - ac - bd), BZeroPadding, False))
return A + B + bd
错误的类版本会生成以下输出:
The faulty class version generates the following output:
x = 234523546643636
y = 325352354534656
x = Karatsuba(x,y)
x.karatsuba()
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-5-aa1c267478ee> in <module>()
4 x = Karatsuba(x,y)
5
----> 6 x.karatsuba()
<ipython-input-1-1d1e9825dcc5> in karatsuba(self)
37 d = int(self.y[j:])
38 #recursively calculate
---> 39 ac = self.karatsuba(a, c)
40 bd = self.karatsuba(b, d)
41 k = self.karatsuba(a + b, c + d)
TypeError: karatsuba() takes 1 positional argument but 3 were given
我最初的直觉是遵循顶部段落链接问题中概述的解决方案，例如:
My initial intuition was to follow the solution outlined in the top paragraph linked question as such:
class Karatsuba(object):
def __init__(self, x, y):
self.x = x
self.y = y
def zeroPad(self, numberString, zeros, left = True):
"""Return the string with zeros added to the left or right."""
for i in range(zeros):
if left:
numberString = '0' + numberString
else:
numberString = numberString + '0'
return numberString
def karatsuba(self):
"""Multiply two integers using Karatsuba's algorithm."""
#convert to strings for easy access to digits
self.x = str(self.x)
self.y = str(self.y)
#base case for recursion
if len(self.x) == 1 and len(self.y) == 1:
return int(self.x) * int(self.y)
if len(self.x) < len(self.y):
self.x = self.zeroPad(self.x, len(self.y) - len(self.x))
elif len(self.y) < len(self.x):
self.y = self.zeroPad(self.y, len(self.x) - len(self.y))
n = len(self.x)
j = n//2
#for odd digit integers
if (n % 2) != 0:
j += 1
BZeroPadding = n - j
AZeroPadding = BZeroPadding * 2
self.a = int(self.x[:j])
self.b = int(self.x[j:])
self.c = int(self.y[:j])
self.d = int(self.y[j:])
#recursively calculate
# ac = self.karatsuba(self.a, self.c)
# bd = self.karatsuba(self.b, self.d)
ac = Karatsuba(self.a, self.c)
ac.karatsuba()
bd = Karatsuba(self.b, self.d)
bd.karatsuba()
k = Karatsuba(self.a + self.b, self.c + self.d)
k.karatsuba()
# k = self.karatsuba(self.a + self.b, self.c + self.d)
A = int(self.zeroPad(str(ac), AZeroPadding, False))
B = int(self.zeroPad(str(k - ac - bd), BZeroPadding, False))
return A + B + bd
x = 234523546643636
y = 325352354534656
x = Karatsuba(x,y)
x.karatsuba()
这超过了位置参数错误，但是然后我遇到了一个新问题:
This gets past the positional argument error, but then I have a new problem:
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
<ipython-input-34-a862504dede9> in <module>()
59
60 x = Karatsuba(x,y)
---> 61 x.karatsuba()
<ipython-input-34-a862504dede9> in karatsuba(self)
44 # bd = self.karatsuba(self.b, self.d)
45 ac = Karatsuba(self.a, self.c)
---> 46 ac.karatsuba()
47 bd = Karatsuba(self.b, self.d)
48 bd.karatsuba()
<ipython-input-34-a862504dede9> in karatsuba(self)
44 # bd = self.karatsuba(self.b, self.d)
45 ac = Karatsuba(self.a, self.c)
---> 46 ac.karatsuba()
47 bd = Karatsuba(self.b, self.d)
48 bd.karatsuba()
<ipython-input-34-a862504dede9> in karatsuba(self)
44 # bd = self.karatsuba(self.b, self.d)
45 ac = Karatsuba(self.a, self.c)
---> 46 ac.karatsuba()
47 bd = Karatsuba(self.b, self.d)
48 bd.karatsuba()
<ipython-input-34-a862504dede9> in karatsuba(self)
51 # k = self.karatsuba(self.a + self.b, self.c + self.d)
52
---> 53 A = int(self.zeroPad(str(ac), AZeroPadding, False))
54 B = int(self.zeroPad(str(k - ac - bd), BZeroPadding, False))
55 return A + B + bd
ValueError: invalid literal for int() with base 10: '<__main__.Karatsuba object at 0x108142ba8>00'
这时我被困住了.
推荐答案
在我输入此问题时，我发现自己以不同的方式查看代码，即思考如何最好地清楚地解释我的问题，和考虑ValueError ，我发现了问题.
As I was typing up this question, I found myself looking over my code in a different way, i.e. thinking about how best to explain my problem clearly,and thinking about the ValueError, and I discovered the problem.
我正确地遵循了先前链接的问题中abarnert提供的直觉.问题在于函数的其余部分如何需要递归子例程中的值.从ValueError中可以看到，递归子例程的存储位置被传递了，而不是该子例程生成的值.然后，解决方案很简单:将ac.karatsuba()修改为ac = ac.karatsuba(), etc...并瞧瞧！
I was correct to follow the intuition provided by abarnert in the previously linked question. The problem was in how the rest of the function needed the values from the recursion subroutines; as you can see from the ValueError, the memory location of the recursion subroutine was being passed along instead of the value generated by the subroutine. The solution then was straightforward: Modify ac.karatsuba() to ac = ac.karatsuba(), etc... and voila!
对于那些试图了解如何在python类中实现递归的人来说，我认为这个(以及之前链接的问题)是一个很好的教程.
我希望你同意并给我好评！
这是工人阶级的代码:
class Karatsuba(object):
def __init__(self, x, y):
self.x = x
self.y = y
def zeroPad(self, numberString, zeros, left = True):
"""Return the string with zeros added to the left or right."""
for i in range(zeros):
if left:
numberString = '0' + numberString
else:
numberString = numberString + '0'
return numberString
def karatsuba(self):
"""Multiply two integers using Karatsuba's algorithm."""
#convert to strings for easy access to digits
self.x = str(self.x)
self.y = str(self.y)
#base case for recursion
if len(self.x) == 1 and len(self.y) == 1:
return int(self.x) * int(self.y)
if len(self.x) < len(self.y):
self.x = self.zeroPad(self.x, len(self.y) - len(self.x))
elif len(self.y) < len(self.x):
self.y = self.zeroPad(self.y, len(self.x) - len(self.y))
n = len(self.x)
j = n//2
#for odd digit integers
if (n % 2) != 0:
j += 1
BZeroPadding = n - j
AZeroPadding = BZeroPadding * 2
self.a = int(self.x[:j])
self.b = int(self.x[j:])
self.c = int(self.y[:j])
self.d = int(self.y[j:])
#recursively calculate
# ac = self.karatsuba(self.a, self.c)
# bd = self.karatsuba(self.b, self.d)
ac = Karatsuba(self.a, self.c)
ac = ac.karatsuba()
bd = Karatsuba(self.b, self.d)
bd = bd.karatsuba()
k = Karatsuba(self.a + self.b, self.c + self.d)
k = k.karatsuba()
# k = self.karatsuba(self.a + self.b, self.c + self.d)
A = int(self.zeroPad(str(ac), AZeroPadding, False))
B = int(self.zeroPad(str(k - ac - bd), BZeroPadding, False))
return A + B + bd
这篇关于在python类中实现karatsuba递归函数，错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！