Может кто-нибудь помочь с этой конкретной проблемой?Я не совсем уверен, как это сделать.Я добавляю свое решение «разделяй и властвуй» ниже и свой псевдокод.«a» и «b» - это просто мои целые числа, которые можно предположить, что они имеют размер n и четный.Таким образом, мы разбиваем их на две части как «R» с правой стороны и «L» с левой стороны.Мой профессор попросил доказать это по индукции, и мне трудно.Базовый случай очень прост, когда длина равна 1, возвращаемое 1. Как мне сформулировать мою гипотезу об индукции, которая выглядит примерно так: предположим, что P (k) верна, а затем покажем, что P (k + 1) верна.
Разделить и решить решение
a = aL aR = aL * 10 ^ (n / 2) + aR
b = bL bR = bL * 10 ^ (n / 2) +bR
a * b = (aL * 10 ^ (n / 2) + aR) * (bL * 10 ^ (n / 2) + bR) = (aLbL) * 10 ^ n + (aLbR +aRbL) * 10 ^ (н / 2) + aRbR
Однако aLbR + aRbL = (aL + aR) (bL + bR) - aLbL - aRbR
mult(a,b)
if len(a), len(b) = 1 return a * b
split a,b into aL bR
c1 = mult(aL, bL)
c2 = mult(aL + aR, bL + bR)
c3 = mult(aR, bR)
return c1*10^n + (c2 - c1 - c3) * 10^(n/2) + c3