apostila

um valor
previamente estabelecido, isto e´, uma precisa˜o previamente determinada. Em alguns
casos, quando o ca´lculo da se´rie na˜o e´ convergente, este valor mı´nimo nunca e´ atingido,
80 CAPI´TULO 7. APLICAC¸O˜ES DAS TE´CNICAS ELEMENTARES
obrigando tambe´m o programa a testar um nu´mero ma´ximo de iterac¸o˜es. Segue a
mesma ideia discutida no caso de gerar o nu´mero a´ureo.
Suponhamos que o enunciado tivesse como condic¸a˜o de parada um destes dois
crite´rios: ou o erro e´ menor do que 10−7 ou o nu´mero ma´ximo de iterac¸o˜es e´ 50.
Se o programa sair pelo crite´rio de erro, enta˜o o valor de e foi encontrado, sena˜o,
se saiu pelo crite´rio do nu´mero ma´ximo de iterac¸o˜es, enta˜o o programa avisa que
na˜o conseguiu encontrar a soluc¸a˜o. A figura 7.6 ilustra a soluc¸a˜o para este caso. E´
importante observar que o que muda com relac¸a˜o a` primeira soluc¸a˜o e´ apenas o crite´rio
de parada. Os ca´lculos internos sa˜o os mesmos.
const itmax=50; precisao=0.0001;
begin
e:= 0;
eanterior:= −1;
fat:= 1;
i := 1;
while ( i <= itmax) and (e − eanterior > precisao) do
begin
novotermo:= 1/fat ;
eanterior:= e ;
e:= e + novotermo;
fat:= i∗fat ;
i := i + 1;
end;
i f i >= itmax then
writeln (’solucao nao encontrada’)
else
writeln (’e= ’ ,e) ;
end.
Figura 7.6: Ca´lculo do nu´mero neperiano.
7.3.2 Ca´lculo do seno
Problema: Calcular o valor de seno(x) pela se´rie abaixo, considerando apenas os
vinte primeiros termos:
seno(x) =
x
1!
− x
3
3!
+
x5
5!
− x
7
7!
+
x9
9!
− x
11
11!
+
x13
13!
− x
15
15!
+ . . .
Comparando esta se´rie com a do nu´mero neperiano, observamos treˆs diferenc¸as
ba´sicas: a primeira e´ o sinal, que a cada termo muda de positivo para negativo e vice-
e-versa e antes era sempre positivo; a segunda e´ o numerador, que antes era a constante
1, agora e´ uma poteˆncia de x; a terceira e´ que os fatoriais na˜o sa˜o consecutivos em
cada termo, aumentam de dois em dois.
7.3. SE´RIES 81
Trataremos de cada caso separadamente, construindo a soluc¸a˜o para o seno base-
ada na do nu´mero neperiano. Vamos tratar primeiro o mais simples, que e´ a questa˜o
dos sinais. Considere a seguinte se´rie:
tmp =
1
0!
− 1
1!
+
1
2!
− 1
3!
+
1
4!
− 1
5!
+
1
6!
− 1
7!
+ . . .
O algoritmo da figura 7.7 modifica o anterior pela introduc¸a˜o de uma nova varia´vel
que controla a mudanc¸a do sinal, produzindo como sa´ıda o ca´lculo da func¸a˜o tmp.
const itmax=20;
begin
seno:= 0;
fat:= 1;
sinal:= 1;
i := 1;
while i <= itmax do
begin
novotermo:= 1/fat ;
seno:= seno + sinal∗novotermo;
sinal:= −sinal ; (∗ nova variavel para sinal trocado ∗)
fat:= i∗fat ;
i := i + 1;
end;
writeln (’tmp= ’ ,seno) ;
end.
Figura 7.7: Se´rie com troca de sinais.
Agora vamos corrigir o denominador, obtendo a seguinte se´rie:
tmp2 =
1
1!
− 1
3!
+
1
5!
− 1
7!
+
1
9!
− 1
11!
+
1
13!
− 1
15!
+ . . .
A atualizac¸a˜o da varia´vel fat deve ser modificada, conforme apontado na fi-
gura 7.8:
Agora so´ resta a atualizac¸a˜o correta do numerador, que depende da leitura de um
valor x do teclado. Uma varia´vel adicional conte´m o valor de x2, para evitar ca´lculos
redundantes. O programa ilustrado na figura 7.9 implementa corretamente o ca´lculo
do seno(x) para um x dado em radianos.
Existem va´rias outras se´ries que podem ser implementadas com estas mesmas
ideias, vamos deixar isto como exerc´ıcio. Basicamente, basta o estudante observar
como os numeradores e denominadores podem ser atualizados em func¸a˜o do termo
anteriormente calculado.
82 CAPI´TULO 7. APLICAC¸O˜ES DAS TE´CNICAS ELEMENTARES
const itmax=20;
begin
seno:= 0;
fat:= 1;
sinal:= 1;
i := 1;
while i <= itmax do
begin
novotermo:= 1/fat ;
seno:= seno + sinal∗novotermo;
fat:= 2∗ i∗(2∗ i+1)∗fat ; (∗ esta eh a princial modificacao ∗)
sinal:= −sinal ;
i := i + 1;
end;
writeln (’tmp2= ’ ,seno) ;
end.
Figura 7.8: Se´rie com troca de sinais e fatorais no denominador corrigidos.
const itmax=20;
begin
seno:= 0;
fat:= 1;
sinal:= 1;
read (x) ;
x quadrado:= x∗x;
numerador:= x;
i:= 1;
while i <= itmax do
begin
novotermo:= numerador/fat ; (∗ atualiza o termo ∗)
seno:= seno + sinal∗novotermo;
numerador:= numerador∗x quadrado; (∗ atualiza o numerador ∗)
fat:= 2∗ i∗(2∗ i+1)∗fat ;
sinal:= −sinal ;
i := i + 1;
end;
writeln (’seno(’ ,x,’)= ’ ,seno) ;
end.
Figura 7.9: Ca´lculo do seno de x.
7.4. NU´MEROS PRIMOS 83
7.4 Nu´meros primos
Este e´ um dos mais completos problemas desta parte inicial da disciplina. A soluc¸a˜o
dele envolve diversos conceitos aprendidos e, de certa forma, permite o estabelecimento
de um ponto de checagem no aprendizado.
Problema: Dado um nu´mero natural n, determinar se ele e´ primo.
Nu´meros naturais primos sa˜o aqueles que sa˜o divis´ıveis apenas por ele mesmo e
por 1. Em outras palavras, se n e´ um nu´mero natural, enta˜o ele e´ primo se, e somente
se, na˜o existe outro nu´mero 1 < p < n que divida n.
Os nu´meros primos sa˜o de particular interesse em computac¸a˜o, sobretudo nos dias
de hoje, pois esta˜o por tra´s dos principais algoritmos de criptografia e transmissa˜o
segura na Internet. Nesta sec¸a˜o vamos estudar alguns algoritmos para se determinar
se um nu´mero e´ ou na˜o primo.
Aplicando-se diretamente a definic¸a˜o, temos que verificar se algum nu´mero entre
2 e n− 1 divide n. Se p divide n enta˜o o resultado da operac¸a˜o nmod p e´ zero.
O primeiro algoritmo, apresentado na figura 7.10, e´ bastante simples: basta variar
p de 2 ate´ n− 1 e contar todos os valores para os quais p divide n. Se a contagem for
zero, o nu´mero na˜o tem divisores no intervalo e e´ portanto primo. Sena˜o na˜o e´.
begin
read (n) ;
cont:= 0; (∗ contador de divisores de n ∗)
i := 2;
while i <= n−1 do
begin
if n mod i = 0 then
cont:= cont + 1; (∗ achou um divisor ∗)
i := i + 1;
end;
i f cont = 0 then
writeln (n,’ eh primo’)
end.
Figura 7.10: Verifica se n e´ primo contando os divisores.
Este algoritmo e´ bom para se determinar quantos divisores primos um dado
nu´mero tem, mas na˜o e´ eficiente para este problema pois basta saber se existe pelo
menos um divisor. Logo, basta parar logo apo´s o primeiro divisor ter sido encontrado.
A te´cnica utilizada e´ baseada em uma varia´vel booleana inicializada como sendo
verdadeira. O algoritmo “chuta” que n e´ primo mas, em seguida, se os ca´lculos
mostrarem que o chute estava errado, a informac¸a˜o e´ corrigida.
O lac¸o principal do programa deve ter duas condic¸o˜es de parada: (1) termina
quando um divisor foi encontrado; (2) termina quando nenhum divisor foi encontrado,
isto e´, quando i ultrapassou n − 1. Um teste na sa´ıda do lac¸o encontra o motivo da
sa´ıda e imprime a resposta correta. Este algoritmo pode ser visto na figura 7.11.
84 CAPI´TULO 7. APLICAC¸O˜ES DAS TE´CNICAS ELEMENTARES
begin
read (n) ;
eh primo:= true ; (∗ inicia chutando que n eh primo ∗)
i := 2;
while ( i <= n−1) and eh primo do
begin
if n mod i = 0 then
eh primo:= false ; (∗ se nao for , corrige ∗)
i := i + 1;
end;
i f eh primo then
writeln (n,’ eh primo’)
end.
Figura 7.11: Testa se n e´ primo parando no primeiro divisor.
A ana´lise deste algoritmo deve ser feita em duas situac¸o˜es: (1) no pior caso, aquele
em que o nu´mero e´ primo; (2) no melhor caso, aquele em que o nu´mero na˜o e´ primo,
de prefereˆncia um primo bem baixo.
No segundo caso, o algoritmo vai terminar bem ra´pido. No outro, ele vai testar
todas as possibilidades de ı´mpares. Mas o caso o´timo e´ raro. De fato, nos problemas
envolvendo criptografia, estes nu´meros primos tem duzentos ou mais d´ıgitos. Isto
pode fazer com que o computador fique bastante tempo processando a informac¸a˜o.
Percebemos enta˜o que se o nu´mero for par enta˜o so´ tem uma chance dele ser
tambe´m