A linguagem escolhida foi Python 3.6..
Seguem abaixo as implementações do cálculo do fatorial nas versões força bruta - i) iterativa ii) recursiva - e iii) divisão e conquista, respectivamente:
i) Iterativa:
def factorial_it(n):
f=1
for i in range(1,n+1):
f=f*i
return f
ii) Recursiva:
def factorial_rec(n):
if(n>1):
return n * factorial_rec(n-1)
else:
return 1
iii) Agora, a partir da estratégia divisão e conquista:
Primeiro, importa-se o pacote math que adiante será utilizado para calcular um arrendondamento para baixo (floor). Logo depois, determina-se uma função que será responsável pelo cálculo do fatorial:
import math
def calc_fact(a,b):
return a * b
Adiante, define-se uma função factorial(m,n), onde factorial(m,n)=n!/(m-1)!. Depois divide-se o problema em duas partes - elas são representadas pelas variáveis a e b. A variável a é definida como (m+p)!/(m-1)!, já a variável b é igual a n!/(m+p!), onde adotamos que p é a divisão inteira de (n-1) por 2 (ou seja, o ponto médio da nossa sequência, já que adotaremos nesse cálculo m=1). Em seguinte o problema é "fundido" (assim como no algoritmo Merge-Sort) em uma única variável c:
def factorial(m,n):
c=m
if(m!=n):
p=math.floor((n-m)//2)
a=factorial(m,m+p)
b=factorial(m+p+1,n)
c=calc_fact(a,b)
return c
Agora, por exemplo, se o objetivo fosse calcular o fatorial de 4!, teríamos que (n=4, m=1) e factorial(1, 4) = factorial(1, 2) x factorial(2, 4), ou seja, dividiríamos o problema nos seguintes cálculos: 2!/0! e 4!/2!. O passo final seria fundir os sub-problemas chegando no resultado 2!/0! x 4!/2! = 4! (o equivalente a: (1 x 2) x (1 x 2 x 3 x 4)/(1 x 2) = 2 x 24/2 = 24.
Basta, então, imprimir a função factorial(1,n) - neste exemplo em particular factorial(1,4):
print(factorial(1,4))
24
Utilizando o Teorema Mestre calcula-se que a complexidade deste terceiro algoritmo é n log n. Nota-se que a assintoticamente este algoritmo é mais eficiente do que os dois primeiros, interação e recursão (os quais possuem complexidade equivalente a n). Observe que há uma economia de computação nesta estratégia, pois quanto maior for o cálculo do fatorial, mais multiplicações serão necessárias (e maior serão esses números). Então, dividindo o cálculo do nosso fatorial ao meio simplificamos de certa forma todas essas contas.