Question

Ранее я опубликовал вопрос на эту тему, и на него был дан довольно хороший ответ. Реализация функции сортировки слиянием в классе Python, ошибки И все же есть кое-что, что ускользает от меня в отношении рекурсии в классе.В приведенной выше проблеме, если я добавлю префикс self. в подпрограмму рекурсии, я получу точно такую же ошибку, которая выдается ниже в выходных данных класса (третий блок кода в этом посте).Я понимаю, почему это происходит;object.karatsuba() принимает только self в качестве входных данных, и, тем не менее, метод в кодированном виде запрашивает 2, а следовательно, ошибку.

Пожалуйста, просмотрите приведенный ниже код и затем посмотрите мою интуицию относительнорешение после 3-го блока кода.

Например: у меня есть рабочая реализация умножения карацубы, которая не хочет работать в классе.Стандартное умножение в классе прекрасно работает в классе, но ...

Это рабочий код вне класса:

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:

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

Неправильная версия класса генерирует следующий вывод:

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

Моя первоначальная интуиция заключалась в том, чтобы следовать решению, изложенному в связанном вопросе верхнего абзаца, как таковое:

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()

Это преодолевает ошибку позиционного аргумента, но у меня возникает новая проблема:

---------------------------------------------------------------------------
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'

На данный момент я застрял.

reka18 · Answer 1 · 09 июня 2018

Когда я набирал этот вопрос, я обнаружил, что перебираю свой код по-другому, то есть думаю о том, как лучше всего объяснить мою проблему, и думаю о ValueError , и я обнаружилпроблема.

Я был прав, следуя интуиции Абарнерта в ранее связанном вопросе.Проблема заключалась в том, как остальная часть функции нуждалась в значениях из подпрограмм рекурсии;как вы можете видеть из ValueError, место в памяти подпрограммы рекурсии передавалось вместо значения, сгенерированного подпрограммой.Решение тогда было простым: измените ac.karatsuba() на ac = ac.karatsuba(), etc... и вуаля!

Я думаю, что это (и ранее связанная проблема) служит хорошим руководством для тех, кто пытается понять, как реализовать рекурсиюна уроках питона.

Надеюсь, вы согласитесь и дадите мне хорошие голоса!

Вот код рабочего класса:

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, ошибки

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

1 Ответ

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Реализация рекурсивной функции Карацубы в классе Python, ошибки

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

1 Ответ

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Похожие темы