Cursos de Informática Grátis www.megainforcursos.com

10 de agosto de 2012

Recurs�o (Aula 10)

Recurs�o
(Aula 10)
A recurs�o � bastante usada na matem�tica para definir fun��es, usando elas mesmas nas suas pr�prias defini��es. Por exemplo o calculo de um fatorial, pode ser representada em forma de recurs�o da seguinte forma:
n!=0 se n = 0
n!=n*(n-1)! se n > 0
Usando a defini��o acima, o fatorial de um n�mero podemos calcular multiplicando o n�mero pelo fatorial do n�mero inteiro anterior, e por sua vez o fatorial deste n�mero podemos calcular multiplicando ele pelo fatorial de seu antecessor, e assim sucessivamente at� chegar a 0, onde o fatorial � igual a 1. Nesse momento acaba a recurs�o.
Existem muitas fun��es ou procedimentos que podemos definir em forma simples e compacta usando a recurs�o. Vejamos como podemos usar a recurs�o em Pascal para calcular o fatorial de um n�mero.

Vamos definir a fun��o fatorial(n) que recebe como par�metro um n�mero inteiro n e retorna o fatorial do n�mero.
Fun��o
function fatorial(n:integer):integer;
begin
if(n=0) then fatorial:=1
else fatorial:=n*fatorial(n-1);
end;
Para testar a fun��o vamos escrever o programa que chama a fun��o fatorial
Fun��o
Program TestaFatorial;
Var n, f: integer;

function fatorial(n:integer):integer;
begin
if(n=0) then fatorial:=1
else fatorial:=n*fatorial(n-1);
end;
Begin
writeln('entre com um n�mero inteiro');
Readln(n);
f:=fatorial(n);
writeln('o fatorial de ',n,' eh ',f);
End.
Vejamos a aplica��o da recurs�o num outro problema mais interessante.
Problema: Torre de Hanoi
As Torres de Han�i s�o um quebra-cabeca muito antigo e conhecido. Ele consiste de um conjunto de N discos de tamanhos diferentes e tr�s pinos verticais, nos quais os discos podem ser encaixados.




Cada pino pode conter uma pilha com qualquer n�mero de discos, desde que cada disco n�o seja colocado acima de outro disco de menor tamanho. A configurac�o inicial consiste de todos os discos no pino 1. O objetivo � mover todos os discos para um dos outros discos, sempre obedecendo � restric�o de n�o colocar um disco sobre outro menor.
Tarefa
Escrever um programa que determine quantos movimentos de trocar um disco de um pino para outro ser�o necess�rios para levar todos os disco do pino 1 (origem) para o pino 3 (destino). Como entrada o programa recebe o n�mero de discos.
Solu��o
Este problema vamos resolver analisando varias situa��es da seguinte forma:
Primeiro vamos analisar a situa��o mais simples: o que fazemos se temos apenas um disco?. A resposta � levar o disco do origem ao destino, neste caso o n�mero de movimentos � 1.
Agora vamos analisar a situa��o em que temos 2 discos (N=2) no origem. Neste caso, levamos primeiro o disco mais leve ao pino temporario (pino 2), logo levamos o disco mais pesado ao destino e finalmente levamos o disco menor do temporario ao destino. Se podemos levar os dois disco ao destino, tamb�m poderiamos levar os dois discos ao pino temporario (seguindo a seguinte seq��ncia: disco menor ao destino, disco maior ao temporario, disco menor ao temporario). Agora imagina que temos 3 discos no origem. O que podemos fazer � levar os dois discos menores ao temporario (isso ja sabemos fazer), logo levar o disco mais pesado ao pino destino e finalmente os dois discos menores levar para o pino destino usando o pino origem. Em forma geral se temos, N discos, levamos os N-1 discos menores ao pino temporario, o disco maior levamos ao destino e depois levamos os N-1 discos ao destinos. Portanto o algoritmo seria:
Algoritmo
procedimento Hanoi(N, Orig, Dest, Temp, contador)
se N = 1 ent�o
mover o menor disco do pino Orig para o pino Dest;
acrecentar o contador;
sen�o
Hanoi(N-1, Orig, Temp, Dest, contador);
mover o N-�simo menor disco do pino Orig para o pino Dest;
acrecentar o contador;
Hanoi(N-1, Temp, Dest, Orig, contador);
fim-se
fim
Em cada movemento vamos acrecentar o valor de um contador para determinar o numero de movimentos. Para que o contador possa ser alterado quando retornar a fun��o, valor utilizar a ideia de passagem de parametro por referencia, o que foi aprendido na aula anterior. Vejamos como seria o programa:
Program
Program testahanoi;
Var n,contador:integer;

