ALGORITMOS E ESTRUTURAS DE DADOS I
259 pág.

ALGORITMOS E ESTRUTURAS DE DADOS I


DisciplinaAlgoritmos e Estrutura de Dados I708 materiais7.919 seguidores
Pré-visualização50 páginas
zero e que sa\u2dco
incrementadas a cada vez que um nu´mero e´ identificado como positivo ou na\u2dco. Esta
ideia pode ser vista na figura 6.9. Importante notar a similaridade das duas soluc¸o\u2dces.
Os problemas sa\u2dco ligeiramente diferentes, eles diferem em um dos subproblemas ape-
nas: um deve imprimir, o outro deve acumular. Os outros problemas tais como o
controle do lac¸o e a leitura dos dados sa\u2dco exatamente os mesmos problemas.
Podemos usar o mesmo racioc´\u131nio para resolver toda uma classe de problemas
similares, isto e´, imprimir a soma de nu´meros que satisfazem alguma propriedade.
No caso do problema anterior, a propriedade era \u201cser negativo\u201d ou \u201cser positivo\u201d.
Mas poderia ser qualquer outra coisa, como por exemplo \u201cser diferente de zero\u201d, \u201cser
primo\u201d, \u201cser mu´ltiplo de 50\u201d ou algo mais complexo como \u201cter saldo positivo nos
u´ltimos 12 meses e na\u2dco estar devendo para o imposto de renda\u201d.
Vejamos um problema similar para uma propriedade simples, cuja soluc¸a\u2dco pode
ser facilmente adaptada do algoritmo anterior.
6.3. DESVIOS CONDICIONAIS DENTRO DE REPETIC¸O\u2dcES 61
program contar ;
var i , (\u2217 serve para contar ate 30 \u2217)
conta positivos , (\u2217 serve para contar os positivos \u2217)
conta outros , (\u2217 serve para contar os nao positivos \u2217)
a: integer ; (\u2217 numeros lidos na entrada \u2217)
begin
conta positivos:= 0; (\u2217 eh preciso inicializar a variavel \u2217)
conta outros:= 0;
i := 1;
while i <= 30 do
begin
read (a) ;
i f a > 0 then
conta positivos:= conta positivos + 1
else
conta outros:= conta outros + 1;
i:= i + 1;
end;
writeln (\u2019A quantidade de positivos lidos eh \u2019 , conta positivos) ;
writeln (\u2019A quantidade de nao positivos lidos eh \u2019 , conta outros) ;
end.
Figura 6.9: Contando os positivos e os negativos e nulos.
6.3.2 Somando pares e \u131´mpares
Problema: Ler uma seque\u2c6ncia de nu´meros e imprimir separadamente a soma dos
que sa\u2dco pares e a soma dos que sa\u2dco \u131´mpares. O programa deve terminar quando o
nu´mero lido for o zero. Este u´ltimo nu´mero tambe´m deve ser ignorado.
No programa ilustrado na figura 6.10, basicamente foi colocado no lugar do if
x > 0 then a traduc¸a\u2dco da expressa\u2dco if \u201cx e´ par\u201d then, traduc¸a\u2dco esta que envolve o uso
da operac¸a\u2dco de resto de divisa\u2dco inteira. Todo nu´mero que, dividido por 2, resulta em
resto 0 so´ pode ser par. Caso contra´rio e´ \u131´mpar. Tambe´m foi feita uma mudanc¸a no
nome das varia´veis para facilitar a compreensa\u2dco do co´digo.
A propriedade pode ser ta\u2dco complexa quanto se queira, mas e´ importante observar
que o co´digo de base na\u2dco muda muito. Observe que ha´ uma leitura, o teste, algum
processamento e, por u´ltimo, a leitura do pro´ximo valor, repetindo-se o co´digo.
Problema: Ler nu´meros do teclado, ate´ ler um zero, e imprimir apenas os que sa\u2dco
ao mesmo tempo mu´ltiplos de 7 mas na\u2dco sa\u2dco mu´ltiplos de 2.
Soluc¸a\u2dco similar (apresentada na figura 6.11). Um lac¸o controla o te´rmino da
repetic¸a\u2dco, e um desvio condicional verifica a propriedade e algum co´digo e´ executado
em seguida (no caso uma simples impressa\u2dco na tela).
62 CAPI´TULO 6. TE´CNICAS ELEMENTARES
program somapareseimpares ;
var x, somapares , somaimpares: integer ;
begin
somapares:= 0;
somaimpares:= 0;
read (x) ;
while x <> 0 do
begin
if x mod 2 = 0 then (\u2217 verdadeiro quando x eh par \u2217)
somapares:= somapares + x
else
somaimpares:= somaimpares + x;
read (x) ;
end;
writeln (somapares , somaimpares) ;
end.
Figura 6.10: Soma pares e \u131´mpares.
program somaquadradosperfeitos ;
var a: integer ;
begin
read (a) ;
while a <> 0 do
begin
if (a mod 7 = 0) AND (a mod 2 <> 0) then
writeln (a) ;
read (a) ;
end;
end.
Figura 6.11: Imprime os mu´ltiplos de 7 que na\u2dco sa\u2dco mu´ltiplos de 2.
Um terceiro problema similar e´ apresentado a seguir.
Problema: Ler nu´meros do teclado, ate´ ler um zero, e imprimir apenas os que forem
mu´ltiplos de 3 maiores do que 50 e menores ou iguais a 201.
Novamente, mesmo racioc´\u131nio (soluc¸a\u2dco na figura 6.12). Apenas a propriedade a
ser satisfeita e´ mais complexa, envolve uma expressa\u2dco booleana contendo conectivos
de conjunc¸a\u2dco. E´ importante para o estudante comparar os tre\u2c6s u´ltimos co´digos e
perceber a enorme similaridade entre eles.
6.3.3 Convertendo para bina´rio
Este problema e´ um desafio que pode ser resolvido com a mesma ideia de se aninhar
um desvio condicional sob o escopo de uma repetic¸a\u2dco, combinada com o uso dos
6.3. DESVIOS CONDICIONAIS DENTRO DE REPETIC¸O\u2dcES 63
program somaquadradosperfeitos ;
var a: integer ;
begin
read (a) ;
while a <> 0 do
begin
if (a mod 3 = 0) AND (a > 50) AND (a <= 201) then
writeln (a) ;
read (a) ;
end;
end.
Figura 6.12: Imprime os mu´ltiplos de 3 lidos entre 51 e 201.
acumuladores.
Problema: Dado um nu´mero inteiro entre 0 e 255 imprimir este nu´mero em seu
formato bina´rio.
Este e´ um exemplo cla´ssico em que o estudante esquece da teoria. Tradicional-
mente, o professor apresenta a definic¸a\u2dco de nu´meros bina´rios, 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