A maior rede de estudos do Brasil

Grátis
146 pág.
Programando com PASCAL - Jaime Evaristo

Pré-visualização | Página 28 de 50

escritas em matemática. Por exemplo, a implementação recursiva do fatorial pode ser feita em 
Pascal simplesmente da seguinte forma:
{Programa para gerar uma tabela de fatoriais}
program TabelaFatoriais;
var i : integer;
{Funcao recursiva para o cálculo do fatorial de um inteiro não negativo}
Function FatRec (n : integer) : longint;
begin
if (n = 0) or (n = 1)
then
 FatRec := 1
else
FatRec := (n * FatRec(n - 1));
end;
{Programa principal}
begin
for i := 1 to 10 do
writeln(i, '! = ', FatRec(i));
end.
É interessante ter uma idéia do que acontece na recursividade. Quando se ativa uma função recursiva, 
cada nova chamada da mesma é empilhada na chamada pilha de recursão até que a condição de escape seja 
atingida. A partir daí, cada ativação pendente é desempilhada (evidentemente, na ordem inversa do 
empilhamento) e as operações vão sendo realizadas. No programa acima, quando i = 5, temos a seguinte 
seqüência de operações:
1. Após a ativação de FatRec(5) 
FatRec(5) n
5*FatRec(4) 5
2. Após a ativação de FatRec(4)
FatRec(5) n FatRec(4) n
5*FatRec(4) 5 4*FatRec(3) 3
3. Após a ativação de FatRec(3)
FatRec(5) n FatRec(4) n FatRec(3) n
5*FatRec(4) 5 4*FatRec(3) 3 3*FatRec(2) 2
4. Após a ativação de FatRec(2)
FatRec(5) n FatRec(4) n FatRec(3) n FatRec(2) n
5*FatRec(4) 5 4*FatRec(3) 3 3*FatRec(2) 2 2*FatRec(1) 1
5. Após a ativação de FatRec(1)
FatRec(5) n FatRec(4) n FatRec(3) n FatRec(2) n
5*FatRec(4) 5 4*FatRec(3) 3 3*FatRec(2) 2 2*1 = 2 1
FatRec(5) n FatRec(4) n FatRec(3) n
5*FatRec(4) 5 4*FatRec(3) 3 3*2 = 6 2
FatRec(5) n FatRec(4) n
5*FatRec(4) 5 4*6 = 24 3
FatRec(5) n
5*24 = 120 5
Embora a utilização da recursividade apresente a vantagem de programas mais simples, ela traz o 
inconveniente de sacrificar a eficiência do programa. Isto ocorre devido à necessidade de chamadas 
sucessivas da função e das operações de empilhamento e desempilhamento, o que demanda um tempo maior 
de computação e uma maior necessidade de uso de memória. Esta observação faz com que a solução não-
recursiva (chamada solução iterativa) seja preferível. No capítulo 10, apresentaremos um exemplo de uma 
função recursiva que é tão eficiente quanto a função iterativa.
Um outro exemplo interessante de recursividade é a implementação do jogo conhecido como Torre de 
Hanói que foi objeto do exercício proposto 2 da seção 1.12. Para lembrar, este jogo consiste de três torres 
chamadas origem, destino e auxiliar e um conjunto de n discos de diâmetros diferentes, colocados na torre 
origem, na ordem decrescente dos seus diâmetros. O objetivo do jogo é, movendo um único disco de cada 
vez e não podendo colocar um disco sobre outro de diâmetro menor, transportar todos os discos para a torre 
destino, podendo usar a torre auxiliar como passagem intermediária dos discos.
Indicando com torre 1  torre 2 o movimento do disco que no momento está na parte superior da torre 1 
para a torre 2, teríamos a seguinte solução para o caso n = 2:
1. origem  auxiliar
2. origem  destino
3. auxiliar  destino
Para n = 3, a solução seria:
1. origem  destino
2. origem  auxiliar
3. destino  auxiliar
4. origem  destino
5. auxiliar  origem
6. auxiliar  destino
7. origem  destino 
Observe que os três movimentos iniciais transferem dois discos da torre origem para a torre auxiliar, 
utilizando a torre destino como auxiliar; o quarto movimento transfere o maior dos discos da origem para 
destino e os últimos movimentos transferem os dois discos que estão na auxiliar para destino, utilizando 
origem como torre auxiliar.
Assim, a operação Move(3, origem, auxiliar, destino) - move três discos da origem para destino usando 
auxiliar como torre auxiliar - pode ser decomposta em três etapas:
1. Move(2, origem, destino, auxiliar) - move dois discos de origem para auxiliar usando destino 
como auxiliar;
2. Move um disco de origem para destino
3. Move(2, auxiliar, origem, destino) - move dois discos de auxiliar para destino usando origem 
como auxiliar.
O interessante é que é fácil mostrar que este raciocínio se generaliza para n discos, de modo que a 
operação Move(n, a, b, c) pode ser obtida com as seguintes operações:
1. Move(n-1, a, c, b)
2. Move um disco de a para c
3. Move(n-1, b, a, c) 
O mais interessante ainda é que isto pode ser implementado em Pascal, através do seguinte programa:
{Programa que implementa o jogo Torre de Hanoi}
program TorreHanoi;
var n : integer;
 {Procedimento para indicar o movimento do disco superior de uma para outra torre}
