apostila

o u´ltimo elemento gerado.
O que era o u´ltimo passa a ser o penu´ltimo. A ordem da atualizac¸a˜o destes valo-
res e´ relevante no co´digo em func¸a˜o do esquema de funcionamento de memo´ria do
computador. Trocando-se a ordem dos comandos o algoritmo para de funcionar.
O algoritmo da figura 7.1 e´ normalmente o mais utilizado para este problema,
isto e´, define-se os dois primeiros e depois sucessivamente soma-se os dois u´ltimos e
1Vale a pena ler: http://pt.wikipedia.org/wiki/Nu´mero de Fibonacci.
75
76 CAPI´TULO 7. APLICAC¸O˜ES DAS TE´CNICAS ELEMENTARES
const max=93; (∗ A partir do 94o estoura a capacidade do tipo qword ∗)
begin
ultimo:= 1; (∗ inicializacao das variaveis principais ∗)
penultimo:= 1;
writeln (’1 ’ ,penultimo) ; (∗ imprime os dois primeiros valores ∗)
writeln (’2 ’ ,ultimo) ;
cont:= 3 ; (∗ calcula do terceiro em diante ∗)
while cont <= max do
begin
soma:= penultimo + ultimo ;
writeln (cont , ’ ’ ,soma) ;
penultimo:= ultimo ; (∗ a ordem destes dois comandos ∗)
ultimo:= soma; (∗ eh relevante no codigo ∗)
cont:= cont + 1;
end;
end.
Figura 7.1: Gerando nu´meros da sequeˆncia de Fibonacci.
atualiza-se o u´ltimo como sendo esta soma recentemente gerada e o penu´ltimo como
sendo o que era o u´ltimo. Existem va´rios outros que sa˜o apresentados como exerc´ıcios.
Um problema similar mas alternativo a este e´, por exemplo, saber qual e´ o primeiro
nu´mero de Fibonacci maior do que um determinado valor. Uma pequena alterac¸a˜o
no controle de parada e no local do comando de impressa˜o resolve o novo problema.
Isto e´ apresentado na figura 7.2. A diferenc¸a ba´sica e´ que neste caso na˜o e´ preciso
contar os nu´meros, pois o crite´rio de parada e´ diferente. Mas e´ importante observar
que a parte da gerac¸a˜o dos nu´meros da sequeˆncia na˜o mudou.
const max=1000;
begin
ultimo:= 1; (∗ inicializacao das variaveis principais ∗)
penultimo:= 1;
soma:= penultimo + ultimo ;
while soma<= max do (∗ calcula do terceiro em diante ∗)
begin
penultimo:= ultimo ;
ultimo:= soma;
soma:= penultimo + ultimo ;
end;
writeln (soma) ;
end.
Figura 7.2: Imprimindo o primeiro nu´mero de Fibonacci maior do que 1000.
Uma das maiores belezas dos nu´meros de Fibonacci e´ que a raza˜o entre dois
termos consecutivos converge para um nu´mero irracional conhecido como nu´mero
a´ureo (tambe´m podendo ter outros nomes parecidos). Tambe´m e´ denotado pela letra
grega ϕ e e´ aproximadamente 1.6180339887499.
7.2. MAIOR SEGMENTO CRESCENTE 77
De fato, vejamos a raza˜o entre dois termos consecutivos para alguns nu´meros
pequenos:
1
1
= 1,
2
1
= 2,
3
2
= 1.5,
5
3
= 1.66,
8
5
= 1.60,
13
8
= 1.625,
21
13
= 1.615, . . .
O algoritmo que calcula o nu´mero a´ureo com a precisa˜o desejada, mostrando
os valores intermedia´rios, e´ apresentado na figura 7.3. Notamos que ele verifica a
convergeˆncia da sequeˆncia para a raza˜o a´urea, fazendo as contas ate´ que o erro seja
menor que a precisa˜o desejada. A func¸a˜o abs e´ nativa do Pascal e retorna o valor
absoluto do nu´mero dado como argumento.
Neste exemplo, novamente o ca´lculo central na˜o mudou, isto e´, os nu´meros con-
tinuam a ser gerados da mesma maneira. O que muda e´ o que fazer com eles. No
caso, e´ preciso obter a raza˜o do u´ltimo pelo penu´ltimo. Tambe´m e´ o primeiro exemplo
apresentado que usa nu´meros reais ao inve´s de inteiros.
const PRECISAO=0.00000000000001;
begin
ultimo:= 1; (∗ inicializacao das variaveis principais ∗)
penultimo:= 1;
naureo anterior:= −1; (∗ para funcionar o primeiro teste ∗)
naureo:= 1;
writeln (naureo:15:14) ;
(∗ calcula do terceiro em diante ∗)
while abs(naureo − naureo anterior) >= PRECISAO do
begin
soma:= penultimo + ultimo ;
naureo anterior:= naureo ;
naureo:= soma/ultimo ;
writeln (naureo:15:14) ;
penultimo:= ultimo ;
ultimo:= soma;
end;
end.
Figura 7.3: Verificando a convergeˆncia do nu´mero a´ureo.
Va´rias outras propriedades interessantes sera˜o deixadas como exerc´ıcio.
7.2 Maior segmento crescente
Problema: Dada uma sequeˆncia de n nu´meros naturais, imprimir o valor do com-
primento do segmento crescente de tamanho ma´ximo dentre os nu´meros lidos.
• Por exemplo, se a sequeˆncia for: 5, 10, 3, 2, 4, 7, 9, 8, 5, o comprimento crescente
ma´ximo e´ 4, pois e´ o tamanho do segmento 2, 4, 7, 9.
78 CAPI´TULO 7. APLICAC¸O˜ES DAS TE´CNICAS ELEMENTARES
• Na sequeˆncia 10, 8, 7, 5, 2, o comprimento de um segmento crescente ma´ximo e´
1.
O algoritmo que resolve este problema e´ apresentado na figura 7.4. A soluc¸a˜o exige
um conjunto de varia´veis que controlam o estado da computac¸a˜o, isto e´, que tentam
manter uma certa memo´ria de que tipo de nu´meros foi lido ate´ o momento, segundo
uma dada restric¸a˜o. Os comenta´rios no co´digo ilustram como guardar o tamanho da
sequeˆncia sendo lida no momento em comparac¸a˜o com o maior tamanho lido ate´ o
momento.
Em um certo sentido guarda a mesma ideia do algoritmo para a sequeˆncia de
Fibonacci, pois e´ necessa´rio guardar o valor lido anteriormente para possibilitar a
comparac¸a˜o com o valor atual. Isto e´ necessa´rio para saber se o valor atual e´ maior
que o anterior. Se for maior, estamos em uma sequeˆncia crescente. Caso contra´rio,
trata-se de outra sequeˆncia. A varia´vel tamanho armazena o tamanho da sequeˆncia
crescente sendo lida, enquanto que maiortam registra a maior sequeˆncia crescente que
ja´ foi processada ate´ o momento.
begin
read (n) ; (∗ inicializa as variaveis principais ∗)
tamanho:= 0;
maiortam:= 0;
a anterior:= 0; (∗ zero eh o primeiro numero natural ∗)
i := 1;
while i <= n do
begin
read (a) ;
i f a > a anterior then
tamanho:= tamanho + 1
else
begin
if tamanho > maiortam then (∗ lembra o maior tamanho ∗)
maiortam:= tamanho;
tamanho:= 1; (∗ reinicializa o contador ∗)
end;
a anterior:= a; (∗ lembra do numero anterior ∗)
i := i + 1;
end;
(∗ este ultimo i f testa se a ultima sequencia nao eh a maior ∗)
i f tamanho > maiortam then (∗ lembra o maior tamanho ∗)
maiortam:= tamanho;
writeln (’maior tamanho encontrado: ’ ,maiortam) ;
end.
Figura 7.4: Maior segmento crescente.
7.3. SE´RIES 79
7.3 Se´ries
Nesta sec¸a˜o tratamos de problemas que envolvem o ca´lculo de se´ries, normalmente
utilizadas para ca´lculos de func¸o˜es tais como seno, cosseno, logaritmo, etc. . . A te´cnica
utilizada e´ basicamente aquela dos acumuladores, pore´m, o ca´lculo dos novos termos
somados e´ ligeiramente mais sofisticado e exige atenc¸a˜o do estudante para a boa
compreensa˜o da soluc¸a˜o.
7.3.1 Nu´mero neperiano
Problema: Calcular o valor no nu´mero e = 2.718281 . . . pela se´rie abaixo, conside-
rando apenas os vinte primeiros termos:
e =
1
0!
+
1
1!
+
1
2!
+
1
3!
+
1
4!
+
1
5!
+
1
6!
+
1
7!
+ . . .
A figura 7.5 ilustra uma soluc¸a˜o baseada nas ja´ estudadas te´cnicas dos acumula-
dores e no problema dos fatoriais. Basicamente, o novo termo e´ calculado em func¸a˜o
do fatorial, que, neste caso, aparece no denominador.
const itmax=20;
begin
e:= 0; (∗ inicializacao das variaveis ∗)
fat:= 1;
i := 1; (∗ calculo da serie ∗)
while i <= itmax do
begin
novotermo:= 1/fat ;
e:= e + novotermo;
fat:= i∗fat ;
i := i + 1;
end;
writeln (’e= ’ ,e) ;
end.
Figura 7.5: Ca´lculo do nu´mero neperiano.
O programa poderia ter dispensado o uso da varia´vel novotermo, mas deixamos
assim pois facilita a compreensa˜o de que a grande e nova dificuldade neste problema
e´ “como gerar o novo termo a partir do anterior”? Isto vai ajudar na soluc¸a˜o de
problemas similares, na sequeˆncia do texto.
Neste caso, o enunciado do problema determinou que o programa calculasse 20
termos da se´rie. Alguns enunciados estabelecem como condic¸a˜o de parada um crite´rio
de erro, isto e´, se o ca´lculo em uma iterac¸a˜o difere do ca´lculo anterior por