apostila

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