procedure MoveDisco(t1, t2 : string);
begin
writeln(t1,'  ', t2);
end;
{Procedimento recursivo para a Torre de Hanoi}
procedure Hanoi(x : integer, o, a, d : string);
 begin
if x > 0
then
begin
 Hanoi(x - 1, o, d, a);
MoveDisco(o, d);
Hanoi(x - 1, a, o, d);
end;
end;
{programa principal}
begin
writeln('Digite o numero de discos ');
readln(n);
Hanoi(n, 'origem', 'auxiliar', 'destino');
end.
5.8 Exercícios propostos
1. Escreva duas funções, uma iterativa e a outra recursiva, que retornem o k-ésimo dígito (da direita para 
a esquerda) de um inteiro n. Por exemplo, K_esimoDigito(2845, 3) = 8.
2. O fatorial ímpar de um número n ímpar positivo é o produto de todos os números ímpares positivos 
menores do que ou iguais a n. Indicando o fatorial ímpar de n por n| temos, n| = 1 . 3. 5 . ... . n. Por 
exemplo, 7| = 1 . 3 . 5 . 7 = 105. Escreva funções iterativas e recursivas para a determinação do fatorial ímpar 
de um inteiro ímpar dado.
3. Como na questão anterior, o fatorial primo de um número primo positivo é o produto de todos os 
primos positivos menores do que ou iguais a ele, p# = 2 . 3 . 5 . 7 . ... .p. Por exemplo, 7# = 2 . 3 . 5 . 7 = 210. 
Escreva um programa que determine o fatorial primo de um primo dado.
4. Escreva uma função que retorne a soma dos algarismos de um inteiro positivo dado.
5. Escreva uma função recursiva que retorne o n-ésimo termo da seqüência de Fibbonaci, n dado.
6. Escreva uma função que receba um número inteiro n e forneça o número formado pelos algarismos de 
n escritos na ordem inversa. Por exemplo, se o número dado for 3876, a função deve fornecer 6783.
7. Escreva uma função recursiva que retorne o máximo divisor comum de dois inteiros dados.
8. Escreva uma função recursiva que retorne o mínimo múltiplo comum de dois inteiros dados.
Observação
Para receber as respostas dos exercícios propostos, encaminhe mensagem para jaime@ccen.ufal.br, 
assunto RESPOSTAS EXERCÍCIOS PASCAL, contendo NOME, INSTITUIÇÃO (se for o caso), 
CIDADE/ESTADO e CATEGORIA (docente, estudante ou auto-didata).
Capítulo 6 Vetores
6.1 O que são vetores
Nos exemplos 6 e 7 da seção 4.5, discutimos programas para a determinação da média aritmética de uma 
relação de números dados. Para tal, utilizamos uma variável simples para receber os números, sendo que 
cada vez que um número, a partir do segundo, era recebido, o anterior era "perdido". Ou seja, a relação de 
números não era armazenada. Imagine que a relação fosse uma relação de notas escolares e que, além da 
média, se quisesse também saber a quantidade de alunos que obtiveram nota acima da média ou uma outra 
medida estatística que dependesse da média (desvio padrão, por exemplo). Neste caso, haveria a necessidade 
de que a relação fosse redigitada o que, além da duplicidade do trabalho, facilitaria os erros de digitação. É 
importante então que exista uma "variável" capaz de armazenar vários valores simultaneamente de tal forma 
que se possa acessar cada um deles independentemente de se acessar os demais. 
Um outro exemplo é o caso do exemplo 2 da seção 4.5. Lá queríamos a relação dos divisores de um 
inteiro dado e estes divisores eram apenas exibidos, não sendo armazenados como recomendado