Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Implemente uma função recursiva que compute o produto de dois números inteiros não-negativos sem utilizar o operador de multiplicação

0 votos
19 visitas
perguntada Out 19 em Programação Computacional por Renan Abrantes (16 pontos)  

O exercício é proveniente do livro Introduction to Recursive Programming, de Manul Rubio-Sánchez.

O autor pede para criar uma função recursiva para calcular o produto de dois números inteiros não-negativos sem utilizar o operador de multiplicação. Adicionalmente pede para ilustrar o processo pensado para a solução do problema.

Segue transcrição do exercício:
"4.4 Implement recursive functions that compute a “slow” product of two nonnegative integersm and n. The algorithms are allowed to add and subtract numbers, but they may not use the multiplication (*) operator. Use decompositions that decrease one or both of the inputs by a single unit. In addition, illustrate the recursive design thought process through diagrams."

Compartilhe

1 Resposta

0 votos
respondida Out 19 por Renan Abrantes (16 pontos)  
editado Out 20 por Renan Abrantes

Como você aprendeu a multiplicar?

Antes de eu aprender (ou decorar) a tabuada, minha professora de primário ensinou que a multiplicação era a soma de um número \(m\) repetidamente, por \(n\) vezes. No modelo pedagógico, pegávamos uma fileira de \(m\) bloquinhos e contávamos esse valor. Posteriormente, adicionávamos uma fileira com o mesmo número de bloquinhos acima da primeira fileira, contando novamente o número total de bloquinhos. Repetíamos esse processo sucessivamente, até chegar ao valor da multiplicação das \(n\) fileiras compostas por \(m\) bloquinhos.

Vamos ilustrar o modelo pedagógico no Python, com \(m=10\) e \(n=4\):

#mostrar graficamente o processo pedagógico primário de multiplicação
import matplotlib.pyplot as plt
from matplotlib.patches import Rectangle

m = 10
n = 4
for i in range(1,n+1): #mostra o número de bloquinhos sucessivamente, com número de fileiras começando em 1 e indo até n
    retangulo = Rectangle((0,0), width=m, height=i)
    plt.figure()
    plt.xlim(0,m)
    plt.ylim(0,i)
    plt.grid(b=True)
    plt.xticks(range(0,m+1))
    plt.yticks(range(0,i+1))
    eixo = plt.gca()
    eixo.add_patch(retangulo)
    plt.show()

Segue o resultado:

A imagem será apresentada aqui.

Agora vamos implementar o modelo pedagógico em uma função recursiva:

def multiply(m,n):
    if (n == 1):
        result =  m;
    else:
        result =  m + multiply(m, n-1);
    return(result)

Por último, vamos apenas checar o resultado de algumas multiplicações:

print(multiply(10,4))
print(multiply(30,2))
print(multiply(170,871))

Os resultados retornados foram \(40\), \(60\) e \(148070\), como era de se esperar.

Ao passo que o humano não executa processos de recursão rapidamente, o computador os faz com muita facilidade. Embora o modelo pedagógico sirva para compreender o que é a multiplicação, é impossível um humano utilizá-lo para a multiplicação de grandes números. Imagine termos que calcular "na mão" com o método dos bloquinhos a multiplicação de 170 por 871? Pois o computador faz isso em um segundo.

comentou Nov 6 por CICERO FILHO (26 pontos)  
Foi explicado de forma bem simples e detalhado o exercício, a intuição e a resolução. Complemento que o cálculo do produto de dois números inteiros não-negativos usando recursão em python é bem intuitivo.

Método:

1) Se x for menor que y, troque o valor das duas variáveis

2) Encontre recursivamente y vezes a soma de x

3) Se algum deles se tornar zero, retorne 0

Outro exemplo:


    # Para encontrar o produto de dois números usando função recursiva
    # Função recursiva para calcular a multiplicação de dois números
    
    def product( x , y ):
        # se x é menor que y então troca os números
        if x < y:
            return product(y, x)
         
        # calcular iterativamente a soma y de x equipes
        elif y != 0:
            return (x + product(x, y - 1))
         
        # se qualquer um dos dois números for zero, retorne zero
        else:
            return 0
     
    x = 5
    y = 2
    print( product(x, y))
     
    Output :
    10
comentou Nov 6 por Renan Abrantes (16 pontos)  
Excelente complementação, Cícero. Obrigado!
...