como sendo uma se´rie especial de poteˆncias de 2. Em seguida apresenta o “algoritmo para conversa˜o para bina´rio”, baseado em uma sequeˆncia de diviso˜es por 2. O resultado se obte´m tomando- se os restos das sucessivas diviso˜es por 2 “ao contra´rio”, isto e´, do u´ltimo resto de divisa˜o por 2 ate´ o primeiro. Por exemplo, tomando o decimal 22 como entrada: 22 div 2 0 11 div 2 1 5 div 2 1 2 div 2 0 1 div 2 1 0 Enta˜o o nu´mero bina´rio correspondente ao 22 seria 10110. O programa ilustrado na figura 6.13 mostra o co´digo para esta versa˜o do algoritmo. Ocorre que este algoritmo imprime o bina´rio ao contra´rio, isto e´, a sa´ıda para a entrada 22 seria 01101 e na˜o 10110 como deveria. Na verdade, basta lembrar que desde o in´ıcio deste texto se insiste em afirmar que para um mesmo problema existem diversas soluc¸o˜es. Neste caso, basta usar a definic¸a˜o de nu´meros bina´rios.1 De fato, o nu´mero decimal 22 pode ser escrito numa se´rie de poteˆncias de 2 como segue: 22 = 1× 24 + 0× 23 + 1× 22 + 1× 21 + 0× 20 1Este exemplo nos ocorreu apo´s trocas de emails com o Allan Neves, enta˜o aluno da disciplina. Agradecemos a ele por isto. 64 CAPI´TULO 6. TE´CNICAS ELEMENTARES program converteparabinario ; const max=128; var n: integer ; begin write (’entre com um numero entre 0 e 255: ’) ; read (n) ; while n <> 0 do begin write (n mod 2) ; n:= n div 2; end; end. Figura 6.13: Convertendo para bina´rio, versa˜o 1. A questa˜o e´ saber quantas vezes cada poteˆncia de 2 cabe no nu´mero original. Este ca´lculo e´ simples e a soluc¸a˜o e´ mostrada na figura 6.14. program converteparabinario ; const max=128; var diferenca , n, pot2 : integer ; begin write (’entre com um numero entre 0 e 255: ’) ; read (n) ; pot2:= max; while pot2 <> 0 do begin diferenca:= n − pot2 ; i f diferenca >= 0 then begin write (1) ; n:= diferenca ; end else write (0) ; pot2:= pot2 div 2; end; end. Figura 6.14: Convertendo para bina´rio, versa˜o 2. 6.3.4 Menor de 3, segunda versa˜o Generalizando o problema de imprimir o menor entre treˆs nu´meros de entrada, vamos agora ler uma sequeˆncia de trincas de nu´meros e imprimir, para cada entrada, o menor deles. A entrada termina quando os treˆs nu´meros lidos forem iguais. Veja como fica o programa na figura 6.15. 6.4. REPETIC¸O˜ES DENTRO DE CONDIC¸O˜ES 65 program imprime menor (input ,utput) ; var a, b, c : Integer ; begin write(’Entre com tres numeros inteiros: ’) ; read(a , b, c) ; while not ((a = b) and (b = c)) do (∗ falso quando a=b=c ∗) begin if a < b then if a < c then writeln (’o menor dos tres eh ’ ,a) else writeln (’o menor dos tres eh ’ ,c) else if a < c then writeln (’o menor dos tres eh ’ ,b) else writeln (’o menor dos tres eh ’ ,c) write(’entre com tres numeros inteiros: ’) ; read(a , b, c) ; end; end. Figura 6.15: Imprimir o menor dentre 3 nu´meros lidos. 6.4 Repetic¸o˜es dentro de condic¸o˜es Os problemas da sec¸a˜o anterior envolveram a mesma estrutura ba´sica, isto e´, um teste sob controle do comando de repetic¸a˜o, com ou sem a parte else do if. Agora veremos o contra´rio, isto e´, um comando de repetic¸a˜o no escopo do comando de desvio condicional. 6.4.1 Calculo do MDC Problema: Imprimir o Ma´ximo Divisor Comum (MDC) entre dois nu´meros dados. O conceito matema´tico de ma´ximo divisor comum entre dois nu´meros dados a e b envolve a fatorac¸a˜o de cada nu´mero como um produto de fatores primos, escolhendo-se os fatores primos que se repetem com a poteˆncia mı´nima. Exemplo: Calcular o MDC entre 24 e 45. 72 = 23 × 32 135 = 33 × 5 66 CAPI´TULO 6. TE´CNICAS ELEMENTARES Da teoria conclui-se que o MDC entre 72 e 135 e´ 32, pois o 3 e´ o u´nico fator primo que se repete em ambos os nu´meros de entrada, e a menor poteˆncia comum e´ 2. Implementar este algoritmo para encontrar o MDC e´ complicado no momento pois na˜o sabemos ainda como obter uma sequeˆncia de primos. Tambe´m na˜o sabemos ainda o quanto caro e´ calcular um nu´mero primo. Euclides propoˆs um algoritmo eficiente para se obter o MDC entre dois nu´meros que na˜o requer o uso da fatorac¸a˜o. Trata-se de um dos primeiros algoritmos conheci- dos, pois foi proposto por volta do ano 300 a.c. O algoritmo pode ser visto atualmente em Pascal conforme esta´ ilustrado na figura 6.16. program mdcporeuclides ; var a, b, resto : integer ; begin read (a ,b) ; i f (a <> 0) AND (b <> 0)) then begin resto:= a mod b; while resto <> 0 do begin a:= b; b:= resto ; resto:= a mod b; end; writeln (’mdc = ’ , b) ; end else writeln (’o algoritmo nao funciona para entradas nulas.’) ; end. Figura 6.16: Algoritmo de Euclides para ca´lculo do MDC. Este algoritmo mostra um caso em que o comando de repetic¸a˜o esta´ dentro do escopo do comando de desvio condicional. Efetivamente os ca´lculos sa˜o feitos somente se as entradas na˜o forem nulas. 6.5 Repetic¸o˜es aninhadas Nesta sec¸a˜o estudaremos problemas para os quais os algoritmos exigem o aninhamento de repetic¸o˜es. 6.5.1 Tabuada Problema: Imprimir as tabuadas do 1 ao 10. 6.5. REPETIC¸O˜ES ANINHADAS 67 program tabuada; var i , j : integer ; begin i := 1; while i <= 10 do begin j:= 1; while j <= 10 do begin writeln ( i ,’x’ , j ,’= ’ , i∗ j ) ; (∗ comando mais interno ∗) j:= j + 1; end; writeln ; i := i + 1; end; end. Figura 6.17: Tabuadas do 1 ao 10. No co´digo apresentado na figura 6.17, para cada valor de i, os valores de j variam de 1 a 10, o que faz com que o comando writeln mais interno seja executado 100 vezes ao longo do programa. Se foˆssemos imprimir a tabuada do 1 ao 1000, este comando seria executado um milha˜o de vezes. Em termos gene´ricos, para uma entrada de tamanho n, o comando mais interno e´ executado da ordem de n2 vezes, por isto sa˜o conhecidos como algoritmos de complexidade quadra´tica. Nos programas anteriores, o ma´ximo que t´ınhamos era uma complexidade linear com relac¸a˜o ao tamanho da entrada. 6.5.2 Fatorial O problema seguinte e´ bastante relevante neste ponto, pois nos permitira´ uma ana´lise sobre a te´cnica usada para resolveˆ-lo. A te´cnica ba´sica implementa diretamente a definic¸a˜o de fatorial e usa uma estrutura baseada em um aninhamento triplo: um desvio condicional no escopo de um aninhamento duplo. Problema: Imprimir o valor do fatorial de todos os nu´meros entre 1 e n, sendo n fornecido pelo usua´rio. O fatorial de n e´ assim definido: n= n× (n− 1)× (n− 2)× . . .× 3× 2× 1 Logo, o ca´lculo do fatorial de um nu´mero tem complexidade linear com relac¸a˜o ao tamanho da entrada e pode ser facilmente implementado usando a te´cnica elementar dos acumuladores, conforme e´ ilustrado na figura 6.18. 68 CAPI´TULO 6. TE´CNICAS ELEMENTARES program fatorial ; var i , n, fat : integer ; begin read (n) ; fat:= 1; (∗ inicializacao do acumulador ∗) i := n; while i >= 1 do begin fat:= fat ∗ i ; i f i > 1 then write ( i ,’x’) else write ( i ,’= ’) ; i := i − 1; end; writeln ( fat ) ; end. Figura 6.18: Obtendo o fatorial de n. Esta versa˜o resolve o problema para o ca´lculo do fatorial de um u´nico nu´mero dado como entrada e portanto na˜o resolve o enunciado. Pore´m, basta colocar este trecho sob o controle de outra repetic¸a˜o que se obte´m o efeito desejado. A soluc¸a˜o e´ apresentada na figura 6.19. E´ verdade que o programa funciona, mas e´ extremamente ineficiente e repleto de ca´lculos redundantes. De fato, o usua´rio que testou o programa para o valor de n = 7 vai perceber que a multiplicac¸a˜o de 2 × 1 ocorreu 6 vezes, a multiplicac¸a˜o de 3 × 2 ocorreu 5 vezes, a de 4 × 6 ocorreu 4 vezes e assim por diante. O programador na˜o explorou corretamente os ca´lculos ja´ feitos anteriormente. i Em outras palavras, o programa pode ficar mais eficiente se for feito como