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