ALGORITMOS E ESTRUTURAS DE DADOS I
259 pág.

ALGORITMOS E ESTRUTURAS DE DADOS I


DisciplinaAlgoritmos e Estrutura de Dados I717 materiais7.910 seguidores
Pré-visualização50 páginas
contendo i:= i + 1 tambe´m e´ uma atri-
buic¸a\u2dco e funciona assim: resolve-se o valor da expressa\u2dco a` direita do s´\u131mbolo :=, isto e´,
o valor da varia´vel i, que na primeira vez e´ 1, e´ somando com a constante 1, resultando
no nu´mero 2. Em seguida, este valor por sua vez e´ colocado na posic¸a\u2dco da varia´vel
que aparece a` esquerda do s´\u131mbolo :=, casualmente a pro´pria varia´vel i, que passa a
ter o valor 2.
5.4. IMPRIMINDO SEQUE\u2c6NCIAS DE NU´MEROS NA TELA 43
O que ocorre e´ que uma certa varia´vel i e´ iniciada com o valor 1 e sucessivamente
enta\u2dco usa-se o comando de impressa\u2dco para exibir o valor de i na tela, incrementando-
se de 1 em 1 o valor da varia´vel, obtendo-se como resultado final a impressa\u2dco do valor
5 e sendo 6 o u´ltimo valor (na\u2dco impresso) da varia´vel i.
O programa foi feito de maneira a ter blocos de comandos repetidos, pois ainda
na\u2dco sabemos mudar o fluxo de execuc¸a\u2dco de um programa, isto e´, ele executa \u201cde cima
para baixo\u201d, enta\u2dco a soluc¸a\u2dco foi repetir os mesmos blocos 5 vezes.
E´ poss´\u131vel forc¸ar a mudanc¸a do fluxo de execuc¸a\u2dco do programa? O que precisamos
e´ de uma estrutura que permita repetir um determinado trecho de co´digo enquanto
uma determinada condic¸a\u2dco for verdadeira.
Isto e´ conseguido com o uso de comandos de repetic¸a\u2dco. A linguagem Pascal oferece
tre\u2c6s maneiras de se fazer isto. Veremos apenas uma delas por enquanto. No decorrer
do curso voltaremos a`s outras formas. A figura 5.7 ilustra o uso deste conceito.
program contar ;
var i : integer ;
begin
i := 1;
while i <= 30000 do
begin
write ( i ) ;
i := i + 1;
end;
end.
Figura 5.7: Sexta soluc¸a\u2dco.
O comando de repetic¸a\u2dco executa os comandos aninhados no bloco entre o begin e
o end; enquanto uma expressa\u2dco booleana for verdadeira. No primeiro momento em
que for falsa, o fluxo e´ alterado para depois do end.
A expressa\u2dco i \u2264 30000 e´ uma expressa\u2dco booleana, retorna verdadeiro ou falso
apenas, dependendo da avaliac¸a\u2dco dos valores pelo computador. No caso, vai resultar
falso apenas quando i for estritamente maior do que 30000.
Neste exemplo, a varia´vel i foi inicializada com o valor 1. Em seguida, os comandos
de impressa\u2dco e incremento sa\u2dco executados enquanto o valor de i for menor ou igual a
30000. Desta forma, o nu´mero 1 e´ impresso, i passa a valer 2, que e´ menor ou igual
a 30000, enta\u2dco 2 e´ impresso e i passa a valer 3, que por sua vez ainda e´ menor ou
igual a 30000. Enta\u2dco 3 e´ impresso na tela e i passa a valer 4, e assim por diante, ate´
o momento em que sera´ impresso na tela o valor 30000. Neste ponto i passara´ a valer
30001, que na\u2dco e´ menor ou igual a 30000, por isto o fluxo de execuc¸a\u2dco do programa
vai para o comando que segue o bloco do comando while, isto e´, o fim do programa.
Nesta sec¸a\u2dco mostramos o conceito de comando de repetic¸a\u2dco (while/do) e um exem-
plo de uso de uma expresso\u2dces booleanas. A pro´xima sec¸a\u2dco apresentara´ a u´ltima es-
trutura ba´sica que nos interessa.
44 CAPI´TULO 5. CONCEITOS ELEMENTARES
5.5 Imprimir os quadrados de uma faixa de nu´meros
Ainda no contexto de problemas simples, este outro problema nos permite combinar as
te´cnicas usadas nos problemas anteriores e resolver algo ligeiramente mais complicado.
Problema: Imprimir uma tabela com os valores de x e x2 para todos os valores de x
tais que 1 \u2264 x \u2264 30.
O programa que ilustra a soluc¸a\u2dco para este problema e´ apresentado na figura 5.8
e imprime todos os valores inteiros de 1 a 30. Observamos que o enunciado na\u2dco deixa
claro, mas na\u2dco seria poss´\u131vel imprimir todos os reais. Seria?
program quadrados ;
var i : integer ;
begin
i := 1;
while i <= 30 do
begin
write ( i ,\u2019 \u2019 , i\u2217 i ) ;
i := i + 1;
end;
end.
Figura 5.8: Tabela com os quadrados dos nu´meros de 1 a 30.
O programa inicia com o valor de i igual a 1 e para cada valor entre 1 e 30 imprime
na tela o pro´prio valor, seguido de um espac¸o em branco e finalmente o quadrado do
nu´mero, calculado pela expressa\u2dco aritme´tica i*i, que significa i× i.
5.6 Imprimindo a soma de va´rios pares de nu´meros
Problema: Ler va´rios pares de nu´meros e imprimir a soma de cada par.
Este e´ uma variante do problema da sec¸a\u2dco 5.3. Naquele caso um u´nico par de
nu´mero era lido do teclado e a soma deles impressa. Agora temos que fazer a mesma
coisa para va´rios pares de nu´meros dados como entrada.
A soluc¸a\u2dco para um u´nico par ja´ estando feita, basta que o programa repita o
mesmo trecho de co´digo va´rias vezes, usando o comando while/do.
Apenas uma questa\u2dco deve ser resolvida: quantos pares de nu´meros sera\u2dco dados
como entrada? O enunciado diz \u201cva´rios pares\u201d, mas na\u2dco estabelece o nu´mero preciso.
Algoritmos na\u2dco sabem lidar com isto. Fazendo uma analogia com o problema do bolo
de chocolate, e´ como se o enunciado fosse \u201cfazer um bolo\u201d. O cozinheiro na\u2dco sabe que
tipo de bolo esta´ sendo solicitado e na\u2dco consegue realizar a tarefa.
E´ necessa´rio estabelecer uma condic¸a\u2dco de parada e isto deve estar claro no enun-
ciado. Existem duas formas de se resolver isto:
5.7. TESTAR SE UM NU´MERO LIDO E´ POSITIVO 45
\u2022 ou o enunciado estabelece a quantidade exata de nu´meros a serem lidos;
\u2022 ou o enunciado estabelece uma condic¸a\u2dco de parada alternativa.
No primeiro caso o enunciado deveria ser algo assim: \u201cler 30 pares de nu´meros do
teclado e imprimir, para cada par, a soma deles\u201d.
No segundo caso poderia ser algo mais ou menos assim: \u201cler pares de nu´meros do
teclado e imprimir, para cada par, a soma deles. O algoritmo deve parar a execuc¸a\u2dco
quando os dois nu´meros lidos forem iguais a zero\u201d.
A figura 5.9 ilustra as duas formas. A esquerda apresenta a soluc¸a\u2dco usando-se um
contador, a da direita apresenta a soluc¸a\u2dco com crite´rio de parada alternativo.
program soma2variasvezes v1 ;
var a,b, cont : integer ;
(\u2217 cont conta os numeros lidos \u2217)
begin
cont:= 1;
while cont <= 30 do
begin
read (a) ;
read (b) ;
writeln (a+b) ;
cont:= cont + 1;
end;
end.
program soma2variasvezes v2 ;
var a,b: integer ;
begin
read (a) ;
read (b) ;
while (a <> 0) or (b <> 0) do
begin
writeln (a+b) ;
read (a) ;
read (b) ;
end;
end.
Figura 5.9: Duas formas para somar pares de nu´meros.
Este exemplo e´ extremamente interessante pois permite ver claramente que o
co´digo referente aos comandos de leitura e impressa\u2dco sa\u2dco os mesmos, apesar da ordem
diferente no segundo exemplo. O que difere e´ a estrutura de controle do lac¸o, isto
e´, do bloco de comandos que se repete. No quadro da esquerda, o algoritmo precisa
contar ate´ 30, por isto existe uma varia´vel cont que faz esta conta. No quadro da
direita, o lac¸o e´ controlado por uma expressa\u2dco booleana um pouco mais sofisticada
que a do exemplo anterior, pois faz uso do operador or. A expressa\u2dco em questa\u2dco se
torna falsa apenas quando ambos os nu´meros lidos forem nulos. Se um dois dois for
na\u2dco nulo, o lac¸o e´ executado.
O comando de impressa\u2dco ficou aparentemente invertido pela simples raza\u2dco de que
o teste depende de uma primeira leitura das varia´veis a e b antes do teste, sena\u2dco o
teste na\u2dco pode ser feito. Mas, ressaltamos, o nu´cleo do programa e´ exatamente o
mesmo, le\u2c6 dois nu´meros e imprime a soma, o que muda e´ o controle do lac¸o.
5.7 Testar se um nu´mero lido e´ positivo
Problema: Ler um u´nico nu´mero do teclado e imprim\u131´-lo apenas se ele for positivo.
Parece simples para o ser humano saber se um nu´mero e´ positivo ou na\u2dco, mas
46 CAPI´TULO 5. CONCEITOS ELEMENTARES
para o computador o que esta´ em memo´ria e´ apenas uma seque\u2c6ncia de bits. Logo,
para ele decidir se um nu´mero e´ positivo deve usar uma expressa\u2dco booleana. Mas,
como executar o comando de impressa\u2dco apenas em um caso (do nu´mero ser positivo)
e ignorar a impressa\u2dco caso na\u2dco seja? Este problema permitira´ introduzir a noc¸a\u2dco de
desvio condicional.
Um desvio condicional produz exatamente o efeito desejado, faz um teste e depen-
dendo do resultado executa ou na\u2dco o comando subsequente. A figura 5.10 ilustra a
soluc¸a\u2dco deste problema. No caso, o comando writeln so´ e´ executado se a expressa\u2dco