terça-feira, 12 de fevereiro de 2008

Exemplo de Programação dinâmica

Um dos blogs que assino o RSS é o VidaGeek. Hoje saiu um post muito interessante sobre Programação Dinâmica. Eu como desocupado além de achar interessante fiquei imaginando um exemplo simples que pudesse fazer em Java ou C#.
Como programação dinãmica é "aplicável à problemas no qual a solução ótima pode ser computada a partir da solução ótima previamente calculada e memorizada" eu imaginei que poderia ser usado em uma classe que calculasse fatorial, pois n! = n * (n - 1)! de quebra ainda estaria exercitando recursão em java, coisa que não lembro se já precisei fazer.

Segue o código abaixo:


Essa implementação seria util para um programa que calculasse o fatorial de vários números. A diferença pro algoritmo padrão de fatorial, é que eu armazeno os resultados pra cada iteração em um HashMap. Quem não entendeu muito bem, recomendo que leia os dois links que eu coloquei acima.

Referências:
http://vidageek.net/2008/02/11/programacao-dinamica/
http://pt.wikipedia.org/wiki/Recursividade