Escreva uma função recursiva que permita fazer a multiplicação à russa de 2 entradas. A Multiplicação à russa consiste em:
(a) Escrever os números A e B , que se deseja multiplicar na parte superior das colunas.
(b) Dividir A por 2, sucessivamente, ignorando o resto até chegar à unidade, escrever os resultados da coluna A .
© Multiplicar B por 2 tantas vezes quantas se haja dividido A por 2, escrever os resultados sucessivos na coluna B.
(d) Somar todos os números da coluna B que estejam ao lado de um número ímpar da coluna A .
Exemplo: 27 * 82
|l|c|c| hline $A$ & $B$ & Parcelas hline 27 & 82 & 82 hline 13 & 164 & 164 hline 6 & 328 & - hline 3 & 656 & 656 hline 1 & 1312 & 1312 hline =2214 Parcelas
27 82 82
13 164 164
6 328 -
3 656 656
1 1312 1312
Soma

Passo 1

A ideia é implementar a multiplicação à russa usando recursão, onde dividimos A por 2 e dobramos B até reduzirmos A a 0 ou 1 e somamos os valores de B correspondentes aos passos em que A é ímpar. Para isso vamos usar conceitos de recursão (caso base e passo recursivo) e teste de paridade de A.

Passo 2

Precisamos de um caso base para parar a recursão: se A for 0, o produto é 0; se A for 1, o produto é B. Isso cobre todas as chamadas recursivas até A ficar reduzido a esses valores.

Passo 3

No passo recursivo, testamos se A é par ou ímpar. Se A for par, o termo atual de B não entra na soma, então retornamos simplesmente a chamada recursiva com A dividido por 2 e B dobrado: rec(A//2, B2).
Se A for ímpar (e maior que 1), incluímos o valor atual de B na soma. Logo, retornamos B + rec(A//2, B
2). Essa estrutura faz exatamente as colunas da multiplicação à russa: coluna A vai a A//2 e coluna B vai a B*2, acumulando B quando A é ímpar.

Passo 4

Revisando:
• Caso base: A0 → 0, A1 → B.
• Caso A par: return rec(A//2, B2).
• Caso A ímpar: return B + rec(A//2, B
2).

Passo 5

Vamos então escrever a função em Python seguindo essa lógica e testar com o exemplo 27 * 82.

Resposta

def russian_mult(a, b):
if a == 0:
return 0
if a == 1:
return b
if a % 2 == 0:
return russian_mult(a//2, b2)
else:
return b + russian_mult(a//2, b
2)

Exemplo de uso:

print(russian_mult(27, 82)) # saída 2214

Exercícios relacionados