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