Каратсубинский рекурсивный код работает неправильно - PullRequest
Новая
       29

Каратсубинский рекурсивный код работает неправильно

0 голосов
/ 27 июня 2019

Я хочу реализовать алгоритм умножения Карацубы в python. Но он работает не полностью.

Код не работает для значений x или y, превышающих 999. Для входов ниже 1000 программа показывает правильный результат. Она также показывает правильные результаты в базовых случаях. 

#Karatsuba method of multiplication.

f = int(input()) #Inputs
e = int(input())

def prod(x,y):
    r = str(x)
    t = str(y)
    lx = len(r)  #Calculation of Lengths
    ly = len(t)

    #Base Case

    if(lx == 1 or ly == 1):
        return x*y

    #Other Case

    else:
        o = lx//2
        p = ly//2

        a = x//(10*o)   #Calculation of a,b,c and d.
        b = x-(a*10*o)  #The Calculation is done by
        c = y//(10*p)   #calculating the length of x and y
        d = y-(c*10*p)  #and then dividing it by half.
                        #Then we just remove the half of the digits of the no.

        return (10**o)*(10**p)*prod(a,c)+(10**o)*prod(a,d)+(10**p)*prod(b,c)+prod(b,d)

print(prod(f,e))

Я думаю, что есть некоторые ошибки в расчете a, b, c и d.

1 Ответ

0 голосов
/ 27 июня 2019 
a = x//(10**o)
b = x-(a*10**o)
c = y//(10**p)
d = y-(c*10**p)

Вы имели в виду 10 в степени, но написали 10, умноженное на.

Вы должны тренироваться, чтобы найти такие ошибки самостоятельно. Есть несколько способов сделать это:

  • Выполните алгоритм вручную на бумаге для конкретных входных данных, затем пошагово просмотрите код и посмотрите, соответствует ли он
  • Сократите код до подразделов и посмотрите, соответствует ли их ожидаемое значение полученному значению. В вашем случае проверяйте для каждого вызова prod(), каким будет ожидаемый результат и что он произвел, чтобы найти минимальные входные значения, которые дают ошибочные результаты.
  • Пройдите по коду с помощью отладчика. Перед каждой строкой подумайте, каким должен быть результат, а затем посмотрите, дает ли строка этот результат.
...