apostila
259 pág.

apostila

Disciplina:Algoritmos e Estrutura de Dados I542 materiais7.956 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˜es de
linhas de co´digo extremamente repetitivo e de dif´ıcil e custosa edic¸a˜o.

A simplicidade do racioc´ınio inicial resultou em uma tarefa ta˜o 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´ıssimos recursos, mas

que, se bem explorados, permite-nos escrever programas fanta´sticos. O racioc´ınio
deve ser enta˜o desenvolvido de tal maneira que o trabalho fique com o computador e
na˜o com o programador.

Primeira lic¸a˜o: na˜o e´ perda de tempo pensar mais antes de escrever co´digo!
As operac¸o˜es elementares da ma´quina sa˜o, basicamente, colocar e consultar dados

da memo´ria ou fazer contas com bastante rapidez. As operac¸o˜es sa˜o executadas uma
por uma, em ordem, visualmente de cima para baixo.

Como explorar isto? Se pelo menos consegu´ıssemos uma versa˜o em que o copi-
ar/colar fosse via´vel, ja´ ajudaria. A figura 5.6 ilustra uma soluc¸a˜o em que isto e´
poss´ıvel.

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˜o.

A expressa˜o i:= 1 e´ mais um exemplo de um comando de atribuic¸a˜o. O resultado
da execuc¸a˜o do comando e´ que a expressa˜o a` direita do s´ımbolo :=, no caso o 1, e´
colocado na posic¸a˜o de memo´ria acessada pela varia´vel i.

A expressa˜o i + 1 e´ mais um exemplo de uma expressa˜o aritme´tica, que e´ cons-
titu´ıda conforme as regras do compilador. Uma expressa˜o aritme´tica resulta em um
valor nume´rico, no caso deste exemplo do mesmo tipo da varia´vel i, que e´ integer.

Destacamos enta˜o que a linha de co´digo contendo i:= i + 1 tambe´m e´ uma atri-
buic¸a˜o e funciona assim: resolve-se o valor da expressa˜o a` direita do s´ımbolo :=, 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˜o da varia´vel
que aparece a` esquerda do s´ımbolo :=, casualmente a pro´pria varia´vel i, que passa a
ter o valor 2.

5.4. IMPRIMINDO SEQUEˆNCIAS 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˜o usa-se o comando de impressa˜o 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˜o do valor
5 e sendo 6 o u´ltimo valor (na˜o impresso) da varia´vel i.

O programa foi feito de maneira a ter blocos de comandos repetidos, pois ainda
na˜o sabemos mudar o fluxo de execuc¸a˜o de um programa, isto e´, ele executa “de cima
para baixo”, enta˜o a soluc¸a˜o foi repetir os mesmos blocos 5 vezes.

E´ poss´ıvel forc¸ar a mudanc¸a do fluxo de execuc¸a˜o do programa? O que precisamos
e´ de uma estrutura que permita repetir um determinado trecho de co´digo enquanto
uma determinada condic¸a˜o for verdadeira.

Isto e´ conseguido com o uso de comandos de repetic¸a˜o. A linguagem Pascal oferece
treˆs 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˜o.

O comando de repetic¸a˜o executa os comandos aninhados no bloco entre o begin e
o end; enquanto uma expressa˜o booleana for verdadeira. No primeiro momento em
que for falsa, o fluxo e´ alterado para depois do end.

A expressa˜o i ≤ 30000 e´ uma expressa˜o booleana, retorna verdadeiro ou falso
apenas, dependendo da avaliac¸a˜o 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˜o e incremento sa˜o 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˜o 2 e´ impresso e i passa a valer 3, que por sua vez ainda e´ menor ou
igual a 30000. Enta˜o 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˜o e´ menor ou igual a 30000, por isto o fluxo de execuc¸a˜o do programa
vai para o comando que segue o bloco do comando while, isto e´, o fim do programa.

Nesta sec¸a˜o mostramos o conceito de comando de repetic¸a˜o (while/do) e um exem-
plo de uso de uma expresso˜es booleanas. A pro´xima sec¸a˜o 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 ≤ x ≤ 30.

O programa que ilustra a soluc¸a˜o para este problema e´ apresentado na figura 5.8
e imprime todos os valores inteiros de 1 a 30. Observamos que o enunciado na˜o deixa
claro, mas na˜o seria poss´ıvel imprimir todos os reais. Seria?

program quadrados ;
var i : integer ;

begin
i := 1;
while i <= 30 do
begin

write ( i ,’ ’ , i∗ 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˜o 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˜o 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˜o 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˜o deve ser resolvida: quantos pares de nu´meros sera˜o dados
como entrada? O enunciado diz “va´rios pares”, mas na˜o estabelece o nu´mero preciso.
Algoritmos na˜o sabem lidar com isto. Fazendo uma analogia com o problema do bolo
de chocolate, e´ como se o enunciado fosse “fazer um bolo”. O cozinheiro na˜o sabe que
tipo de bolo esta´ sendo solicitado e na˜o consegue realizar a tarefa.

E´ necessa´rio estabelecer uma condic¸a˜o 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

• ou o enunciado estabelece a quantidade exata de nu´meros a serem lidos;
• ou o enunciado estabelece uma condic¸a˜o de parada alternativa.
No primeiro caso o enunciado deveria ser algo assim: “ler 30 pares de nu´meros do

teclado e imprimir, para cada par, a soma deles”.
No segundo caso poderia ser algo mais ou menos assim: “ler pares de nu´meros do

teclado e imprimir, para cada par, a soma deles. O algoritmo deve parar a execuc¸a˜o
quando os dois nu´meros lidos forem iguais a zero”.

A figura 5.9 ilustra as duas formas. A esquerda apresenta a soluc¸a˜o usando-se um
contador, a da direita apresenta a soluc¸a˜o com crite´rio de parada alternativo.

program soma2variasvezes v1 ;
var a,b, cont : integer ;
(∗ cont conta os numeros lidos ∗)
begin

cont:= 1;
while cont <= 30 do
begin

read (a) ;
read (b) ;
writeln (a+b) ;
cont:= cont + 1;

end;
end.

program soma2variasvezes