apostila

diversos co´digos foram integrados.
8.2. AMIGOS QUADRA´TICOS 95
begin
n:= 1;
while n<= 10000 do
begin
m:= 1;
while m<= 10000 do
begin
(∗ decompoe n ao quadrado ∗)
n2:= n∗n;
soma dig n2:= 0;
while n2 <> 0 do
begin
digito:= n2 mod 10;
soma dig n2:= soma dig n2 + digito ;
n2:= n2 div 10;
end;
(∗ decompoe m ao quadrado ∗)
m2:= m∗m;
soma dig m2:= 0;
while m2<> 0 do
begin
digito:= m2 mod 10;
soma dig m2:= soma dig m2 + digito ;
m2:= m2 div 10;
end;
i f (soma dig n2 = m) and (soma dig m2 = n) then
writeln(n,’ e ’ , m, ’ sao amigos quadraticos.’) ;
m:= m + 1;
end;
n:= n + 1;
end;
end.
Figura 8.7: Verificando se nu´meros n e m sa˜o amigos quadra´ticos.
96 CAPI´TULO 8. REFINAMENTOS SUCESSIVOS
E´ poss´ıvel contudo fazer menos ca´lculos e economizar um lac¸o, reduzindo de um
milha˜o para mil operac¸o˜es se, para cada n, testarmos se a soma dos seus d´ıgitos ao
quadrado pode ser transformado novamente em n. Veja o algoritmo da figura 8.8 e
compare com a versa˜o anterior.
program amigosquad;
var n, m, n2, m2, soma dig n2 , soma dig m2, unidade : integer ;
begin
n:= 1;
while n<= 10000 do
begin
(∗ decompoe n ao quadrado ∗)
n2:= n∗n;
soma dig n2:= 0;
while n2 <> 0 do
begin
unidade:= n2 mod 10;
soma dig n2:= soma dig n2 + unidade ;
n2:= n2 div 10;
end;
m:= soma dig n2 ;
i f soma dig n2 <= 1000 then (∗ se estiver na faixa permitida ∗)
begin
(∗ decompoe soma dig n2 ∗)
m2:= m∗m;
soma dig m2:= 0;
while m2<> 0 do
begin
unidade:= m2 mod 10;
soma dig m2:= soma dig m2 + unidade ;
m2:= m2 div 10;
end;
i f soma dig m2 = n then
writeln(n,’ e ’ , m, ’ sao amigos quadraticos.’) ;
end;
n:= n + 1;
end;
end.
Figura 8.8: Tornando amigos quadra´ticos mais eficiente.
8.3 Pal´ındromos
Este problema, e o da sec¸a˜o seguinte, nos permitira´ entender melhor a te´cnica usada
na sec¸a˜o anterior, a de se decompor um nu´mero qualquer na sequeˆncia de d´ıgitos que
o compo˜e para depois poder fazer algum ca´lculo com eles. A ideia e´ que os dados
8.3. PALI´NDROMOS 97
de ca´lculo do programa sa˜o gerados ao inve´s de lidos do teclado. Esta e´ a diferenc¸a
ba´sica.
Problema: Imprimir todos os nu´meros pal´ındromos entre 1 e 1000.
Nu´meros pal´ındromos sa˜o aqueles que sa˜o lidos da direita para a esquerda da
mesma maneira que da esquerda para a direita. Por exemplo o nu´mero 12321 e´
pal´ındromo, enquanto que 123 na˜o e´.
O algoritmo apresentado na figura 8.9 mostra a soluc¸a˜o, que exige um aninhamento
duplo de comandos de repetic¸a˜o e um teste dentro de um deles. Ele testa todos os
nu´meros e imprime quando sa˜o pal´ındromos.
Para testar se um nu´mero e´ pal´ındromo usamos a seguinte te´cnica: separamos
os d´ıgitos do nu´mero em questa˜o, em seguida reconstru´ımos o nu´mero ao contra´rio,
usando a te´cnica do acumulador, e finalmente comparamos com o nu´mero original.
Lembrando que um nu´mero da forma d0d1d2 . . . dn e´ escrito da seguinte forma:
do × 100 + d1 × 101 + d2 × 102 + . . .+ dn × 10n
Para gerar o nu´mero ao contra´rio basta fazer multiplicac¸o˜es sucessivas por 10
invertendo-se os d´ıgitos, assim:
do × 10n + d1 × 10n−1 + d2 × 10n−2 + . . .+ dn × 100
const max=1000;
begin
i := 1;
while i <= max do (∗ laco que controla os numeros entre 1 e max ∗)
begin
invertido:= 0; (∗ inicializa aculumador ∗)
n:= i ;
while n <> 0 do
begin
invertido:= invertido∗10 + n mod 10;
n:= n div 10;
end;
(∗ imprime se for palindromo, senao nao faz nada ∗)
i f invertido = i then
writeln ( i ) ;
i := i + 1;
end;
end.
Figura 8.9: Imprimindo todos os pal´ındromos de 1 a 1000.
98 CAPI´TULO 8. REFINAMENTOS SUCESSIVOS
Testar pal´ındromos pode ser muito caro dependendo da aplicac¸a˜o. Em todo caso,
apresentamos um problema no mı´nimo divertido, que e´ o de gerar os pal´ındromos,
assim evitando que todos os nu´meros sejam testados. De qualquer forma, este pro-
blema serve para o estudante perceber melhor o uso de contadores em diversos n´ıveis
de aninhamentos de comandos de repetic¸a˜o.
Problema: Gerar todos os nu´meros pal´ındromos entre 1 e 1000.
O algoritmo apresentado na figura 8.10 conte´m a soluc¸a˜o para este problema. Ele
tem por base o formato dos pal´ındromos, gerando todos os de um d´ıgito, depois todos
os de dois d´ıgitos e finalmente todos os de 3 d´ıgitos. Um exerc´ıcio interessante seria
generalizar este co´digo, mas deixamos isto como exerc´ıcio.
begin
i := 1; (∗ gerando todos de um digito ∗)
while i <= 9 do
begin
writeln ( i ) ;
i := i + 1;
end;
pal:= 11; (∗ gerando todos de 2 digitos ∗)
i := 2;
while i <= 10 do
begin
writeln (pal) ;
pal:= i ∗ 11;
i := i + 1;
end;
i := 1; (∗ gerando todos os de 3 digitos ∗)
while i <= 9 do
begin
j:= 0;
while j <= 9 do
begin
pal:= i∗100 + j∗10 + i ;
writeln (pal) ;
j:= j + 1;
end;
i := i + 1;
end;
end.
Figura 8.10: Gerando todos os pal´ındromos de 1 a 1000.
8.4. INVERTER UM NU´MERO DE TREˆS DI´GITOS 99
8.4 Inverter um nu´mero de treˆs d´ıgitos
O pro´ximo problema vai nos permitir reforc¸ar o uso da te´cnica do acumulador ao
mesmo tempo em que continuamos a mostrar va´rias soluc¸o˜es para o mesmo problema
de maneira a evoluirmos na compreensa˜o da arte de se construir algoritmos.
Problema: Ler um nu´mero de 3 d´ıgitos do teclado e imprimir este nu´mero invertido.
Exemplo, se a entrada for “123” (cento e vinte e treˆs) a sa´ıda deve ser “321” (trezentos
e vinte e um).
A primeira soluc¸a˜o, apresentada na figura 8.11, foi feita pelos alunos em sala
de aula em um curso no segundo semestre de 2002. E´ um bom exemplo de como
particularizar a soluc¸a˜o leva, quase que necessariamente, a dificuldades imensas na
reimplementac¸a˜o do co´digo para problemas similares.
begin
write(’entre com o numero de tres digitos: ’) ;
readln(numero) ;
centena:= numero div 100;
dezena:= (numero mod 100) div 10;
unidade:= numero mod 10;
inverso := unidade∗100 + dezena∗10 + centena ;
writeln( inverso) ;
end.
Figura 8.11: Primeira soluc¸a˜o para inverter um nu´mero de 3 d´ıgitos.
Os estudantes propuseram esta soluc¸a˜o por considerarem que o ser humano faz
mais ou menos do mesmo modo, isto e´, ele separa os d´ıgitos mentalmente lendo o
nu´mero de tra´s para frente ao mesmo tempo que os escreve na ordem desejada.
A soluc¸a˜o enta˜o parte do princ´ıpio de, primeiro separar o nu´mero dado na entrada
em treˆs d´ıgitos para, depois, imprimi-los na ordem inversa. Assim, os operadores
de divisa˜o e resto de divisa˜o inteira sa˜o utilizados para a separac¸a˜o dos nu´meros em
unidade, dezena e centena.
O programa funciona, e´ verdade, mas tem um grave problema. Ele so´ funciona
para nu´meros com 3 d´ıgitos. Se fosse pedido para resolver o mesmo problema para
um nu´mero de 4 d´ıgitos, enta˜o a implementac¸a˜o do mesmo me´todo implicaria na total
reconstruc¸a˜o do co´digo acima. Isto e´, e´ como se tive´ssemos um novo problema para
ser resolvido e nunca tive´ssemos pensado em nenhuma soluc¸a˜o parecida, o que na˜o e´
verdade.
O co´digo da figura 8.12 ilustra a adaptac¸a˜o desta mesma ideia, desta vez para 4
d´ıgitos.
Ale´m de ter que declarar mais uma varia´vel (milhar), houve alterac¸a˜o de prati-
camente todas as linhas do co´digo. Aparentemente, separar a unidade e o primeiro
d´ıgito (no caso o milhar) e´ fa´cil, bastando uma divisa˜o inteira por 10 e um resto de
divisa˜o inteira por 10. Mas calcular a dezena e a centena comec¸a a ficar complicado.
E´ poss´ıvel imaginar o estrago no co´digo se for exigido que a entrada seja cons-
titu´ıda de 10 d´ıgitos ou mais, o que nos permite perceber claramente a dificuldade na
100 CAPI´TULO 8. REFINAMENTOS SUCESSIVOS
begin
write(’entre com o numero de quatro digitos: ’) ;
readln(numero) ;
milhar:= numero div 1000;
centena:= (numero mod 1000) div 100;
dezena:= (numero mod 100) div 10;
unidade:= numero mod 10;
inverso := unidade∗1000