ALGORITMOS E ESTRUTURAS DE DADOS I
259 pág.

ALGORITMOS E ESTRUTURAS DE DADOS I


DisciplinaAlgoritmos e Estrutura de Dados I717 materiais7.907 seguidores
Pré-visualização50 páginas
; (\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 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