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