terça-feira, 2 de dezembro de 2014

[Programação em C] - Triângulo de Pascal com Programação Dinâmica

Olá pessoal, nesse post nós iremos falar sobre o triângulo de pascal e como resolver utilizando programação dinâmica.

O triângulo de pascal é um triângulo numérico infinito formado por números binomiais.

O triângulo de pascal tem uma propriedade bem interessante: cada número do triângulo é igual à soma do número imediatamente acima e do antecessor do número de cima.

Veja a imagem acima, o 10 é a soma do 6 (número acima) + o 4 (antecessor do número de cima que é o 6).

Nosso objetivo é fazer um programa que, dado um "n" e um "k", retorne o resultado desse número binomial.

Com n=3 e k=1 temos que o resultado é (3!)/((3 - 1)! * 1!) = 3.

Mas vamos utilizar uma técnica chamada Programação Dinâmica para calcular isso de forma mais rápida.

Programação dinâmica nada mais é que uma técnica para resolver problemas computacionais em problemas nos quais a solução ótima pode ser computada a partir da solução ótima previamente calculada e memorizada com o objetivo de evitar recalcular.

Fibonacci é um clássico problema que pode ser resolvido utilizando programação dinâmica.

Veja o código abaixo que resolve o triângulo de pascal utilizando programação dinâmica:


Iremos construir uma matriz 51x51 (N = 51). Na linha 13 temos um "for" que começa a construir essa tabela que é o nosso triângulo. Perceba que atribui 1 para tab[i][0] e tab[i][i]. Por que isso?

Olhe para a imagem anterior, percebemos que o triângulo é preenchido com o valor 1 na primeira coluna, daí tab[i][0] receber 1. Percebemos também que a última diagonal é preenchida com 1, por isso tab[i][i] recebe 1.

Ok, já temos os elementos iniciais para começarmos a calcular os outros valores do nosso triângulo.

A partir da linha 19 começa a percorrer a matriz. Olhando para o "for" mais interno, percebemos que se o "i" for menor ou igual a "j", é dado um break para sair do loop mais interno, isso acontece porque NÃO precisa preencher a matriz toda, é um triângulo. Olhe novamente a imagem anterior, "n" é a linha e "k" a coluna. Só calcula enquanto "n" for menor que "k", porque quando eles são iguais é igual a 1 (fizemos isso na inicialização).

Quando "i' é maior que "j" fazemos o cálculo. O cálculo tem como resultado a soma do número acima dele com o antecessor do número de cima. Veja:

tab[i - 1][j] acessa o elemento de cima

tab[i - 1][j - 1] acessa o antecessor do elemento de cima.

Fácil não é mesmo? Na linha 30 inicializamos as variáveis "A" e "B" com 50 e 45 respectivamente. Agora basta consultar a tabela, pois o "A" é a linha e "B" a coluna, tab[A][B] possui o resultado que procuramos.

Quaisquer dúvidas, sugestões ou críticas deixem nos comentários, até a próxima.


Nenhum comentário: