apostila
259 pág.

apostila


DisciplinaAlgoritmos e Estrutura de Dados I706 materiais7.917 seguidores
Pré-visualização50 páginas
+ dezena\u2217100 + centena\u221710 + milhar ;
writeln( inverso) ;
end.
Figura 8.12: Mesmo algoritmo, agora para 4 d´\u131gitos.
adaptac¸a\u2dco da soluc¸a\u2dco ao mesmo tempo em que se percebe que, para o computador,
nem sempre e´ fa´cil resolver problemas da mesma maneira como o ser humano faria.
Novamente, e´ preciso deixar que o computador fac¸a o trabalho, na\u2dco o programador.
Se este u´ltimo for esperto o suficiente, fara´ um co´digo baseado num algoritmo mais
elaborado. Provavelmente o algoritmo na\u2dco sera´ mais ta\u2dco intuitivo, mas se for bem
feito, vai nos permitir generalizar o co´digo para entradas de qualquer tamanho.
O que queremos aqui, assim como no problema da sec¸a\u2dco anterior, e´ tentar perceber
algum racioc´\u131nio que possa ser repetido um nu´mero controlado de vezes. Deve-se
tentar explorar uma mesma seque\u2c6ncia de operac¸o\u2dces, que consiste em separar o u´ltimo
d´\u131gito e remover do nu´mero original este d´\u131gito que foi separado.
Desta forma, a construc¸a\u2dco da resposta na\u2dco pode mais ser feita apenas no final do
algoritmo. A` medida que o nu´mero original vai sendo separado, o seu inverso ja´ deve
ir sendo constru´\u131do, tal como foi feito nas duas sec¸o\u2dces anteriores. O co´digo final e´
apresentado na figura 8.13.
begin
write(\u2019entre com o numero de tres digitos: \u2019) ;
readln(numero) ;
inverso := 0;
i:= 1;
while ( i <= 3) do
begin
unidade := numero mod 10;
resto := numero div 10;
inverso := inverso\u221710 + unidade ;
numero := resto ;
i := i + 1;
end;
writeln( inverso) ;
end.
Figura 8.13: Soluc¸a\u2dco com uso de acumuladores.
8.5. CA´LCULO DO MDC PELA DEFINIC¸A\u2dcO 101
8.5 Ca´lculo do MDC pela definic¸a\u2dco
Nesta sec¸a\u2dco apresentaremos a soluc¸a\u2dco do problema do MDC calculado pela definic¸a\u2dco.
O objetivo e´ motivar o cap´\u131tulo seguinte, uma vez que sabemos que existe um algo-
ritmo melhor, estudado na sec¸a\u2dco 6.16.
O MDC entre dois inteiros a e b foi definido matematicamente na sec¸a\u2dco 6.4.1 e
envolve a fatorac¸a\u2dco de ambas as entradas como um produto de nu´meros primos. O
algoritmo ba´sico, em pseudo-co´digo e´ apresentado na figura 8.14.
begin
read (a ,b) ;
mdc:= 1;
(\u2217 descobre quantas vezes o 2 divide as duas entradas \u2217)
cont a:= {numero de vezes que o 2 divide a} ;
cont b:= {numero de vezes que o 2 divide b} ;
menor cont:= {menor entre cont a e cont b} ;
mdc:= mdc \u2217 {2 elevado a potencia menor cont} ;
a:= a div mdc;
b:= b div mdc;
(\u2217 repete o processo para todos os impares \u2217)
primo:= 3;
while (a <> 1) and (b <> 1) do
begin
cont a:= {numero de vezes que primo divide a}
cont b:= {numero de vezes que primo divide b}
menor cont:= {menor entre cont a e cont b} ;
mdc:= mdc \u2217 {primo elevado a potencia menor cont} ;
a:= a div mdc;
b:= b div mdc;
primo:= primo + 2; (\u2217 passa para o proximo impar \u2217)
end;
writeln (mdc) ;
end.
Figura 8.14: Pseudo-co´digo para o calculo do MDC pela definic¸a\u2dco.
O princ´\u131pio do algoritmo e´ verificar quantas vezes cada nu´mero primo divide as
entradas e descobrir qual deles e´ o menor. O MDC e´ atualizado enta\u2dco para menor
pote\u2c6ncia deste primo. E´ preciso separar o caso do 2 dos outros, por motivos que ja´
discutimos. Os valores de a e de b sa\u2dco atualizados, para na\u2dco haver ca´lculos inu´teis
com os \u131´mpares mu´ltiplos de primos que ja´ foram previamente processados.
O programa que implementa este algoritmo na\u2dco cabe em uma pa´gina, por isto e´
apresentado em duas partes nas figuras 8.15 e 8.16.
Neste ponto deixamos claro ao leitor o motivo da apresentac¸a\u2dco deste problema
no final deste cap´\u131tulo: este co´digo tem um n´\u131vel muito alto de trechos de co´digo
bastante parecidos. Observamos que, em quatro vezes, se calcula quantas vezes um
102 CAPI´TULO 8. REFINAMENTOS SUCESSIVOS
dado primo p divide um nu´mero n. Ainda, a atualizac¸a\u2dco do MDC tambe´m aparece
em dois trechos diferentes mas bastante similares.
O reaproveitamento de co´digo e´ uma das motivac¸o\u2dces para o uso de subprogramas
nas linguagens de alto n´\u131vel. Mas na\u2dco e´ a u´nica, existem outras motivac¸o\u2dces. No
pro´ximo cap´\u131tulo vamos introduzir as importantes noc¸o\u2dces de procedure e function em
Pascal, e poderemos reescrever o co´digo acima com muito mais elega\u2c6ncia.
begin
(\u2217 inicializacao das variaveis principais \u2217)
read (a ,b) ;
mdc:= 1;
(\u2217 descobre quantas vezes o 2 divide as duas entradas \u2217)
cont a:= 0;
while a mod 2 = 0 do
begin
cont a:= cont a + 1;
a:= a div 2;
end;
cont b:= 0;
while b mod 2 = 0 do
begin
cont b:= cont b + 1;
b:= b div 2;
end;
(\u2217 descobre qual dos contadores eh o menor \u2217)
i f cont a <= cont b then
menor cont:= cont a
else
menor cont:= cont b ;
(\u2217 atualiza o mdc para o 2 \u2217)
i := 1;
while i <= menor cont do
begin
mdc:= mdc \u2217 2;
i := i + 1;
end;
Figura 8.15: Calcula MDC entre a e b pela definic¸a\u2dco (caso primo=2).
8.5. CA´LCULO DO MDC PELA DEFINIC¸A\u2dcO 103
(\u2217 repete o processo para todos os impares \u2217)
primo:= 3;
while (a <> 1) and (b <> 1) do
begin
cont a:= 0;
while a mod primo = 0 do
begin
cont a:= cont a + 1;
a:= a div primo;
end;
cont b:= 0;
while b mod primo = 0 do
begin
cont b:= cont b + 1;
b:= b div primo;
end;
(\u2217 descobre qual dos contadores eh o menor \u2217)
i f cont a <= cont b then
menor cont:= cont a
else
menor cont:= cont b ;
(\u2217 atualiza o mdc para o primo impar da vez \u2217)
i := 1;
while i <= menor cont do
begin
mdc:= mdc \u2217 primo;
i:= i + 1;
end;
(\u2217 passa para o proximo impar \u2217)
primo:= primo + 2;
end;
(\u2217 imprime o resultado final \u2217)
writeln (mdc) ;
end.
Figura 8.16: Calcula MDC entre a e b pela definic¸a\u2dco (caso primo e´ \u131´mpar).
104 CAPI´TULO 8. REFINAMENTOS SUCESSIVOS
8.6 Exerc´\u131cios
1. Fazer um programa em Pascal que leia do teclado dois nu´meros inteiros posi-
tivos e que imprima na sa´\u131da um u´nico nu´mero inteiro que e´ a soma dos dois
primeiros. Entretanto, seu programa na\u2dco pode utilizar o operador de soma (+)
da linguagem Pascal para somar os dois inteiros lidos em uma u´nica operac¸a\u2dco.
Outrossim, o programa deve implementar a soma dos nu´meros d´\u131gito a d´\u131gito,
iniciando pelo menos significativo ate´ o mais significativo, considerando o \u201cvai
um\u201d, conforme costumamos fazer manualmente desde o ensino fundamental.
Exemplo 1 Exemplo 2
11 (&quot;vai um&quot;) 1111 (&quot;vai um&quot;)
40912 (primeiro nu´mero) 52986 (primeiro nu´mero)
1093 (segundo nu´mero) 1058021 (segundo nu´mero)
----- -------
42005 (soma) 1111007 (soma)
2. Um agricultor possui 1 (uma) espiga de milho. Cada espiga tem 150 gra\u2dcos, e cada
gra\u2dco pesa 1g (um grama). Escreva um programa em Pascal para determinar
quantos anos sera\u2dco necessa´rios para que o agricultor colha mais de cem toneladas
de milho (1T = 1000Kg, 1Kg = 1000g), sendo que:
\u2022 A cada ano ele planta todos os gra\u2dcos da colheita anterior
\u2022 Ha´ apenas uma colheita por ano
\u2022 10% (dez por cento) dos gra\u2dcos na\u2dco germina (morre sem produzir)
\u2022 Cada gra\u2dco que germina produz duas espigas de milho
Assuma que a quantidade de terra dispon´\u131vel e´ sempre suficiente para o plantio.
3. Modifique a questa\u2dco anterior acrescentando na simulac¸a\u2dco os seguintes fatos:
\u2022 Ha´ 8 (oito) CASAIS de pombas (16 pombas) que moram na propriedade
do agricultor.
\u2022 Cada pomba come 30 gra\u2dcos por dia, durante os 30 dias do ano em que as
espigas esta\u2dco formadas antes da colheita;
\u2022 A cada ano, cada casal gera 2 novos casais (4 pombas), que se alimentara\u2dco
e reproduzira\u2dco no ano seguinte;
\u2022 Uma pomba vive tres anos;
Ao final do programa, imprima tambe´m o nu´mero de pombas que vivem na
propriedade quando o agricultor colher mais de 100T de milho
8.6. EXERCI´CIOS 105
4. Considere um nu´mero inteiro com 9 d´\u131gitos. Suponha que o u´ltimo d´\u131gito seja
o \u201cd´\u131gito verificador\u201d do nu´mero formado pelos 8 primeiros. Fac¸a um programa
em Pascal que leia uma massa de dados terminada por 0 (zero) e que imprima os
nu´meros que na\u2dco sa\u2dco bem formados, isto e´, aqueles que na\u2dco satisfazem