apostila
259 pág.

apostila


DisciplinaAlgoritmos e Estrutura de Dados I706 materiais7.916 seguidores
Pré-visualização50 páginas
1
e 30.000 ou entre 1 e 100.000.000, o programa ficaria com 30 mil ou 100 milho\u2dces de
linhas de co´digo extremamente repetitivo e de dif´\u131cil e custosa edic¸a\u2dco.
A simplicidade do racioc´\u131nio inicial resultou em uma tarefa ta\u2dco exaustiva que o
computador deixou de ajudar, ele passou a atrapalhar!
42 CAPI´TULO 5. CONCEITOS ELEMENTARES
Felizmente, ha´ algoritmos melhores!
O computador e´, conforme vimos, uma ma´quina com pouqu´\u131ssimos recursos, mas
que, se bem explorados, permite-nos escrever programas fanta´sticos. O racioc´\u131nio
deve ser enta\u2dco desenvolvido de tal maneira que o trabalho fique com o computador e
na\u2dco com o programador.
Primeira lic¸a\u2dco: na\u2dco e´ perda de tempo pensar mais antes de escrever co´digo!
As operac¸o\u2dces elementares da ma´quina sa\u2dco, basicamente, colocar e consultar dados
da memo´ria ou fazer contas com bastante rapidez. As operac¸o\u2dces sa\u2dco executadas uma
por uma, em ordem, visualmente de cima para baixo.
Como explorar isto? Se pelo menos consegu´\u131ssemos uma versa\u2dco em que o copi-
ar/colar fosse via´vel, ja´ ajudaria. A figura 5.6 ilustra uma soluc¸a\u2dco em que isto e´
poss´\u131vel.
program contar ;
var i : integer ;
begin
i := 1;
write ( i ) ;
i := i + 1;
write ( i ) ;
i := i + 1;
write ( i ) ;
i := i + 1;
write ( i ) ;
i := i + 1;
write ( i ) ;
i := i + 1;
end.
Figura 5.6: Segunda soluc¸a\u2dco.
A expressa\u2dco i:= 1 e´ mais um exemplo de um comando de atribuic¸a\u2dco. O resultado
da execuc¸a\u2dco do comando e´ que a expressa\u2dco a` direita do s´\u131mbolo :=, no caso o 1, e´
colocado na posic¸a\u2dco de memo´ria acessada pela varia´vel i.
A expressa\u2dco i + 1 e´ mais um exemplo de uma expressa\u2dco aritme´tica, que e´ cons-
titu´\u131da conforme as regras do compilador. Uma expressa\u2dco aritme´tica resulta em um
valor nume´rico, no caso deste exemplo do mesmo tipo da varia´vel i, que e´ integer.
Destacamos enta\u2dco que a linha de co´digo 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