apostila

como sendo uma se´rie
especial de pote\u2c6ncias de 2. Em seguida apresenta o \u201calgoritmo para conversa\u2dco para
bina´rio\u201d, baseado em uma seque\u2c6ncia de diviso\u2dces por 2. O resultado se obte´m tomando-
se os restos das sucessivas diviso\u2dces por 2 \u201cao contra´rio\u201d, isto e´, do u´ltimo resto de
divisa\u2dco 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\u2dco o nu´mero bina´rio correspondente ao 22 seria 10110. O programa ilustrado
na figura 6.13 mostra o co´digo para esta versa\u2dco do algoritmo.
Ocorre que este algoritmo imprime o bina´rio ao contra´rio, isto e´, a sa´\u131da para a
entrada 22 seria 01101 e na\u2dco 10110 como deveria. Na verdade, basta lembrar que
desde o in´\u131cio deste texto se insiste em afirmar que para um mesmo problema existem
diversas soluc¸o\u2dces. Neste caso, basta usar a definic¸a\u2dco de nu´meros bina´rios.1
De fato, o nu´mero decimal 22 pode ser escrito numa se´rie de pote\u2c6ncias 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\u2dco 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 (\u2019entre com um numero entre 0 e 255: \u2019) ;
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\u2dco 1.
A questa\u2dco e´ saber quantas vezes cada pote\u2c6ncia de 2 cabe no nu´mero original. Este
ca´lculo e´ simples e a soluc¸a\u2dco e´ mostrada na figura 6.14.
program converteparabinario ;
const max=128;
var diferenca , n, pot2 : integer ;
begin
write (\u2019entre com um numero entre 0 e 255: \u2019) ;
read (n) ;
pot2:= max;
while pot2 <> 0 do
begin
diferenca:= n \u2212 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\u2dco 2.
6.3.4 Menor de 3, segunda versa\u2dco
Generalizando o problema de imprimir o menor entre tre\u2c6s nu´meros de entrada, vamos
agora ler uma seque\u2c6ncia de trincas de nu´meros e imprimir, para cada entrada, o menor
deles. A entrada termina quando os tre\u2c6s nu´meros lidos forem iguais. Veja como fica
o programa na figura 6.15.
6.4. REPETIC¸O\u2dcES DENTRO DE CONDIC¸O\u2dcES 65
program imprime menor (input ,utput) ;
var
a, b, c : Integer ;
begin
write(\u2019Entre com tres numeros inteiros: \u2019) ;
read(a , b, c) ;
while not ((a = b) and (b = c)) do (\u2217 falso quando a=b=c \u2217)
begin
if a < b then
if a < c then
writeln (\u2019o menor dos tres eh \u2019 ,a)
else
writeln (\u2019o menor dos tres eh \u2019 ,c)
else
if a < c then
writeln (\u2019o menor dos tres eh \u2019 ,b)
else
writeln (\u2019o menor dos tres eh \u2019 ,c)
write(\u2019entre com tres numeros inteiros: \u2019) ;
read(a , b, c) ;
end;
end.
Figura 6.15: Imprimir o menor dentre 3 nu´meros lidos.
6.4 Repetic¸o\u2dces dentro de condic¸o\u2dces
Os problemas da sec¸a\u2dco anterior envolveram a mesma estrutura ba´sica, isto e´, um
teste sob controle do comando de repetic¸a\u2dco, com ou sem a parte else do if. Agora
veremos o contra´rio, isto e´, um comando de repetic¸a\u2dco 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\u2dco de cada nu´mero como um produto de fatores primos, escolhendo-se
os fatores primos que se repetem com a pote\u2c6ncia m\u131´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\u2c6ncia comum e´ 2.
Implementar este algoritmo para encontrar o MDC e´ complicado no momento pois
na\u2dco sabemos ainda como obter uma seque\u2c6ncia de primos. Tambe´m na\u2dco sabemos ainda
o quanto caro e´ calcular um nu´mero primo.
Euclides propo\u2c6s um algoritmo eficiente para se obter o MDC entre dois nu´meros
que na\u2dco requer o uso da fatorac¸a\u2dco. 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 (\u2019mdc = \u2019 , b) ;
end
else
writeln (\u2019o algoritmo nao funciona para entradas nulas.\u2019) ;
end.
Figura 6.16: Algoritmo de Euclides para ca´lculo do MDC.
Este algoritmo mostra um caso em que o comando de repetic¸a\u2dco esta´ dentro do
escopo do comando de desvio condicional. Efetivamente os ca´lculos sa\u2dco feitos somente
se as entradas na\u2dco forem nulas.
6.5 Repetic¸o\u2dces aninhadas
Nesta sec¸a\u2dco estudaremos problemas para os quais os algoritmos exigem o aninhamento
de repetic¸o\u2dces.
6.5.1 Tabuada
Problema: Imprimir as tabuadas do 1 ao 10.
6.5. REPETIC¸O\u2dcES 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 ,\u2019x\u2019 , j ,\u2019= \u2019 , i\u2217 j ) ; (\u2217 comando mais interno \u2217)
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\u2c6ssemos imprimir a tabuada do 1 ao 1000, este comando
seria executado um milha\u2dco 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\u2dco
conhecidos como algoritmos de complexidade quadra´tica. Nos programas anteriores,
o ma´ximo que t´\u131nhamos era uma complexidade linear com relac¸a\u2dco 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\u2c6-lo. A te´cnica ba´sica implementa diretamente a
definic¸a\u2dco 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\u2212 1)× (n\u2212 2)× . . .× 3× 2× 1
Logo, o ca´lculo do fatorial de um nu´mero tem complexidade linear com relac¸a\u2dco 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; (\u2217 inicializacao do acumulador \u2217)
i := n;
while i >= 1 do
begin
fat:= fat \u2217 i ;
i f i > 1 then
write ( i ,\u2019x\u2019)
else
write ( i ,\u2019= \u2019) ;
i := i \u2212 1;
end;
writeln ( fat ) ;
end.
Figura 6.18: Obtendo o fatorial de n.
Esta versa\u2dco resolve o problema para o ca´lculo do fatorial de um u´nico nu´mero
dado como entrada e portanto na\u2dco resolve o enunciado. Pore´m, basta colocar este
trecho sob o controle de outra repetic¸a\u2dco que se obte´m o efeito desejado. A soluc¸a\u2dco 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\u2dco de 2 × 1 ocorreu 6 vezes, a multiplicac¸a\u2dco de 3 × 2
ocorreu 5 vezes, a de 4 × 6 ocorreu 4 vezes e assim por diante. O programador na\u2dco
explorou corretamente os ca´lculos ja´ feitos anteriormente. i
Em outras palavras, o programa pode ficar mais eficiente se for feito como