apostila

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