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