Pré-visualização50 páginas
3 5 e´ 3-alternante. Escreva um programa Pascal que verifica se uma seque\u2c6ncia de tamanho n e´ 10-alternante. O programa deve ler n, o tamanho da seque\u2c6ncia, no inic´\u131o do programa e aceitar somente valores mu´ltiplos de 10. A sa´\u131da do programa deve ser a mensagem \u201cA sequencia eh 10-alternante\u201d caso a seque\u2c6ncia seja 10- alternante e \u201cA sequencia nao eh 10-alternante\u201d, caso contra´rio. 15. Fac¸a um programa em Pascal que calcule o resultado da seguinte se´rie: S = x0 2! \u2212 x 4 6! + x8 10! \u2212 x 12 14! + x16 18! \u2212 . . . 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! \u2212 2 2! + 4 3! \u2212 8 2! + 16 1! \u2212 32 2! + 64 3! \u2212 · · · 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\u2dcES DAS TE´CNICAS ELEMENTARES Cap´\u131tulo 8 Refinamentos sucessivos Neste ponto consideramos que o estudante ja´ domina as estruturas elementares de controle de fluxo de execuc¸a\u2dco de um programa, enta\u2dco podemos aplicar estes conceitos em alguns algoritmos mais sofisticados, isto e´, em problemas para os quais as soluc¸o\u2dces envolvem generalizac¸o\u2dces dos conteu´dos previamente ministrados. A partir de agora, vamos construir os programas passo a passo, iniciando pela apresentac¸a\u2dco de um pseudo-co´digo, que e´ um algoritmo de mais alto n´\u131vel que nor- malmente na\u2dco 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\u2dco global do problema. Tambe´m na\u2dco 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\u2dco primos entre si para todo 2 \u2264 a \u2264 100 e a \u2264 b \u2264 100. Este problema pode ser dividido em dois sub-problemas: (1) dado um par de nu´meros quaisquer, como saber se eles sa\u2dco 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\u2dco por ele, neste ponto ignorando completamente o primeiro sub-problema. A soluc¸a\u2dco 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 \u2264 a \u2264 100 e a \u2264 b \u2264 100. Na parte central do pseudo-co´digo existe um desvio condicional que na\u2dco esta´ escrito em forma de linguagem de programac¸a\u2dco, mas que pode ser considerado como um teste feito atrave´s de um ora´culo que, por sua vez, sabe responder sim ou na\u2dco se cada par e´ ou na\u2dco e´ constitu´\u131do 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 ; (\u2217 para gerar pares com j sendo maior ou igual a i \u2217) while j <= 100 do begin if { i e j sao primos entre si} then writeln ( i , j ) ; (\u2217 oraculo \u2217) 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\u2dco nu´meros primos entre si quando o ma´ximo divisor comum entre eles e´ 1. Isto e´, mdc(a, b) = 1. Na sec¸a\u2dco 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\u2dco 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 ; (\u2217 inicio do bloco euclides \u2217) resto:= a mod b; (\u2217 \u2217 \u2217) while resto <> 0 do (\u2217 \u2217 \u2217) begin (\u2217 \u2217 \u2217) a:= b; (\u2217 \u2217 \u2217) b:= resto ; (\u2217 \u2217 \u2217) resto:= a mod b; (\u2217 \u2217 \u2217) end; (\u2217 termino do bloco euclides \u2217) i f b = 1 then writeln ( i , j ) ; (\u2217 b=1 era o oraculo \u2217) 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\u2dco 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\u2dco usando va´rios n´\u131veis de detalhamento, comec¸ando pelo pseudo-co´digo de mais alto n´\u131vel, 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\u2dco ditos amigos quadra´ticos quando n e´ igual a soma dos d´\u131gitos de m2 e ao mesmo tempo m e´ igual a soma dos d´\u131gitos de n2. Imprimir todos os pares n e m que sa\u2dco amigos quadra´ticos no intervalo 1 \u2264 10000 \u2264 n e 1 \u2264 10000 \u2264 m. Por exemplo, os nu´meros 13 e 16 sa\u2dco 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\u2dco anterior. Para cada par, alguns ora´culos nos auxiliara\u2dco na busca pela soluc¸a\u2dco. 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,\u2019 e \u2019 , m, \u2019 sao amigos quadraticos.\u2019) ; 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\u2dco amigos quadra´ticos. Para isto temos que resolver mais um subproblema, pois a definic¸a\u2dco de amigos quadra´ticos exige que a soma dos d´\u131gitos de um nu´mero ao quadrado tem que ser igual a soma dos d´\u131gitos do quadrado do outro nu´mero. Isto envolve decompor o quadrado de um nu´mero qualquer na soma dos d´\u131gitos que o compo\u2dce. Isto pode ser feito como na figura 8.4. Finalmente temos um terceiro subproblema: como podemos separar os d´\u131gitos de um nu´mero inteiro qualquer dado, para depois soma´-los? A te´cnica usada explora a operac¸a\u2dco aritme´tica de se pegar o resto da divisa\u2dco 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\u2dces por 10 nos da\u2dco os d´\u131gitos 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´\u131gitos de um dado nu´mero n. A varia´vel digito conte´m, a cada iterac¸a\u2dco, um d´\u131gito 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´\u131gitos de um dado nu´mero n. Por u´ltimo, na\u2dco resta mais nada a na\u2dco 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