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
.
(d) Somar todos os números da coluna B que estejam ao lado de um número ímpar da coluna A .
Exemplo: 27 * 82
Parcelas
27
82
82
13
164
164
6
328
-
3
656
656
1
1312
1312
Soma
(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
(d) Somar todos os números da coluna B que estejam ao lado de um número ímpar da coluna A .
|
|
Parcelas |
27 | 82 | 82 |
13 | 164 | 164 |
6 | 328 | - |
3 | 656 | 656 |
1 | 1312 | 1312 |
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, B2). 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.
Se A for ímpar (e maior que 1), incluímos o valor atual de B na soma. Logo, retornamos B + rec(A//2, B2). 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, B2).
• Caso base: A0 → 0, A1 → B.
• Caso A par: return rec(A//2, B2).
• Caso A ímpar: return B + rec(A//2, B2).
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, b2)
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, b2)