apostila

+ dezena∗100 + centena∗10 + milhar ;
writeln( inverso) ;
end.
Figura 8.12: Mesmo algoritmo, agora para 4 d´ıgitos.
adaptac¸a˜o da soluc¸a˜o 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˜o o programador.
Se este u´ltimo for esperto o suficiente, fara´ um co´digo baseado num algoritmo mais
elaborado. Provavelmente o algoritmo na˜o sera´ mais ta˜o 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˜o anterior, e´ tentar perceber
algum racioc´ınio que possa ser repetido um nu´mero controlado de vezes. Deve-se
tentar explorar uma mesma sequeˆncia de operac¸o˜es, que consiste em separar o u´ltimo
d´ıgito e remover do nu´mero original este d´ıgito que foi separado.
Desta forma, a construc¸a˜o da resposta na˜o 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´ıdo, tal como foi feito nas duas sec¸o˜es anteriores. O co´digo final e´
apresentado na figura 8.13.
begin
write(’entre com o numero de tres digitos: ’) ;
readln(numero) ;
inverso := 0;
i:= 1;
while ( i <= 3) do
begin
unidade := numero mod 10;
resto := numero div 10;
inverso := inverso∗10 + unidade ;
numero := resto ;
i := i + 1;
end;
writeln( inverso) ;
end.
Figura 8.13: Soluc¸a˜o com uso de acumuladores.
8.5. CA´LCULO DO MDC PELA DEFINIC¸A˜O 101
8.5 Ca´lculo do MDC pela definic¸a˜o
Nesta sec¸a˜o apresentaremos a soluc¸a˜o do problema do MDC calculado pela definic¸a˜o.
O objetivo e´ motivar o cap´ıtulo seguinte, uma vez que sabemos que existe um algo-
ritmo melhor, estudado na sec¸a˜o 6.16.
O MDC entre dois inteiros a e b foi definido matematicamente na sec¸a˜o 6.4.1 e
envolve a fatorac¸a˜o 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;
(∗ descobre quantas vezes o 2 divide as duas entradas ∗)
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 ∗ {2 elevado a potencia menor cont} ;
a:= a div mdc;
b:= b div mdc;
(∗ repete o processo para todos os impares ∗)
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 ∗ {primo elevado a potencia menor cont} ;
a:= a div mdc;
b:= b div mdc;
primo:= primo + 2; (∗ passa para o proximo impar ∗)
end;
writeln (mdc) ;
end.
Figura 8.14: Pseudo-co´digo para o calculo do MDC pela definic¸a˜o.
O princ´ıpio 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˜o para menor
poteˆncia deste primo. E´ preciso separar o caso do 2 dos outros, por motivos que ja´
discutimos. Os valores de a e de b sa˜o atualizados, para na˜o haver ca´lculos inu´teis
com os ı´mpares mu´ltiplos de primos que ja´ foram previamente processados.
O programa que implementa este algoritmo na˜o 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˜o deste problema
no final deste cap´ıtulo: este co´digo tem um n´ıvel 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˜o do MDC tambe´m aparece
em dois trechos diferentes mas bastante similares.
O reaproveitamento de co´digo e´ uma das motivac¸o˜es para o uso de subprogramas
nas linguagens de alto n´ıvel. Mas na˜o e´ a u´nica, existem outras motivac¸o˜es. No
pro´ximo cap´ıtulo vamos introduzir as importantes noc¸o˜es de procedure e function em
Pascal, e poderemos reescrever o co´digo acima com muito mais elegaˆncia.
begin
(∗ inicializacao das variaveis principais ∗)
read (a ,b) ;
mdc:= 1;
(∗ descobre quantas vezes o 2 divide as duas entradas ∗)
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;
(∗ descobre qual dos contadores eh o menor ∗)
i f cont a <= cont b then
menor cont:= cont a
else
menor cont:= cont b ;
(∗ atualiza o mdc para o 2 ∗)
i := 1;
while i <= menor cont do
begin
mdc:= mdc ∗ 2;
i := i + 1;
end;
Figura 8.15: Calcula MDC entre a e b pela definic¸a˜o (caso primo=2).
8.5. CA´LCULO DO MDC PELA DEFINIC¸A˜O 103
(∗ repete o processo para todos os impares ∗)
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;
(∗ descobre qual dos contadores eh o menor ∗)
i f cont a <= cont b then
menor cont:= cont a
else
menor cont:= cont b ;
(∗ atualiza o mdc para o primo impar da vez ∗)
i := 1;
while i <= menor cont do
begin
mdc:= mdc ∗ primo;
i:= i + 1;
end;
(∗ passa para o proximo impar ∗)
primo:= primo + 2;
end;
(∗ imprime o resultado final ∗)
writeln (mdc) ;
end.
Figura 8.16: Calcula MDC entre a e b pela definic¸a˜o (caso primo e´ ı´mpar).
104 CAPI´TULO 8. REFINAMENTOS SUCESSIVOS
8.6 Exerc´ıcios
1. Fazer um programa em Pascal que leia do teclado dois nu´meros inteiros posi-
tivos e que imprima na sa´ıda um u´nico nu´mero inteiro que e´ a soma dos dois
primeiros. Entretanto, seu programa na˜o pode utilizar o operador de soma (+)
da linguagem Pascal para somar os dois inteiros lidos em uma u´nica operac¸a˜o.
Outrossim, o programa deve implementar a soma dos nu´meros d´ıgito a d´ıgito,
iniciando pelo menos significativo ate´ o mais significativo, considerando o “vai
um”, conforme costumamos fazer manualmente desde o ensino fundamental.
Exemplo 1 Exemplo 2
11 ("vai um") 1111 ("vai um")
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˜os, e cada
gra˜o pesa 1g (um grama). Escreva um programa em Pascal para determinar
quantos anos sera˜o necessa´rios para que o agricultor colha mais de cem toneladas
de milho (1T = 1000Kg, 1Kg = 1000g), sendo que:
• A cada ano ele planta todos os gra˜os da colheita anterior
• Ha´ apenas uma colheita por ano
• 10% (dez por cento) dos gra˜os na˜o germina (morre sem produzir)
• Cada gra˜o que germina produz duas espigas de milho
Assuma que a quantidade de terra dispon´ıvel e´ sempre suficiente para o plantio.
3. Modifique a questa˜o anterior acrescentando na simulac¸a˜o os seguintes fatos:
• Ha´ 8 (oito) CASAIS de pombas (16 pombas) que moram na propriedade
do agricultor.
• Cada pomba come 30 gra˜os por dia, durante os 30 dias do ano em que as
espigas esta˜o formadas antes da colheita;
• A cada ano, cada casal gera 2 novos casais (4 pombas), que se alimentara˜o
e reproduzira˜o no ano seguinte;
• 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´ıgitos. Suponha que o u´ltimo d´ıgito seja
o “d´ıgito verificador” 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˜o sa˜o bem formados, isto e´, aqueles que na˜o satisfazem