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
do algoritmo anterior, ter´\u131amos que escrever algo como ilustrado na
figura 6.2.
program soma valores 50 ;
var
a1, a2, a3 , a4, a5, a6, a7, a8 , a9, a10, a11, a12, a13, a14, a15, a16, a17,
a18, a19, a20, a21, a22, a23, a24, a25, a26, a27, a28, a29, a30, a31, a32,
a33, a34, a35, a36, a37, a38, a39, a40, a41, a42, a43, a44, a45, a46, a47,
a48, a49, a50: integer ;
begin
read (a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15,
a16, a17, a18, a19, a20, a21, a22, a23, a24, a25, a26, a27, a28,
a29, a30, a31, a32, a33, a34, a35, a36, a37, a38, a39, a40, a41,
a42, a43, a44, a45, a46, a47, a48, a49, a50) ;
writeln (a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 + a9 + a10 + a11 + a12 +
a13 + a14 + a15 + a16 + a17 + a18 + a19 + a20 + a21 + a22 + a23 +
a24 + a25 + a26 + a27 + a28 + a29 + a30 + a31 + a32 + a33 + a34 +
a35 + a36 + a37 + a38 + a39 + a40 + a41 + a42 + a43 + a44 + a45 +
a46 + a47 + a48 + a49 + a50) ;
end.
Figura 6.2: Imprimindo a soma de 50 nu´meros lidos no teclado.
E´ o´bvio que esta te´cnica na\u2dco e´ adequada. Ale´m disto, so´ pode ser usada quando
se sabe quantos nu´meros sera\u2dco fornecidos. Para o problema abaixo, o algoritmo na\u2dco
pode ser usado.
Problema: Ler uma seque\u2c6ncia de nu´meros positivos do teclado e imprimir a soma
deles. O programa deve terminar quando o nu´mero lido do teclado for zero.
Como usar uma varia´vel para cada valor lido? Uma vez que na\u2dco se sabe, a
princ´\u131pio, quantos nu´meros sera\u2dco digitados, na\u2dco ha´ como fazer isto. Logo, a te´cnica
de soluc¸a\u2dco na\u2dco pode ser esta.
O algoritmo apresentado na figura 6.3 faz uso de uma te´cnica elementar em pro-
gramac¸a\u2dco que e´ o uso de acumuladores.
Conve´m observar que a parte do algoritmo relativa a entrada de dados controlada
pelo lac¸o ja´ foi estudada no cap´\u131tulo anterior. Desta forma, se eliminarmos todas
as linhas que conte´m a varia´vel soma o que teremos e´ um programa que le\u2c6 va´rios
nu´meros do teclado ate´ que seja lido um zero. O programa na\u2dco faria nada com os
nu´meros lidos.
Usa-se uma varia´vel (soma) cujo papel e´ acumular valores, isto e´, a varia´vel e´
inicializada com um valor nulo e na seque\u2c6ncia, ela e´ atualizada para os outros valores
a` medida em que eles sa\u2dco lidos do teclado.
A inicializac¸a\u2dco do acumulador com o valor zero deve-se ao fato deste ser o elemento
6.2. DESVIOS CONDICIONAIS ANINHADOS 57
neutro da adic¸a\u2dco. Se fosse uma multiplicac¸a\u2dco de va´rios nu´meros, o acumulador deveria
ser inicializado com o elemento neutro da multiplicac¸a\u2dco, isto e´, o 1.
program soma valores ;
var
numero, soma: integer ;
begin
soma:= 0; (\u2217 inicializa o acumulador \u2217)
read (numero) ;
while numero <> 0 do
begin
soma:= soma + numero; (\u2217 atualiza o acumulador \u2217)
read (numero) ;
end;
end.
Figura 6.3: Te´cnica do acumulador.
Na figura 6.4 mostra-se como resolver o problema inicial usando a te´cnica dos
acumuladores. Notem que a soluc¸a\u2dco explora um comando de atribuic¸a\u2dco sob o escopo
de um comando de repetic¸a\u2dco.
Trocando-se o valor da constante MAX de 5 para 50, tem-se a soluc¸a\u2dco para o
problema 2. E´ fa´cil perceber que esta maneira e´ gene´rica, resolve problemas similares
para qualquer tamanho de entrada, bastando-se trocar o valor da constante MAX.
program soma valores ;
const max=5;
var
numero, i , soma: integer ;
begin
soma:= 0;
i:= 1;
while i <= max do
begin
read (numero) ;
soma:= soma + numero;
end;
end.
Figura 6.4: Soluc¸a\u2dco para o primeiro problema com acumuladores.
6.2 Desvios condicionais aninhados
O problema a seguir nos permitira´ apresentar um algoritmo que o resolve de maneira
elegante atrave´s do uso de estruturas contendo aninhamentos de desvios condicionais.
58 CAPI´TULO 6. TE´CNICAS ELEMENTARES
6.2.1 O menor de tre\u2c6s
Problema: Apo´s ler tre\u2c6s nu´meros no teclado, imprimir o menor deles.
A soluc¸a\u2dco para este problema (figura 6.5) envolve uma se´rie de tomada de deciso\u2dces
com diversos fluxos alternativos de co´digo.
Quando um comando esta´ sob o controle de outro, diz-se que o comando mais
interno esta´ sob o escopo do mais externo. Neste caso, vamos usar um desvio condici-
onal que controla outro. No jarga\u2dco dos programadores, se diz que os comandos nesta
forma esta\u2dco aninhados.
program imprime menor;
var
a, b, c : integer ;
begin
write(\u2019entre com tres numeros inteiros: \u2019) ;
read(a , b, c) ;
i f 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 b < c then
writeln (\u2019o menor dos tres eh \u2019 ,b)
else
writeln (\u2019o menor dos tres eh \u2019 ,c)
end.
Figura 6.5: Imprimir o menor dentre 3 nu´meros lidos.
6.3 Desvios condicionais dentro de repetic¸o\u2dces
Nesta sec¸a\u2dco veremos exemplos de problemas cujas soluc¸o\u2dces algor´\u131tmicas requerem o
uso de atribuic¸o\u2dces aninhadas em repetic¸o\u2dces.
6.3.1 Imprimir apenas nu´meros positivos
Neste problema estudaremos como aninhar um comando de desvio condicional dentro
do escopo de um comando de repetic¸a\u2dco. Tambe´m aproveitaremos para iniciar o estudo
sobre como pensar no problema global e nos poss´\u131veis subproblemas existentes.
Problema: Ler do teclado 30 nu´meros inteiros e imprimir na tela aqueles que sa\u2dco
6.3. DESVIOS CONDICIONAIS DENTRO DE REPETIC¸O\u2dcES 59
positivos, ignorando os negativos ou nulos.
Se o enunciado fosse simplesmente para ler e imprimir 30 nu´meros, como far´\u131amos?
Provavelmente como ilustrado na figura 6.6. Observamos que este problema e´ muito
similar a outros ja´ estudados no cap´\u131tulo anterior. Trata-se de um lac¸o que precisa de
um contador para se determinar a sa´\u131da.
program lereimprimir ;
var i , a : integer ; (\u2217 i serve para contar quantos numeros foram lidos \u2217)
begin
i := 1;
while i <= 30 do
begin
read (a) ;
writeln (a) ;
i := i + 1;
end;
end.
Figura 6.6: Lendo e imprimindo 30 nu´meros.
O problema e´ que na\u2dco queremos imprimir todos os nu´meros lidos, mas apenas
aqueles que sa\u2dco positivos: se o nu´mero lido for positivo, enta\u2dco queremos imprimir,
sena\u2dco na\u2dco. Conforme ja´ visto, o comando if faz exatamente isto, testa uma expressa\u2dco
booleana que, caso satisfeita, executa o comando subsequente, sena\u2dco o pula, passando
diretamente para o seguinte, tal como ilustrado na figura 6.7.
program lereimprimir ;
var i , a : integer ;
begin
i := 1;
while i <= 30 do
begin
read (a) ;
i f a > 0 then
writeln (a) ; (\u2217 so eh executado quando a eh positivo \u2217)
i := i + 1;
end;
end.
Figura 6.7: Lendo e imprimindo os positivos apenas.
Relembrando, o comando de desvio condicional tambe´m permite executar exclu-
sivamente uma ac¸a\u2dco alternativa, caso o teste da expressa\u2dco booleana resulte em falso.
Por exemplo, se o enunciado fosse \u201cler 30 nu´meros e imprimir os que sa\u2dco pares mas
imprimir o quadrado dos que na\u2dco sa\u2dco, incluindo o zero\u201d.
60 CAPI´TULO 6. TE´CNICAS ELEMENTARES
Do ponto de vista lo´gico, seria o mesmo que dizer o seguinte: \u201cse o nu´mero lido for
positivo, imprim\u131´-lo, caso contra´rio ele e´ zero ou negativo, enta\u2dco imprimir o quadrado
dele\u201d. Isto pode ser visto na figura 6.8. Destacamos mais uma vez que a estrutura
de controle do lac¸o na\u2dco mudou, apenas os comandos que sa\u2dco executados no lac¸o
mudaram, caracterizando-se dois subproblemas: um para controlar o lac¸o, outro para
se decidir se o nu´mero e´ positivo ou na\u2dco e o que fazer com ele.
program lereimprimir ;
var i , a : integer ;
begin
i := 1;
while i <= 30 do
begin
read (a) ;
i f a > 0 then
writeln (a) (\u2217 so eh executado quando a for positivo \u2217)
else
writeln (a\u2217a) ; (\u2217 so eh executado quando a <= 0 \u2217)
i := i + 1;
end;
end.
Figura 6.8: Lendo e imprimindo os positivos e os quadrados dos \u131´mpares.
Agora, o comando que imprime a so´ e´ executado quando a > 0. Se isto na\u2dco for
verdade, o que e´ impresso e´ o quadrado de a. Em ambos os casos o valor de i e´
incrementado.
Este u´ltimo programa pode facilmente ser modificado para se resolver o problema
de se contar quantos nu´meros lidos sa\u2dco positivos e quantos na\u2dco sa\u2dco. Basta, ao inve´s
de imprimir, contar, ou em outras palavras, acumular.
Para isto sa\u2dco necessa´rias duas varia´veis adicionais, que iniciam em