Python нужна помощь с методом Карацубы

2 октября, 14:38 Учеба 3215 0

Здравствуйте есть вот такие числа X = 21625695688898558125310188636840316594920403182768
Y = 13306827740879180856696800391510469038934180115260
Теперь для этих двух значений, что у меня прописаны вначале надо количество сколько раз встречалось ad+bc=105, ad+bc=72,ad+bc=12. Мне считает, 1 и третье правильно, а 2 нет . Правильные ответы при ad+bc=105 - 1 или 3 или 4, ad+bc=72 - 16 или 7, ad+bc=12 - 17 , 15 , 5. Кто может помочь, можете написать правильно строчку кода, где ошибка
Вот код

def karat(x1, y1):
x1 = str(x1)
y1 = str(y1)

x2 = len(x1)
y2 = len(y1)

if (int(x2) == 1 and int(y2) == 1):
return int(x1) * int(y1)
else:
half1 = int(math.ceil(x2 / 2.0))
half2 = int(math.ceil(y2 / 2.0))

if (half1 < half2):
half = half1
else:
half = half2

h1 = x2 — half
h2 = y2 — half

if h1 == 0:
a = 0
else:
a = int(x1[0:h1])

if h2 == 0:
c = 0
else:
c = int(y1[0:h2])

b = int(x1[h1:x2])
d = int(y1[h2:y2])

ac = karat(a, c)
bd = karat(b, d)
adbc = karat(a + b, c + d) — ac — bd

if adbc in dictionary:
value = dictionary[adbc]
value = value + 1
dictionary.update({adbc: value})
else:
dictionary[adbc] = 1

results = ac * math.pow(10, x2) + adbc * math.pow(10, x2 / 2) + bd

return int(results)



result = karat(168528749932832829781465563927858366791935584939145345 6921116729, 711419284857775458796974462655857153672898316795455299989534 8492)
print(result)
print(’’)
for key in sorted(dictionary.keys()):
print(key, " :: ", dictionary[key])
input()

0 комментариев
Сортировка:
Добавить комментарий

IT Новости

Смотреть все