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

Algoritmo para a multiplicação de números inteiros otimizado através da decomposição do problema

0 votos
20 visitas
perguntada Out 5 em Ciência da Computação por Matheus Cintrão (16 pontos)  

No exercício 4.5 do capítulo 4 do livro "Introduction to Recursive Programing" de Manuel Rubio-Sánchez, o autor propõem a criação de uma função recursiva para a multiplicação de números inteiros usando o algorítimo lento apresentado no capítulo 4.1.2 ("Slow addition"), mas aplicando uma estratégia de decomposição do problema. A decomposição consiste em estimas apenas metade do problema e ao final apenas duplicar o resultado.

Ex: eu tenho o problema de multiplicar 6 por 8. Em vez de realizar a soma 8 + 8 + 8 +... +8, ou seja, 6 operações de soma, eu posso estimar \(r = 8 + 8 + 8\) , \(resultado = r + r\). Aqui eu tenho apenas 4 operações de adição, em vez de 6. Esta operação irá reduzir o número de operações de \(n\) para \( (n/2) +1\).

A lógica muda pouco para o caso dos números impares.

Ex: \( 7 \cdot 8 = 8 + 8 + ... + 8\), teríamos 7 somas. Podemos, no entando fazer \( r = 8 + 8 + 8\), \( resultado = (r + r) + 8\), ou seja 5 operações de soma. Aqui teremos a redução para \( (n//2) + 2\), onde "\\" é a divisão sem o resto.

Importante notar que o exercício admite que as outras operações estão funcionando normalmente (soma, divisão, etc), pois o objetivo é trabalhar um método de implementação de funções recursivas.

Segue o código criado:

def slow_product(a, b):

#criando condições de parada do algoritmo
    if a == 0 or b == 0:
        return 0
    elif a == 1:
        return b
    elif b == 1:
        return a
    elif a == -1:
        return -b
    elif b == -1:
        return -a
#Aumentando eficiência usando o menor valor    
    elif a <= b: 
#Vou usar uma variável r como intermediária para que o 
#slow_product não seja calculado 2 vezes        
        if a % 2 ==0:            
            r = slow_product(a//2, b) 
            return r + r
        else:
            r = slow_product(a//2, b)
            return  r + r + b
    else:
        if b % 2 ==0:
            r = slow_product(a, b//2) 
            return r + r
        else:
            r = slow_product(a, b//2)
            return  r + r + a


if __name__ == '__main__':

    # testando a função    
    c = slow_product(-4, 3)
    print(c)
Compartilhe

1 Resposta

0 votos
respondida Out 7 por Thiago Trafane (21 pontos)  

Matheus, parabéns pela solução! Acredito que esteja tudo correto. Por isso, tenho apenas alguns comentários pontuais:

1) Talvez seja interessante colocar o enunciado completo da questão, assim como a referência, no campo "Mais informações sobre a pergunta".

2) Quando você escreve logo no primeiro parágrafo "A decomposição consiste em estimas [...]", acredito que você queria dizer "A decomposição consiste em estimar [...]".

3) Quando você escreve "[...] onde '\\' é a divisão sem o resto", penso que o correto seria "[...] onde '//' é a divisão sem o resto".

4) No seu programa, ao invés de usar "elif a <= b", seria melhor usar "elif abs(a) <= abs(b)". Afinal, se o objetivo é aumentar a eficiência do programa, diminuindo o número de recursões, o que importa é o valor absoluto dos inputs.

5) Na parte final do programa, você repete duas vezes basicamente o mesmo código, para tratar os casos \( a \leq b \) e \( a \gt b \). Você poderia tentar simplificar esse trecho do código. Por exemplo, você poderia criar duas variáveis auxiliares e atribuir sempre o menor valor dos inputs para uma delas e o maior valor para a outra. Desse modo, você poderia escrever essa parte final do código apenas uma vez. Uma forma de implementar essa sugestão seria você substituir a parte final do código da sua função (a partir de “elif a <= b”, incluindo tal trecho) por:

else:
    if abs(a) <= abs(b): 
        c_min = a
        c_max = b
    else:
        c_min = b
        c_max = a

    if c_min % 2 ==0:            
        r = slow_product(c_min//2, c_max) 
        return r + r
    else:
        r = slow_product(c_min//2, c_max)
        return  r + r + c_max
...