#python #algorithm #recursion #karatsuba
#python #алгоритм #рекурсия #карацуба
Вопрос:
Новичок здесь. Я провел большую часть дня, работая над алгоритмом Карацубы только потому, что думал, что это будет плодотворно. Я видел похожие вопросы здесь, но они на других языках и кажутся странно сложными. Ниже приведен мой код. В ту минуту, когда он попадает на рекурсивный вызов ac, он просто продолжает повторяться. Как будто он никогда не попадает в базовый вариант. Если кто-нибудь может быть настолько любезен, чтобы предложить некоторое представление о том, где что-то идет не так, это было бы весьма признателен. Для этого кода вы должны предположить, что я умножаю 2, основание-10, четырехзначные числа.
def karatsuba(x, y):
if len(str(x)) == 1 or len(str(y)) == 1:
return (x * y)
else:
n = (max(len(str(x)), len(str(y))))
a = x / 10**(n / 2)
b = x % 10**(n / 2)
c = y / 10**(n / 2)
d = y % 10**(n / 2)
ac = karatsuba(a, c)
ad = karatsuba(a, d)
bc = karatsuba(b, c)
bd = karatsuba(b, d)
product = (10**n*(ac) 10**(n/2)*(ad bc) bd)
return product
print (karatsuba(1234, 5678))
Комментарии:
1. числа
lenникогда не будет<1— всегда есть хотя бы 1 цифра, даже если0вы предполагаете, что вы имели в виду==1. Если это так, есть ли причина не просто проверить, являются ли они<10вместо преобразования в astr?2. @AChampion — Спасибо за ответ. Очень хороший улов! Я пробовал оба метода. Подход == 1 оставил меня с той же бесконечной рекурсией. Подход <10 (без приведения типов к строке) оставил меня с другой бесконечной рекурсией в строке «bc». Сюжет сгущается. Еще раз спасибо!
3. Является ли проблема неопределенной? Т.Е. Вы находите разные результаты каждый раз, когда запускаете его?
4. @sakurashinken Я хотел бы получить какой-то результат. Я использую IDLE для python, и я просто получаю бесконечный поток ошибок, указывающих на рекурсивную строку, прямо сейчас это ac. Когда я вставлял операторы печати, я видел много десятичных значений для a amp; c, которые были неожиданными.
5. Предполагая, что вы используете python3. Используйте целочисленное деление
//, иначе вы введете числа с плавающей запятой и вызовете проблемы. Протестировано с целочисленным делением, и оно работает нормально, хотя вы можете исключить один из рекурсивных вызовов, и гораздо быстрее будет работать в двоичном или десятичном формате.
Ответ №1:
Простое исправление вашего кода с помощью целочисленных делений позволило ему работать правильно, но вот немного другая версия, использующая 3 рекурсивных вызова (в базе 10):
def karatsuba(x, y):
if x < 10 or y < 10:
return x * y
n = max(len(str(x)), len(str(y))) // 2
p = 10**n
a, b = divmod(x, p)
c, d = divmod(y, p)
ac = karatsuba(a, c)
bd = karatsuba(b, d)
abcd = karatsuba(a b, c d) - ac - bd
return (ac*p abcd)*p bd
Но он намного быстрее работает в двоичном формате и использует битовое переключение:
def karatsuba(x, y):
if x < 16 or y < 16:
return x * y
n = max(x.bit_length(), y.bit_length()) // 2
mask = (1 << n) - 1
a, b = x >> n, x amp; mask
c, d = y >> n, y amp; mask
ac = karatsuba(a, c)
bd = karatsuba(b, d)
abcd = karatsuba(a b, c d) - ac - bd
return (((ac << n) abcd) << n) bd
Комментарии:
1. (
return (ac * p abcd) * p bdможет быть более читабельным и ближе к «варианту с битовым поворотом».)2. Очень впечатляет! Спасибо за помощь, ребята. Здесь есть о чем подумать!
3. @greybeard очень верно — намного аккуратнее
Ответ №2:
Вы хотите целочисленное деление? В этом случае вы должны использовать:
a = x // 10 ** (n / 2)
и
c = y // 10 ** (n / 2)
В противном случае ваша программа будет передавать десятичные дроби в вашу функцию, которая, как я полагаю, не предназначена.
Я тоже новичок, не стесняйтесь меня поправлять.
Комментарии:
1. Большое спасибо за ответ! Это имело смысл, поэтому я попробовал. К сожалению, проблема бесконечной рекурсии переместилась с вычисления ac на рекурсивный вызов bd. Еще раз спасибо!
2. @RyanD. Вам
n//2тоже нужно исправить — при условии, что вы используете Python3. Который у вас также есть в окончательномproductвычислении.