apostila

o u´ltimo elemento gerado.
O que era o u´ltimo passa a ser o penu´ltimo. A ordem da atualizac¸a\u2dco destes valo-
res e´ relevante no co´digo em func¸a\u2dco 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\u2dcES DAS TE´CNICAS ELEMENTARES
const max=93; (\u2217 A partir do 94o estoura a capacidade do tipo qword \u2217)
begin
ultimo:= 1; (\u2217 inicializacao das variaveis principais \u2217)
penultimo:= 1;
writeln (\u20191 \u2019 ,penultimo) ; (\u2217 imprime os dois primeiros valores \u2217)
writeln (\u20192 \u2019 ,ultimo) ;
cont:= 3 ; (\u2217 calcula do terceiro em diante \u2217)
while cont <= max do
begin
soma:= penultimo + ultimo ;
writeln (cont , \u2019 \u2019 ,soma) ;
penultimo:= ultimo ; (\u2217 a ordem destes dois comandos \u2217)
ultimo:= soma; (\u2217 eh relevante no codigo \u2217)
cont:= cont + 1;
end;
end.
Figura 7.1: Gerando nu´meros da seque\u2c6ncia 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\u2dco apresentados como exerc´\u131cios.
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\u2dco
no controle de parada e no local do comando de impressa\u2dco resolve o novo problema.
Isto e´ apresentado na figura 7.2. A diferenc¸a ba´sica e´ que neste caso na\u2dco e´ preciso
contar os nu´meros, pois o crite´rio de parada e´ diferente. Mas e´ importante observar
que a parte da gerac¸a\u2dco dos nu´meros da seque\u2c6ncia na\u2dco mudou.
const max=1000;
begin
ultimo:= 1; (\u2217 inicializacao das variaveis principais \u2217)
penultimo:= 1;
soma:= penultimo + ultimo ;
while soma<= max do (\u2217 calcula do terceiro em diante \u2217)
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\u2dco 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 \u3d5 e e´ aproximadamente 1.6180339887499.
7.2. MAIOR SEGMENTO CRESCENTE 77
De fato, vejamos a raza\u2dco 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\u2dco desejada, mostrando
os valores intermedia´rios, e´ apresentado na figura 7.3. Notamos que ele verifica a
converge\u2c6ncia da seque\u2c6ncia para a raza\u2dco a´urea, fazendo as contas ate´ que o erro seja
menor que a precisa\u2dco desejada. A func¸a\u2dco abs e´ nativa do Pascal e retorna o valor
absoluto do nu´mero dado como argumento.
Neste exemplo, novamente o ca´lculo central na\u2dco 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\u2dco 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; (\u2217 inicializacao das variaveis principais \u2217)
penultimo:= 1;
naureo anterior:= \u22121; (\u2217 para funcionar o primeiro teste \u2217)
naureo:= 1;
writeln (naureo:15:14) ;
(\u2217 calcula do terceiro em diante \u2217)
while abs(naureo \u2212 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\u2c6ncia do nu´mero a´ureo.
Va´rias outras propriedades interessantes sera\u2dco deixadas como exerc´\u131cio.
7.2 Maior segmento crescente
Problema: Dada uma seque\u2c6ncia de n nu´meros naturais, imprimir o valor do com-
primento do segmento crescente de tamanho ma´ximo dentre os nu´meros lidos.
\u2022 Por exemplo, se a seque\u2c6ncia 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\u2dcES DAS TE´CNICAS ELEMENTARES
\u2022 Na seque\u2c6ncia 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\u2dco exige
um conjunto de varia´veis que controlam o estado da computac¸a\u2dco, 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\u2dco. Os comenta´rios no co´digo ilustram como guardar o tamanho da
seque\u2c6ncia sendo lida no momento em comparac¸a\u2dco com o maior tamanho lido ate´ o
momento.
Em um certo sentido guarda a mesma ideia do algoritmo para a seque\u2c6ncia de
Fibonacci, pois e´ necessa´rio guardar o valor lido anteriormente para possibilitar a
comparac¸a\u2dco 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\u2c6ncia crescente. Caso contra´rio,
trata-se de outra seque\u2c6ncia. A varia´vel tamanho armazena o tamanho da seque\u2c6ncia
crescente sendo lida, enquanto que maiortam registra a maior seque\u2c6ncia crescente que
ja´ foi processada ate´ o momento.
begin
read (n) ; (\u2217 inicializa as variaveis principais \u2217)
tamanho:= 0;
maiortam:= 0;
a anterior:= 0; (\u2217 zero eh o primeiro numero natural \u2217)
i := 1;
while i <= n do
begin
read (a) ;
i f a > a anterior then
tamanho:= tamanho + 1
else
begin
if tamanho > maiortam then (\u2217 lembra o maior tamanho \u2217)
maiortam:= tamanho;
tamanho:= 1; (\u2217 reinicializa o contador \u2217)
end;
a anterior:= a; (\u2217 lembra do numero anterior \u2217)
i := i + 1;
end;
(\u2217 este ultimo i f testa se a ultima sequencia nao eh a maior \u2217)
i f tamanho > maiortam then (\u2217 lembra o maior tamanho \u2217)
maiortam:= tamanho;
writeln (\u2019maior tamanho encontrado: \u2019 ,maiortam) ;
end.
Figura 7.4: Maior segmento crescente.
7.3. SE´RIES 79
7.3 Se´ries
Nesta sec¸a\u2dco tratamos de problemas que envolvem o ca´lculo de se´ries, normalmente
utilizadas para ca´lculos de func¸o\u2dces 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\u2dco do estudante para a boa
compreensa\u2dco da soluc¸a\u2dco.
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\u2dco baseada nas ja´ estudadas te´cnicas dos acumula-
dores e no problema dos fatoriais. Basicamente, o novo termo e´ calculado em func¸a\u2dco
do fatorial, que, neste caso, aparece no denominador.
const itmax=20;
begin
e:= 0; (\u2217 inicializacao das variaveis \u2217)
fat:= 1;
i := 1; (\u2217 calculo da serie \u2217)
while i <= itmax do
begin
novotermo:= 1/fat ;
e:= e + novotermo;
fat:= i\u2217fat ;
i := i + 1;
end;
writeln (\u2019e= \u2019 ,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\u2dco de que a grande e nova dificuldade neste problema
e´ \u201ccomo gerar o novo termo a partir do anterior\u201d? Isto vai ajudar na soluc¸a\u2dco de
problemas similares, na seque\u2c6ncia do texto.
Neste caso, o enunciado do problema determinou que o programa calculasse 20
termos da se´rie. Alguns enunciados estabelecem como condic¸a\u2dco de parada um crite´rio
de erro, isto e´, se o ca´lculo em uma iterac¸a\u2dco difere do ca´lculo anterior por