Procedure Hanoi(n,origem,dest, temp:integer; var contador:integer);
Begin
if(n=1) then begin
contador:=contador+1;
end
else begin
Hanoi(n-1, origem, temp, dest,contador);
contador:=contador+1;
Hanoi(n-1, temp, dest, origem,contador);
end;
End;
Begin
writeln('entre com o numero de discos');
readln(n);
contador:=0;
Hanoi(n,1,2,3,contador);
writeln('o numero de movimentos eh: ',contador);
End.
Como podemos notar a recurs�o pode ser uma ferramenta muito �til para resolver alguns problemas de repeti��o. No entanto, a recurs�o consome mais memoria que uma itera��o normal, por isso devemos evitar usar a recurs�o quando seja poss�vel. Por exemplo, � melhor calcular o fatorial usando um la�o como foi feito na aula 4 que usando a recurs�o como foi mostrado nesta aula.
Exerc�cios
Somas dos numeros
A soma dos primeiros N numeros inteiros pode ser calculado facilmente com um programa utilizando os la��s. Como poderiamos fazer a mesma soma, usando a recurs�o?
Tarefa
Fa�a um fun��o recurs�o que calcula a soma dos primeiros N numeros.
Exemplo de entrada
120

Exemplo de sa�da
7260

Coelhos de Fibonacci
Certo matem�tico italiano com nome de Leonardo de Pisa, conhecido tambem como Fibonacci, propos o seguinte problema: Suponha que acabamos de comprar um casal de coelhos. No final do mes este casal vai ter um casal de coelhinhos (um coelho e uma coelha). Um mes depois, o casal vai ter outro casal de coelhinhos e ao mesmo tempo seus primeiros filhos que agora ja est�o adultos tambem v�o ter um casal de coelhinhos. Assim a cada mes, cada casal de coelhos adultos tem um casal de coelhinos e cada casal de coelhos nacidos no mes anterior viram adultos. A pergunta �, �quantos casais de coelhos vamos ter no final do mes N?.
Este problema pode ser tratado usando a recurs�o. Se consideramos Fn o numero de coelhos do final do mes, este ser� a soma dos casais adultos no mes (n-2) e os casais que virar�o adultos no mes (n-1). Ou seja:
Fn=Fn-1 + Fn-2

como no primeiro mes e anterior o numero de casais era apenas 1 ent�o F0=1 e F1=1. A seq��ncia de n�mero obtidos usando esta recurs�o s�o chamados de n�meros de fibonacci. Vejamos como � a seq��ncia:
F0 = 1
F1 = 1
F2 = 2
F3 = 3
F4 = 5
F5 = 8
.....

Tarefa
Fazer um programa que calcula em forma recursiva o n�mero do fibonacci. como entrada o programa recebe o n�mero do mes N e como saida mostra o numero de fibonacci FN
Exemplo de Entrada
10

Exemplo de Sa�da
89

Turismo do planalto
Planalto � uma cidade planejada e possui uma caracter�stica muito peculiar. Todas as suas ruas s�o orientadas na direc�o oeste-leste e norte-sul, e todos os quarteir�es s�o do mesmo tamanho, formando uma grid regular. As interse��es de ruas em Planalto s�o identificados pelo n�mero da rua, em cada dire��o, por exemplo, (2,4) representa a interse��o da rua 2 em dire��o oeste-leste e a rua 4 em dire��o norte-sul. Agora suponha que um turista com um obse��o por geometria esta planejando visitar a cidade do Planalto. Nosso turista quer come�ar seu trajeto no ponto central da cidade, marcado com a interse��o (0,0), depois quer caminhar uma quadra para norte, sul, oeste, ou leste, para ver as vista na interse��o (0,1) se va para norte, (0,-1) se va para sul, (1,0) se va para leste e (-1,0) se va para oeste. Nosso turista se sente mais animado ao ver a regularidade da cidade, e decide agora andar mais dois quarteir�es. So que n�o quer mais caminhar na mesma dire��o e quer ir para direita o esquerda, tamb�m n�o quer voltar. No pr�ximo segmento ele caminha tres quarteir�es, depois quatro, cinco, e assim sucessivamente ate chegar ao ponto inicial, sempre trocando de dire��o a cada segmento. Lamentavelmente, nosso visitante quer fazer essa visita em pleno ver�o quando algumas interse��es est�o interrompidas por causa de trabalhos nas ruas. No entanto a prefeitura do planalto sempre publica as informa��es de quais interese��es que est�o bloquedas.


Tarefa
Fa�a um programa que ajude a nosso tourista determinar qual deve ser a ruta, de forma que consiga fazer o trajeto acima especificado.
Entrada
A primeira entrada para o programa � um n�mero inteiro n�o maior que 20 indicando o comprimento do maior segmento. Este � o comprimento do ultimo segmento que leva ao ponto de partida. Na linha seguinte ser� dado um inteiro de 0 a 50 indicando o n�mero de interse��es que est�o bloqueadas. Nas proximas linhas ser�o dadas as coordenadas das interse��es bloqueada. Um par de n�meros inteiros por linha, indicando as coordenadas x e y.
exemplo de Entrada
8
2
-2 0
6 2

Sa�da
Na s�ida deve ser impresso a seq��ncia de carateres N, S, L, O, indicando a dire��o de cada segmento da ruta. Caso n�o seja poss�vel fazer o trajeto especificado, indicar que n�o � poss�vel.
Exemplo de sa�da
O S L N L N O S

as solu��es voce encontra aqui

0 comentários:

Postar um comentário

 
Design by Wordpress Theme | Bloggerized by Free Blogger Templates | coupon codes