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

Como escrever uma função recursiva que calcule o fatorial usando a estratégia de divisão e conquista como no algoritmo "merge sort"?

+1 voto
130 visitas

1 Resposta

0 votos
respondida Mai 13 por Carlos Eduardo Véras (11 pontos)  
editado Mai 23 por Carlos Eduardo Véras

O problema pede que seja definida uma função Fatorial(n,m) que calcule n x (n - 1) x ...m e chame essa função recursivamente para calcular o fatorial. Para fins de comparação, foram implementadas na linguagem Python as versões força bruta (iterativa e recursiva) do problema e a versão divisão e conquista. O código está comentado com as explicações pertinentes.

biblioteca para realizar a analise do tempo de execução do algoritmo

import time

cálculo do fatorial por meio da força-bruta

def fatorial_bf(m,n):
"""
Método para cálculo do fatorial de um número utilizando a estratégia de
força bruta. O método recebe como parâmetros os valores m e n, que são,
respectivamente, o intervalo inferior e o intervalo superior para cáculo
do fatorial. Como o método é recursivo, existe o caso base, que é o fatorial
de m e o fatorial de 1. A recursividade está implementada na chamada
sucessiva do método para os casos em que n > m.
"""

if n == m:
    if m > 0:
        return m
    else:
        return 1

elif n > m:
    return n*fatorial_bf(m,n-1)

cálculo do fatorial por meio da divisão e conquista

def fatorial_dc(m,n):
"""
Método para cálculo do fatorial entre os números m e n. No caso do cálculo
por meio da estratégia de divisão e conquista, tomam-se intervalos sucessi-
vamente menores entre os extremos inferior (m) e superior (n). Em outras
palavras "p" corresponde à metade do intervalo entre "m" e "n" e, por
conseguinte, o fatorial é calculado recussivamente em dois intervalos
distintos adjacentes: entre "m" e "m+p"; e entre "m+p+1" e "n".
Posteriormente, calcula-se o produto entre os fatoriais dos intervalos
anteriores.
"""

# incializa a variável "z" com o valor inferior do intervalo
# de cálculo

z = m

# critério de parada para o cálculo do fatorial de um número "m"="n"    
if (m != n):

    # tamanho do intervalo para a divisão
    p = (n-m)//2 

    # fatorial calculado recursivamente para a primeira metade do 
    # intervalo
    x = fatorial_dc(m, m + p)
    # fatorial calculado recursivamente para a segunda metade do 
    # intervalo
    y = fatorial_dc(m + p + 1, n)                   
    # calcula o fatorial dos dois intervalos
    z = x*y  

return z

executa os métodos para cálculo do (n,m)!

if name == 'main':

"""
Resultado da execução do código:

Fatorial força-bruta: 604800
--- 0.0 segundos ---
Fatorial divisão e conquista: 604800
--- 0.0 segundos ---

"""


# limite inferior do intervalo
m = 4
# limite superior do intervalo
n = 10

# cálculo por meio da estratégia de força-bruta
start_time = time.time()
print("Fatorial força-bruta:", (fatorial_bf(m,n)))
print("--- %s segundos ---" % (time.time() - start_time))      

# cálculo por meio da estratégia de divisão e conquista
start_time = time.time()
print("Fatorial divisão e conquista:", (fatorial_dc(m,n)))
print("--- %s segundos ---" % (time.time() - start_time))  

Interessante notar que a avaliação empírica de eficiência do algoritmo indica que o método de divisão e conquista apresenta mesmo tempo de execução do algoritmo força-bruta. Em termos de complexidade computacional tem-se:

Através do "Teorema Mestre":

A imagem será apresentada aqui.

  • Fatorial com recursividade:

T(n) = T(n) + 1

a = 1; b = 1; d = 0, logo: a > b^d => T(n) = Theta(n^logb(a)) = Theta(n)

  • Fatorial com divisão e conquista:

T(n) = 2T(n/2) + 1

a = 2; b = 2; d = 0, logo: a > b^d => T(n) = Theta(n^logb(a)) = Theta(n)

Portanto, ambos os algoritmos possuem a mesma complexidade computacional e, por conseguinte, a mesma eficiência em termos de tempo de execução.

...