apostila
259 pág.

apostila


DisciplinaAlgoritmos e Estrutura de Dados I706 materiais7.917 seguidores
Pré-visualização50 páginas
um valor
previamente estabelecido, isto e´, uma precisa\u2dco previamente determinada. Em alguns
casos, quando o ca´lculo da se´rie na\u2dco e´ convergente, este valor m\u131´nimo nunca e´ atingido,
80 CAPI´TULO 7. APLICAC¸O\u2dcES DAS TE´CNICAS ELEMENTARES
obrigando tambe´m o programa a testar um nu´mero ma´ximo de iterac¸o\u2dces. Segue a
mesma ideia discutida no caso de gerar o nu´mero a´ureo.
Suponhamos que o enunciado tivesse como condic¸a\u2dco de parada um destes dois
crite´rios: ou o erro e´ menor do que 10\u22127 ou o nu´mero ma´ximo de iterac¸o\u2dces e´ 50.
Se o programa sair pelo crite´rio de erro, enta\u2dco o valor de e foi encontrado, sena\u2dco,
se saiu pelo crite´rio do nu´mero ma´ximo de iterac¸o\u2dces, enta\u2dco o programa avisa que
na\u2dco conseguiu encontrar a soluc¸a\u2dco. A figura 7.6 ilustra a soluc¸a\u2dco para este caso. E´
importante observar que o que muda com relac¸a\u2dco a` primeira soluc¸a\u2dco e´ apenas o crite´rio
de parada. Os ca´lculos internos sa\u2dco os mesmos.
const itmax=50; precisao=0.0001;
begin
e:= 0;
eanterior:= \u22121;
fat:= 1;
i := 1;
while ( i <= itmax) and (e \u2212 eanterior > precisao) do
begin
novotermo:= 1/fat ;
eanterior:= e ;
e:= e + novotermo;
fat:= i\u2217fat ;
i := i + 1;
end;
i f i >= itmax then
writeln (\u2019solucao nao encontrada\u2019)
else
writeln (\u2019e= \u2019 ,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!
\u2212 x
3
3!
+
x5
5!
\u2212 x
7
7!
+
x9
9!
\u2212 x
11
11!
+
x13
13!
\u2212 x
15
15!
+ . . .
Comparando esta se´rie com a do nu´mero neperiano, observamos tre\u2c6s 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\u2c6ncia de x; a terceira e´ que os fatoriais na\u2dco sa\u2dco consecutivos em
cada termo, aumentam de dois em dois.
7.3. SE´RIES 81
Trataremos de cada caso separadamente, construindo a soluc¸a\u2dco para o seno base-
ada na do nu´mero neperiano. Vamos tratar primeiro o mais simples, que e´ a questa\u2dco
dos sinais. Considere a seguinte se´rie:
tmp =
1
0!
\u2212 1
1!
+
1
2!
\u2212 1
3!
+
1
4!
\u2212 1
5!
+
1
6!
\u2212 1
7!
+ . . .
O algoritmo da figura 7.7 modifica o anterior pela introduc¸a\u2dco de uma nova varia´vel
que controla a mudanc¸a do sinal, produzindo como sa´\u131da o ca´lculo da func¸a\u2dco tmp.
const itmax=20;
begin
seno:= 0;
fat:= 1;
sinal:= 1;
i := 1;
while i <= itmax do
begin
novotermo:= 1/fat ;
seno:= seno + sinal\u2217novotermo;
sinal:= \u2212sinal ; (\u2217 nova variavel para sinal trocado \u2217)
fat:= i\u2217fat ;
i := i + 1;
end;
writeln (\u2019tmp= \u2019 ,seno) ;
end.
Figura 7.7: Se´rie com troca de sinais.
Agora vamos corrigir o denominador, obtendo a seguinte se´rie:
tmp2 =
1
1!
\u2212 1
3!
+
1
5!
\u2212 1
7!
+
1
9!
\u2212 1
11!
+
1
13!
\u2212 1
15!
+ . . .
A atualizac¸a\u2dco da varia´vel fat deve ser modificada, conforme apontado na fi-
gura 7.8:
Agora so´ resta a atualizac¸a\u2dco 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´\u131cio. Basicamente, basta o estudante observar
como os numeradores e denominadores podem ser atualizados em func¸a\u2dco do termo
anteriormente calculado.
82 CAPI´TULO 7. APLICAC¸O\u2dcES 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\u2217novotermo;
fat:= 2\u2217 i\u2217(2\u2217 i+1)\u2217fat ; (\u2217 esta eh a princial modificacao \u2217)
sinal:= \u2212sinal ;
i := i + 1;
end;
writeln (\u2019tmp2= \u2019 ,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\u2217x;
numerador:= x;
i:= 1;
while i <= itmax do
begin
novotermo:= numerador/fat ; (\u2217 atualiza o termo \u2217)
seno:= seno + sinal\u2217novotermo;
numerador:= numerador\u2217x quadrado; (\u2217 atualiza o numerador \u2217)
fat:= 2\u2217 i\u2217(2\u2217 i+1)\u2217fat ;
sinal:= \u2212sinal ;
i := i + 1;
end;
writeln (\u2019seno(\u2019 ,x,\u2019)= \u2019 ,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\u2dco
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\u2dco aqueles que sa\u2dco divis´\u131veis apenas por ele mesmo e
por 1. Em outras palavras, se n e´ um nu´mero natural, enta\u2dco ele e´ primo se, e somente
se, na\u2dco existe outro nu´mero 1 < p < n que divida n.
Os nu´meros primos sa\u2dco de particular interesse em computac¸a\u2dco, sobretudo nos dias
de hoje, pois esta\u2dco por tra´s dos principais algoritmos de criptografia e transmissa\u2dco
segura na Internet. Nesta sec¸a\u2dco vamos estudar alguns algoritmos para se determinar
se um nu´mero e´ ou na\u2dco primo.
Aplicando-se diretamente a definic¸a\u2dco, temos que verificar se algum nu´mero entre
2 e n\u2212 1 divide n. Se p divide n enta\u2dco o resultado da operac¸a\u2dco nmod p e´ zero.
O primeiro algoritmo, apresentado na figura 7.10, e´ bastante simples: basta variar
p de 2 ate´ n\u2212 1 e contar todos os valores para os quais p divide n. Se a contagem for
zero, o nu´mero na\u2dco tem divisores no intervalo e e´ portanto primo. Sena\u2dco na\u2dco e´.
begin
read (n) ;
cont:= 0; (\u2217 contador de divisores de n \u2217)
i := 2;
while i <= n\u22121 do
begin
if n mod i = 0 then
cont:= cont + 1; (\u2217 achou um divisor \u2217)
i := i + 1;
end;
i f cont = 0 then
writeln (n,\u2019 eh primo\u2019)
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\u2dco 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 \u201cchuta\u201d que n e´ primo mas, em seguida, se os ca´lculos
mostrarem que o chute estava errado, a informac¸a\u2dco e´ corrigida.
O lac¸o principal do programa deve ter duas condic¸o\u2dces de parada: (1) termina
quando um divisor foi encontrado; (2) termina quando nenhum divisor foi encontrado,
isto e´, quando i ultrapassou n \u2212 1. Um teste na sa´\u131da do lac¸o encontra o motivo da
sa´\u131da e imprime a resposta correta. Este algoritmo pode ser visto na figura 7.11.
84 CAPI´TULO 7. APLICAC¸O\u2dcES DAS TE´CNICAS ELEMENTARES
begin
read (n) ;
eh primo:= true ; (\u2217 inicia chutando que n eh primo \u2217)
i := 2;
while ( i <= n\u22121) and eh primo do
begin
if n mod i = 0 then
eh primo:= false ; (\u2217 se nao for , corrige \u2217)
i := i + 1;
end;
i f eh primo then
writeln (n,\u2019 eh primo\u2019)
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\u2dces: (1) no pior caso, aquele
em que o nu´mero e´ primo; (2) no melhor caso, aquele em que o nu´mero na\u2dco e´ primo,
de prefere\u2c6ncia um primo bem baixo.
No segundo caso, o algoritmo vai terminar bem ra´pido. No outro, ele vai testar
todas as possibilidades de \u131´mpares. Mas o caso o´timo e´ raro. De fato, nos problemas
envolvendo criptografia, estes nu´meros primos tem duzentos ou mais d´\u131gitos. Isto
pode fazer com que o computador fique bastante tempo processando a informac¸a\u2dco.
Percebemos enta\u2dco que se o nu´mero for par enta\u2dco so´ tem uma chance dele ser
tambe´m