3 5 e´ 3-alternante. Escreva um programa Pascal que verifica se uma sequeˆncia de tamanho n e´ 10-alternante. O programa deve ler n, o tamanho da sequeˆncia, no inic´ıo do programa e aceitar somente valores mu´ltiplos de 10. A sa´ıda do programa deve ser a mensagem “A sequencia eh 10-alternante” caso a sequeˆncia seja 10- alternante e “A sequencia nao eh 10-alternante”, caso contra´rio. 15. Fac¸a um programa em Pascal que calcule o resultado da seguinte se´rie: S = x0 2! − x 4 6! + x8 10! − x 12 14! + x16 18! − . . . 16. Fac¸a um programa em Pascal que receba como entrada um dado inteiro N e o imprima como um produto de primos. Exemplos: 45 = 3 × 3 × 5. 56 = 2× 2× 2× 7. 17. Fac¸a um programa em Pascal que calcule e escreva o valor de S assim definido: S = 1 1! − 2 2! + 4 3! − 8 2! + 16 1! − 32 2! + 64 3! − · · · 18. Fazer um programa em Pascal que calcule e escreva o valor de S: S = 37× 38 1 + 36× 37 2 + 35× 36 3 + · · ·+ 1× 2 37 90 CAPI´TULO 7. APLICAC¸O˜ES DAS TE´CNICAS ELEMENTARES Cap´ıtulo 8 Refinamentos sucessivos Neste ponto consideramos que o estudante ja´ domina as estruturas elementares de controle de fluxo de execuc¸a˜o de um programa, enta˜o podemos aplicar estes conceitos em alguns algoritmos mais sofisticados, isto e´, em problemas para os quais as soluc¸o˜es envolvem generalizac¸o˜es dos conteu´dos previamente ministrados. A partir de agora, vamos construir os programas passo a passo, iniciando pela apresentac¸a˜o de um pseudo-co´digo, que e´ um algoritmo de mais alto n´ıvel que nor- malmente na˜o pode ser compilado, mas pode progressivamente ser detalhado ate´ se obter o co´digo final compila´vel. Vamos tambe´m introduzir uma te´cnica de se isolar os subproblemas, de maneira a definir blocos que realizam ca´lculos bem definidos: integrando-se os diversos pedac¸os, teremos a soluc¸a˜o global do problema. Tambe´m na˜o nos preocuparemos mais com os cabec¸alhos dos programas. 8.1 Primos entre si Problema: Imprimir todos os pares de nu´meros (a, b) que sa˜o primos entre si para todo 2 ≤ a ≤ 100 e a ≤ b ≤ 100. Este problema pode ser dividido em dois sub-problemas: (1) dado um par de nu´meros quaisquer, como saber se eles sa˜o primos entre si? (2) como gerar todos os pares ordenados no intervalo desejado? Nosso conhecimento deveria ser suficiente para resolvermos o segundo sub-problema. Por este motivo vamos iniciar a tentativa de soluc¸a˜o por ele, neste ponto ignorando completamente o primeiro sub-problema. A soluc¸a˜o poderia ser tal como mostrado na figura 8.1, a qual apresenta um co´digo global que gera todos os pares ordenados que interessam, isto e´, tais que 2 ≤ a ≤ 100 e a ≤ b ≤ 100. Na parte central do pseudo-co´digo existe um desvio condicional que na˜o esta´ escrito em forma de linguagem de programac¸a˜o, mas que pode ser considerado como um teste feito atrave´s de um ora´culo que, por sua vez, sabe responder sim ou na˜o se cada par e´ ou na˜o e´ constitu´ıdo por pares de nu´meros primo entre si. 91 92 CAPI´TULO 8. REFINAMENTOS SUCESSIVOS begin i := 2; while i <= 100 do begin j:= i ; (∗ para gerar pares com j sendo maior ou igual a i ∗) while j <= 100 do begin if { i e j sao primos entre si} then writeln ( i , j ) ; (∗ oraculo ∗) j:= j + 1; end; i := i + 1; end; end. Figura 8.1: Pseudo-co´digo para o problema dos pares entre si. Agora basta transformar o ora´culo em co´digo propriamente dito. Lembramos que a e b sa˜o nu´meros primos entre si quando o ma´ximo divisor comum entre eles e´ 1. Isto e´, mdc(a, b) = 1. Na sec¸a˜o 6.4.1 vimos como se calcula de forma eficiente o MDC entre dois nu´meros pelo me´todo de Euclides (figura 6.16. A versa˜o final esta´ na figura 8.2. begin i := 2; while i <= 100 do begin j:= i ; while j <= 100 do begin a:= i ; b:= j ; (∗ inicio do bloco euclides ∗) resto:= a mod b; (∗ ∗ ∗) while resto <> 0 do (∗ ∗ ∗) begin (∗ ∗ ∗) a:= b; (∗ ∗ ∗) b:= resto ; (∗ ∗ ∗) resto:= a mod b; (∗ ∗ ∗) end; (∗ termino do bloco euclides ∗) i f b = 1 then writeln ( i , j ) ; (∗ b=1 era o oraculo ∗) j:= j + 1; end; i := i + 1; end; end. Figura 8.2: Gerando todos os primos entre si. O teste b = 1 no final do co´digo, logo apo´s o bloco que calcula o MDC por Euclides, e´ exatamente o teste que o ora´culo fazia na versa˜o anterior. A diferenc¸a entre os dois co´digos e´ exatamente o trecho inserido em destaque. 8.2. AMIGOS QUADRA´TICOS 93 8.2 Amigos quadra´ticos Neste problema poderemos explorar a busca por uma soluc¸a˜o usando va´rios n´ıveis de detalhamento, comec¸ando pelo pseudo-co´digo de mais alto n´ıvel, passando por um outro pseudo-co´digo intermedia´rio e finalmente, atrave´s de mais um passo de refinamento, obtendo o co´digo final. Problema: Dois nu´meros naturais n e m sa˜o ditos amigos quadra´ticos quando n e´ igual a soma dos d´ıgitos de m2 e ao mesmo tempo m e´ igual a soma dos d´ıgitos de n2. Imprimir todos os pares n e m que sa˜o amigos quadra´ticos no intervalo 1 ≤ 10000 ≤ n e 1 ≤ 10000 ≤ m. Por exemplo, os nu´meros 13 e 16 sa˜o amigos quadra´ticos, pois 132 = 169 e 1+6+9=16. Por outro lado, 162 = 256 e 2+5+6=13. Novamente usaremos a te´cnica de se resolver o problema por partes. Vamos iniciar gerando os pares de nu´meros dentro do intervalo desejado, conforme fizemos na sec¸a˜o anterior. Para cada par, alguns ora´culos nos auxiliara˜o na busca pela soluc¸a˜o. O pseudo-co´digo para isto esta´ na figura 8.3. begin n:= 1; while n<= 10000 do begin m:= 1; while m<= 10000 do begin if {m e n sao amigos quadraticos} then writeln(n,’ e ’ , m, ’ sao amigos quadraticos.’) ; m:= m + 1; end; n:= n + 1; end; end. Figura 8.3: Pseudo-co´digo para o problema dos amigos quadra´ticos. Agora podemos nos concentrar exclusivamente no problema de se determinar se um par de nu´meros m e n sa˜o amigos quadra´ticos. Para isto temos que resolver mais um subproblema, pois a definic¸a˜o de amigos quadra´ticos exige que a soma dos d´ıgitos de um nu´mero ao quadrado tem que ser igual a soma dos d´ıgitos do quadrado do outro nu´mero. Isto envolve decompor o quadrado de um nu´mero qualquer na soma dos d´ıgitos que o compo˜e. Isto pode ser feito como na figura 8.4. Finalmente temos um terceiro subproblema: como podemos separar os d´ıgitos de um nu´mero inteiro qualquer dado, para depois soma´-los? A te´cnica usada explora a operac¸a˜o aritme´tica de se pegar o resto da divisa˜o inteira por 10. Vejamos um exemplo para o nu´mero 169. 94 CAPI´TULO 8. REFINAMENTOS SUCESSIVOS begin {dados n e m} soma n:= {oraculo que soma os digitos de n} ; soma m:= {oraculo que soma os digitos de m} ; i f soma n = soma m then {sao amigos quadraticos} end. Figura 8.4: Pseudo-co´digo para decidir sobre amigos quadra´ticos. 169 div 10 9 16 div 10 6 1 div 10 1 0 No exemplo acima o nu´mero 169 foi sucessivamente dividido por 10 ate´ virar zero. Os restos das diviso˜es por 10 nos da˜o os d´ıgitos do 169, a saber, 9, 6 e 1, obtidos nesta ordem. Isto esta´ implementado conforme ilustrado na figura 8.5. begin {dado n inteiro} while n <> 0 do begin digito:= n mod 10; n:= n div 10; end; end. Figura 8.5: Separando os d´ıgitos de um dado nu´mero n. A varia´vel digito conte´m, a cada iterac¸a˜o, um d´ıgito que faz parte do nu´mero dado. Para se obter a soma, basta usar a te´cnica do acumulador, conforme a figura 8.6. begin {dado N inteiro} soma:= 0; while N<> 0 do begin digito:= N mod 10; soma:= soma + digito ; N:= N div 10; end; end. Figura 8.6: Somando os d´ıgitos de um dado nu´mero n. Por u´ltimo, na˜o resta mais nada a na˜o ser juntar os diversos pedac¸os de co´digo em um u´nico programa que executa a tarefa com sucesso. Isto e´ mostrado na figura 8.7. O leitor deve estudar atentamente a maneira como os