apostila

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