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

3 comentários:

Daniel disse...

Tá voando muito hein rodrigo... espero nunca precisar fazer algo do tipo :)

Rafael disse...

Muito interessante essa estratégia de memorizar os fatoriais.

Nunca tinha pensado nisso, também nunca parei p pensar ;)

Anibal Sólon disse...

É, recursividade é útil também pra calcular determinantes e pra fazer até uma tree de arquivos/pastas :) Acho mui útil...