apostila

primo, justamente se o nu´mero for o 2. No caso dos \u131´mpares e´ necessa´rio que
todos sejam testados. A figura 7.12 ilustra o programa que implementa este racioc´\u131nio.
O algoritmo testa inicialmente se o nu´mero e´ par. Se for, testa se e´ o 2, que e´
primo. Se for \u131´mpar, testa todos os \u131´mpares entre 1 e n \u2212 1, eliminando metade dos
ca´lculos, pois os pares foram descartados.
Melhorou, mas pode melhorar mais com um pouco mais de observac¸a\u2dco: na\u2dco e´
necessa´rio se testar todos os \u131´mpares, basta que se teste ate´ a raiz no nu´mero.
De fato, todo nu´mero natural pode ser decomposto como um produto de nu´meros
primos. Se a entrada na\u2dco for um primo, enta\u2dco pode ser decomposta, no melhor caso,
assim: n = p \u2217 p, em que p e´ primo. O algoritmo que implementa esta soluc¸a\u2dco e´
mostrado na figura 7.13.
Para se ter uma ideia do ganho, vejam na tabela seguinte o quanto se ganha com
as tre\u2c6s u´ltimas verso\u2dces do programa.
x x
2
\u221a
x
1000000 500000 1000
1000000000 500000000 31622
1000000000000 500000000000 1000000
A tabela acima mostra que para entradas da ordem de 1012, o nu´mero de ca´lculos
feitos com o programa da figura 7.11 pode ser da mesma ordem de 1012. Os ca´lculos
do programa da figura 7.12 pode ser da ordem de 1011 (ganho pequeno), enquanto
que na u´ltima versa\u2dco, ele pode fazer ca´lculos da ordem de \u201capenas\u201d 106.
7.4. NU´MEROS PRIMOS 85
begin
read (n) ;
eh primo:= true ; (\u2217 inicia chutando que n eh primo \u2217)
i f n mod 2 = 0 then (\u2217 n eh par \u2217)
i f n <> 2 then
eh primo:= false (\u2217 n nao eh 2 \u2217)
else eh primo:= true
else (\u2217 n nao eh par , testar todos os impares \u2217)
begin
i := 3;
while ( i <= n\u22121) and eh primo do
begin
if n mod i = 0 then
eh primo:= false ; (\u2217 achamos um divisor impar \u2217)
i := i + 2;
end;
end;
i f eh primo then
writeln (n,\u2019 eh primo\u2019)
end.
Figura 7.12: Testa se n e´ primo, tratando os pares em separado.
begin
read (n) ;
eh primo:= true ; (\u2217 inicia chutando que n eh primo \u2217)
i f n mod 2 = 0 then (\u2217 n eh par \u2217)
i f n <> 2 then
eh primo:= false (\u2217 n nao eh 2 \u2217)
else eh primo:= true
else begin (\u2217 n nao eh par , testar todos os impares \u2217)
i := 3;
while ( i <= trunc(sqrt(n))) and eh primo do
begin
if n mod i = 0 then
eh primo:= false ; (\u2217 achamos um divisor impar \u2217)
i := i + 2;
end;
end;
i f eh primo then
writeln (n,\u2019 eh primo\u2019)
end.
Figura 7.13: Testa se n e´ primo parando na raiz de n.
86 CAPI´TULO 7. APLICAC¸O\u2dcES DAS TE´CNICAS ELEMENTARES
7.5 Exerc´\u131cios
1. Dado um nu´mero de tre\u2c6s d´\u131gitos, construir outro nu´mero de quatro d´\u131gitos com a
seguinte regra: a) os tre\u2c6s primeiros d´\u131gitos, contados da esquerda para a direita,
sa\u2dco iguais aos do nu´mero dado; b) o quarto d´\u131gito e\u2019 um d´\u131gito de controle
calculado da seguinte forma: primeiro d´\u131gito + 3*segundo d´\u131gito + 5*terceiro
d´\u131gito; o d´\u131gito de controle e´ igual ao resto da divisa\u2dco dessa soma por 7.
2. Dado um nu´mero inteiro de cinco d´\u131gitos representando um nu´mero bina´rio,
determinar seu valor equivalente em decimal. Por exemplo, se a entrada for
10001, a sa´\u131da deve ser 17.
3. Considere o programa feito para resoluc¸a\u2dco do ca´lculo do nu´mero neperiano
(sec¸a\u2dco 7.3.1. Quantas operac¸o\u2dces de multiplicac¸a\u2dco sao executadas no seu pro-
grama?
(a) Considerando 20 termos.
(b) Considerando N termos.
4. Considere a progressa\u2dco geome´trica 1, 2, 4, 8, 16, 32, ... e um inteiro positivo N.
Imprimir os N primeiros termos desta PG e a soma deles.
5. Imprimir os N primeiros termos das seque\u2c6ncias definidas pelas relac¸o\u2dces de re-
corre\u2c6ncia:
(a) Y (k + 1) = Y (k) + k, k = 1, 2, 3..., Y (1) = 1
(b) Y (k + 1) = Y (k) + (2k + 1), k = 0, 1, 2, 3..., Y (0) = 1
(c) Y (k + 1) = Y (k) + (3k2 + 3k + 1), k = 0, 1, 2, 3..., Y (0) = 1
(d) Y (k + 1) = 2Y (k), k = 1, 2, 3..., Y (1) = 1
6. Dado um nu´mero inteiro N , tabelar N [k] para k variando de 1 ate´ N . Considere
que, por definic¸a\u2dco, X[k] = X(X \u2212 1)(X \u2212 2)(X \u2212 3)...(X \u2212 k + 1), X sendo
um nu´mero real, k um natural diferente de zero e X[0] = 1. Observe que se
X = N = k, enta\u2dco N [N ] = N !.
7. Sabe-se que o valor do coseno de 1 (um) radiano pode ser calculado pela se´rie
infinita abaixo:
coseno(x) =
1
0!
\u2212 x
2
2!
+
x4
4!
\u2212 x
6
6!
+ . . .
Fazer um programa que calcule o valor do cosseno de x obtido pela se´rie acima
considerando apenas os primeiros 14 termos da mesma.
7.5. EXERCI´CIOS 87
8. Considere o conjunto C de todos os nu´meros inteiros com quatro algarismos
distintos, ordenados segundo seus valores, em ordem crescente:
C = {1023, 1024, 1025, 1026, 1027, 1028, 1029, 1032, 1034, 1035, . . . }
Fac¸a um programa em Pascal que leia um nu´mero N , pertencente a este con-
junto, e imprima a posic¸a\u2dco deste nu´mero no conjunto.
Exemplos:
\u2022 Entrada: 1026
Sa´\u131da: 4
\u2022 Entrada: 1034
Sa´\u131da: 9
\u2022 Entrada: 9876
Sa´\u131da: 4536
\u2022 Entrada: 1243
Sa´\u131da: 72
9. Fac¸a um programa em Pascal que calcule e imprima o valor de f(x), onde x \u2208 <
e´ lido no teclado e:
f(x) =
5x
2!
\u2212 6x
2
3!
+
11x3
4!
\u2212 12x
4
5!
+
17x5
6!
\u2212 18x
6
7!
+ . . .
O ca´lculo deve parar quando abs(f(xn+1)\u2212 f(xn)) < 0.00000001, onde abs(x) e´
a func¸a\u2dco em Pascal que retorna o valor absoluto de x.
10. O nu´mero a´ureo \u3d5 (1,6180339...) pode ser calculado atrave´s de expresso\u2dces com
se´ries de frac¸o\u2dces sucessivas do tipo:
\u3d51 = 1 +
1
1
= 2
\u3d52 = 1 +
1
1 + 1
1
= 1, 5
\u3d53 = 1 +
1
1 + 1
1+ 1
1
= 1, 666
\u3d54 = 1 +
1
1 + 1
1+ 1
1+11
= 1, 6
onde \u3d5i indica a aproximac¸a\u2dco do nu´mero a´ureo com i frac¸o\u2dces sucessivas. Estes
valores variam em torno do nu´mero a´ureo, sendo maior ou menor alternada-
mente, mas sempre se aproximando deste quando o nu´mero de frac¸o\u2dces cresce.
Fac¸a um programa em Pascal que leia um nu´mero N e imprima o valor da
aproximac¸a\u2dco do nu´mero a´ureo \u3d5N , que usa uma se´rie de N frac¸o\u2dces sucessivas.
11. Dado um inteiro positivo N e dada uma seque\u2c6ncia de N nu´meros reais x1, . . . , xn
fac¸a um programa em Pascal que calcule o quociente da soma dos reais pelo seu
produto. Isto e´:
q =
\u2211N
i=1 xi\u220fN
i=1 xi
88 CAPI´TULO 7. APLICAC¸O\u2dcES DAS TE´CNICAS ELEMENTARES
Como na\u2dco pode haver divisa\u2dco por zero, seu programa deve parar ta\u2dco logo esta
situac¸a\u2dco seja verificada indicando uma mensagem apropriada para o usua´rio.
12. Em Pascal o tipo CHAR e´ enumera´vel, e portanto esta´ na classe dos tipos
chamados de ordinais, conforme o guia de refere\u2c6ncia da linguagem estudado em
aula. A ordem de cada caracter e´ dada pela tabela ASCII. Assim e´ poss´\u131vel, por
exemplo, escrever trechos de co´dico tais como:
IF \u2019A\u2019 > \u2019B\u2019 THEN
WRITE (\u2019A eh maior que B\u2019)
ELSE
WRITE (\u2019A n~ao eh maior que B\u2019);
que produziria a mensagem \u201cA na\u2dco eh maior que B\u201d, pois na tabela ASCII o
s´\u131mbolo \u201cA\u201d tem ordem 64 enquanto que \u201cB\u201d tem ordem 65.
Ou ainda:
FOR i:= \u2019a\u2019 TO \u2019z\u2019 DO
WRITE (i);
que produziria como sa´\u131da \u201cabcdefghijklmnopqrstuvxwyz\u201d.
Fac¸a um programa em Pascal que leia seu nome completo (nomes completos em
geral) constitu´\u131dos por apenas letras maiu´sculas entre \u201cA\u201d e \u201cZ\u201d e espac¸os em
branco terminadas em \u201c.\u201d e que retorne o nu´mero de vogais e consoantes neste
nome. Exemplos:
Entrada: FABIANO SILVA.
Sa\u131´da:
Vogais: 6
Consoantes: 6
Entrada: MARCOS ALEXANDRE CASTILHO.
Sa\u131´da:
Vogais: 9
Consoantes: 14
13. Fac¸a um programa em Pascal que leia um inteiro positivo n, e escreva a soma
dos n primeiros termos da se´rie:
1000
1
\u2212 997
2
+
994
3
\u2212 991
4
+ . . .
7.5. EXERCI´CIOS 89
14. Dizemos que uma seque\u2c6ncia de inteiros e´ k-alternante se for composta alterna-
damente por segmentos de nu´meros pares de tamanho k e segmentos de nu´meros
\u131´mpares de tamanho k.
Exemplos:
A seque\u2c6ncia 1 3 6 8 9 11 2 4 1 7 6 8 e´ 2-alternante.
A seque\u2c6ncia 2 1 4 7 8 9 12 e´ 1-alternante.
A seque\u2c6ncia 1