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
(\u2217 decompoe n ao quadrado \u2217)
n2:= n\u2217n;
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;
(\u2217 decompoe m ao quadrado \u2217)
m2:= m\u2217m;
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,\u2019 e \u2019 , m, \u2019 sao amigos quadraticos.\u2019) ;
m:= m + 1;
end;
n:= n + 1;
end;
end.
Figura 8.7: Verificando se nu´meros n e m sa\u2dco amigos quadra´ticos.
96 CAPI´TULO 8. REFINAMENTOS SUCESSIVOS
E´ poss´\u131vel contudo fazer menos ca´lculos e economizar um lac¸o, reduzindo de um
milha\u2dco para mil operac¸o\u2dces se, para cada n, testarmos se a soma dos seus d´\u131gitos ao
quadrado pode ser transformado novamente em n. Veja o algoritmo da figura 8.8 e
compare com a versa\u2dco anterior.
program amigosquad;
var n, m, n2, m2, soma dig n2 , soma dig m2, unidade : integer ;
begin
n:= 1;
while n<= 10000 do
begin
(\u2217 decompoe n ao quadrado \u2217)
n2:= n\u2217n;
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 (\u2217 se estiver na faixa permitida \u2217)
begin
(\u2217 decompoe soma dig n2 \u2217)
m2:= m\u2217m;
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,\u2019 e \u2019 , m, \u2019 sao amigos quadraticos.\u2019) ;
end;
n:= n + 1;
end;
end.
Figura 8.8: Tornando amigos quadra´ticos mais eficiente.
8.3 Pal´\u131ndromos
Este problema, e o da sec¸a\u2dco seguinte, nos permitira´ entender melhor a te´cnica usada
na sec¸a\u2dco anterior, a de se decompor um nu´mero qualquer na seque\u2c6ncia de d´\u131gitos que
o compo\u2dce 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\u2dco gerados ao inve´s de lidos do teclado. Esta e´ a diferenc¸a
ba´sica.
Problema: Imprimir todos os nu´meros pal´\u131ndromos entre 1 e 1000.
Nu´meros pal´\u131ndromos sa\u2dco aqueles que sa\u2dco lidos da direita para a esquerda da
mesma maneira que da esquerda para a direita. Por exemplo o nu´mero 12321 e´
pal´\u131ndromo, enquanto que 123 na\u2dco e´.
O algoritmo apresentado na figura 8.9 mostra a soluc¸a\u2dco, que exige um aninhamento
duplo de comandos de repetic¸a\u2dco e um teste dentro de um deles. Ele testa todos os
nu´meros e imprime quando sa\u2dco pal´\u131ndromos.
Para testar se um nu´mero e´ pal´\u131ndromo usamos a seguinte te´cnica: separamos
os d´\u131gitos do nu´mero em questa\u2dco, em seguida reconstru´\u131mos 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\u2dces sucessivas por 10
invertendo-se os d´\u131gitos, assim:
do × 10n + d1 × 10n\u22121 + d2 × 10n\u22122 + . . .+ dn × 100
const max=1000;
begin
i := 1;
while i <= max do (\u2217 laco que controla os numeros entre 1 e max \u2217)
begin
invertido:= 0; (\u2217 inicializa aculumador \u2217)
n:= i ;
while n <> 0 do
begin
invertido:= invertido\u221710 + n mod 10;
n:= n div 10;
end;
(\u2217 imprime se for palindromo, senao nao faz nada \u2217)
i f invertido = i then
writeln ( i ) ;
i := i + 1;
end;
end.
Figura 8.9: Imprimindo todos os pal´\u131ndromos de 1 a 1000.
98 CAPI´TULO 8. REFINAMENTOS SUCESSIVOS
Testar pal´\u131ndromos pode ser muito caro dependendo da aplicac¸a\u2dco. Em todo caso,
apresentamos um problema no m\u131´nimo divertido, que e´ o de gerar os pal´\u131ndromos,
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´\u131veis
de aninhamentos de comandos de repetic¸a\u2dco.
Problema: Gerar todos os nu´meros pal´\u131ndromos entre 1 e 1000.
O algoritmo apresentado na figura 8.10 conte´m a soluc¸a\u2dco para este problema. Ele
tem por base o formato dos pal´\u131ndromos, gerando todos os de um d´\u131gito, depois todos
os de dois d´\u131gitos e finalmente todos os de 3 d´\u131gitos. Um exerc´\u131cio interessante seria
generalizar este co´digo, mas deixamos isto como exerc´\u131cio.
begin
i := 1; (\u2217 gerando todos de um digito \u2217)
while i <= 9 do
begin
writeln ( i ) ;
i := i + 1;
end;
pal:= 11; (\u2217 gerando todos de 2 digitos \u2217)
i := 2;
while i <= 10 do
begin
writeln (pal) ;
pal:= i \u2217 11;
i := i + 1;
end;
i := 1; (\u2217 gerando todos os de 3 digitos \u2217)
while i <= 9 do
begin
j:= 0;
while j <= 9 do
begin
pal:= i\u2217100 + j\u221710 + i ;
writeln (pal) ;
j:= j + 1;
end;
i := i + 1;
end;
end.
Figura 8.10: Gerando todos os pal´\u131ndromos de 1 a 1000.
8.4. INVERTER UM NU´MERO DE TRE\u2c6S DI´GITOS 99
8.4 Inverter um nu´mero de tre\u2c6s d´\u131gitos
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\u2dces para o mesmo problema
de maneira a evoluirmos na compreensa\u2dco da arte de se construir algoritmos.
Problema: Ler um nu´mero de 3 d´\u131gitos do teclado e imprimir este nu´mero invertido.
Exemplo, se a entrada for \u201c123\u201d (cento e vinte e tre\u2c6s) a sa´\u131da deve ser \u201c321\u201d (trezentos
e vinte e um).
A primeira soluc¸a\u2dco, 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\u2dco leva, quase que necessariamente, a dificuldades imensas na
reimplementac¸a\u2dco do co´digo para problemas similares.
begin
write(\u2019entre com o numero de tres digitos: \u2019) ;
readln(numero) ;
centena:= numero div 100;
dezena:= (numero mod 100) div 10;
unidade:= numero mod 10;
inverso := unidade\u2217100 + dezena\u221710 + centena ;
writeln( inverso) ;
end.
Figura 8.11: Primeira soluc¸a\u2dco para inverter um nu´mero de 3 d´\u131gitos.
Os estudantes propuseram esta soluc¸a\u2dco por considerarem que o ser humano faz
mais ou menos do mesmo modo, isto e´, ele separa os d´\u131gitos mentalmente lendo o
nu´mero de tra´s para frente ao mesmo tempo que os escreve na ordem desejada.
A soluc¸a\u2dco enta\u2dco parte do princ´\u131pio de, primeiro separar o nu´mero dado na entrada
em tre\u2c6s d´\u131gitos para, depois, imprimi-los na ordem inversa. Assim, os operadores
de divisa\u2dco e resto de divisa\u2dco inteira sa\u2dco utilizados para a separac¸a\u2dco 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´\u131gitos. Se fosse pedido para resolver o mesmo problema para
um nu´mero de 4 d´\u131gitos, enta\u2dco a implementac¸a\u2dco do mesmo me´todo implicaria na total
reconstruc¸a\u2dco 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\u2dco parecida, o que na\u2dco e´
verdade.
O co´digo da figura 8.12 ilustra a adaptac¸a\u2dco desta mesma ideia, desta vez para 4
d´\u131gitos.
Ale´m de ter que declarar mais uma varia´vel (milhar), houve alterac¸a\u2dco de prati-
camente todas as linhas do co´digo. Aparentemente, separar a unidade e o primeiro
d´\u131gito (no caso o milhar) e´ fa´cil, bastando uma divisa\u2dco inteira por 10 e um resto de
divisa\u2dco inteira por 10. Mas calcular a dezena e a centena comec¸a a ficar complicado.
E´ poss´\u131vel imaginar o estrago no co´digo se for exigido que a entrada seja cons-
titu´\u131da de 10 d´\u131gitos ou mais, o que nos permite perceber claramente a dificuldade na
100 CAPI´TULO 8. REFINAMENTOS SUCESSIVOS
begin
write(\u2019entre com o numero de quatro digitos: \u2019) ;
readln(numero) ;
milhar:= numero div 1000;
centena:= (numero mod 1000) div 100;
dezena:= (numero mod 100) div 10;
unidade:= numero mod 10;
inverso := unidade\u22171000