ALGORITMOS E ESTRUTURAS DE DADOS I
259 pág.

ALGORITMOS E ESTRUTURAS DE DADOS I


DisciplinaAlgoritmos e Estrutura de Dados I708 materiais7.919 seguidores
Pré-visualização50 páginas
no escopo do comando de desvio
condicional.
6.4.1 Calculo do MDC
Problema: Imprimir o Ma´ximo Divisor Comum (MDC) entre dois nu´meros dados.
O conceito matema´tico de ma´ximo divisor comum entre dois nu´meros dados a e b
envolve a fatorac¸a\u2dco de cada nu´mero como um produto de fatores primos, escolhendo-se
os fatores primos que se repetem com a pote\u2c6ncia m\u131´nima.
Exemplo: Calcular o MDC entre 24 e 45.
72 = 23 × 32
135 = 33 × 5
66 CAPI´TULO 6. TE´CNICAS ELEMENTARES
Da teoria conclui-se que o MDC entre 72 e 135 e´ 32, pois o 3 e´ o u´nico fator primo
que se repete em ambos os nu´meros de entrada, e a menor pote\u2c6ncia comum e´ 2.
Implementar este algoritmo para encontrar o MDC e´ complicado no momento pois
na\u2dco sabemos ainda como obter uma seque\u2c6ncia de primos. Tambe´m na\u2dco sabemos ainda
o quanto caro e´ calcular um nu´mero primo.
Euclides propo\u2c6s um algoritmo eficiente para se obter o MDC entre dois nu´meros
que na\u2dco requer o uso da fatorac¸a\u2dco. Trata-se de um dos primeiros algoritmos conheci-
dos, pois foi proposto por volta do ano 300 a.c. O algoritmo pode ser visto atualmente
em Pascal conforme esta´ ilustrado na figura 6.16.
program mdcporeuclides ;
var a, b, resto : integer ;
begin
read (a ,b) ;
i f (a <> 0) AND (b <> 0)) then
begin
resto:= a mod b;
while resto <> 0 do
begin
a:= b;
b:= resto ;
resto:= a mod b;
end;
writeln (\u2019mdc = \u2019 , b) ;
end
else
writeln (\u2019o algoritmo nao funciona para entradas nulas.\u2019) ;
end.
Figura 6.16: Algoritmo de Euclides para ca´lculo do MDC.
Este algoritmo mostra um caso em que o comando de repetic¸a\u2dco esta´ dentro do
escopo do comando de desvio condicional. Efetivamente os ca´lculos sa\u2dco feitos somente
se as entradas na\u2dco forem nulas.
6.5 Repetic¸o\u2dces aninhadas
Nesta sec¸a\u2dco estudaremos problemas para os quais os algoritmos exigem o aninhamento
de repetic¸o\u2dces.
6.5.1 Tabuada
Problema: Imprimir as tabuadas do 1 ao 10.
6.5. REPETIC¸O\u2dcES ANINHADAS 67
program tabuada;
var i , j : integer ;
begin
i := 1;
while i <= 10 do
begin
j:= 1;
while j <= 10 do
begin
writeln ( i ,\u2019x\u2019 , j ,\u2019= \u2019 , i\u2217 j ) ; (\u2217 comando mais interno \u2217)
j:= j + 1;
end;
writeln ;
i := i + 1;
end;
end.
Figura 6.17: Tabuadas do 1 ao 10.
No co´digo apresentado na figura 6.17, para cada valor de i, os valores de j variam
de 1 a 10, o que faz com que o comando writeln mais interno seja executado 100 vezes
ao longo do programa. Se fo\u2c6ssemos imprimir a tabuada do 1 ao 1000, este comando
seria executado um milha\u2dco de vezes. Em termos gene´ricos, para uma entrada de
tamanho n, o comando mais interno e´ executado da ordem de n2 vezes, por isto sa\u2dco
conhecidos como algoritmos de complexidade quadra´tica. Nos programas anteriores,
o ma´ximo que t´\u131nhamos era uma complexidade linear com relac¸a\u2dco ao tamanho da
entrada.
6.5.2 Fatorial
O problema seguinte e´ bastante relevante neste ponto, pois nos permitira´ uma ana´lise
sobre a te´cnica usada para resolve\u2c6-lo. A te´cnica ba´sica implementa diretamente a
definic¸a\u2dco de fatorial e usa uma estrutura baseada em um aninhamento triplo: um
desvio condicional no escopo de um aninhamento duplo.
Problema: Imprimir o valor do fatorial de todos os nu´meros entre 1 e n, sendo n
fornecido pelo usua´rio.
O fatorial de n e´ assim definido:
n= n× (n\u2212 1)× (n\u2212 2)× . . .× 3× 2× 1
Logo, o ca´lculo do fatorial de um nu´mero tem complexidade linear com relac¸a\u2dco ao
tamanho da entrada e pode ser facilmente implementado usando a te´cnica elementar
dos acumuladores, conforme e´ ilustrado na figura 6.18.
68 CAPI´TULO 6. TE´CNICAS ELEMENTARES
program fatorial ;
var i , n, fat : integer ;
begin
read (n) ;
fat:= 1; (\u2217 inicializacao do acumulador \u2217)
i := n;
while i >= 1 do
begin
fat:= fat \u2217 i ;
i f i > 1 then
write ( i ,\u2019x\u2019)
else
write ( i ,\u2019= \u2019) ;
i := i \u2212 1;
end;
writeln ( fat ) ;
end.
Figura 6.18: Obtendo o fatorial de n.
Esta versa\u2dco resolve o problema para o ca´lculo do fatorial de um u´nico nu´mero
dado como entrada e portanto na\u2dco resolve o enunciado. Pore´m, basta colocar este
trecho sob o controle de outra repetic¸a\u2dco que se obte´m o efeito desejado. A soluc¸a\u2dco e´
apresentada na figura 6.19.
E´ verdade que o programa funciona, mas e´ extremamente ineficiente e repleto de
ca´lculos redundantes. De fato, o usua´rio que testou o programa para o valor de n = 7
vai perceber que a multiplicac¸a\u2dco de 2 × 1 ocorreu 6 vezes, a multiplicac¸a\u2dco de 3 × 2
ocorreu 5 vezes, a de 4 × 6 ocorreu 4 vezes e assim por diante. O programador na\u2dco
explorou corretamente os ca´lculos ja´ feitos anteriormente. i
Em outras palavras, o programa pode ficar mais eficiente se for feito como ilustrado
na figura 6.20, de maneira que o algoritmo, mais esperto, tem complexidade linear, e
na\u2dco quadra´tica como na versa\u2dco anterior. Interessante observar que a soluc¸a\u2dco, eficiente,
usa apenas uma atribuic¸a\u2dco no escopo de uma repetic¸a\u2dco.
6.5. REPETIC¸O\u2dcES ANINHADAS 69
program fatorial1 n ;
var cont , i , n, fat : integer ;
begin
read (n) ;
cont:= 1;
while cont <= n do
begin
fat:= 1; (\u2217 inicializacao do acumulador \u2217)
i := cont ;
while i >= 1 do
begin
fat:= fat \u2217 i ;
i f i > 1 then
write ( i ,\u2019x\u2019)
else
write ( i ,\u2019= \u2019) ;
i := i \u2212 1;
end;
writeln ( fat ) ;
cont:= cont + 1;
end;
end.
Figura 6.19: Obtendo va´rios fatoriais.
program fatorial1 n ;
var cont , n, fat : integer ;
begin
read (n) ;
cont:= 1;
fat:= 1; (\u2217 inicializacao do acumulador \u2217)
while cont <= n do
begin
fat:= fat \u2217 cont ;
writeln (\u2019fat(\u2019 ,cont ,\u2019)= \u2019 , fat ) ;
cont:= cont + 1;
end;
end.
Figura 6.20: Otimizando o ca´lculo dos fatoriais.
70 CAPI´TULO 6. TE´CNICAS ELEMENTARES
6.6 Exerc´\u131cios
1. Dados o primeiro termo e a raza\u2dco de uma progressa\u2dco aritme´tica, determinar a
soma dos seus primeiros cinco termos.
2. Ler um inteiro positivo N diferente de zero e calcular a soma: 13 + 23 + ...+N3.
3. Dados dois nu´meros inteiros positivos determinar o valor da maior pote\u2c6ncia do
primeiro que divide o segundo. Se o primeiro na\u2dco divide o segundo, a maior
pote\u2c6ncia e´ definida igual a 1.
4. Dados dois nu´meros reais positivos determinar o quociente inteiro do primeiro
pelo segundo usando apenas os operadores aritme´ticos reais.
5. Dado um nu´mero real positivo determinar sua parte inteira e sua parte fra-
ciona´ria usando apenas os operadores aritme´ticos reais.
6. Fazer um programa em Pascal que leia uma seque\u2c6ncia de pares de nu´meros
inteiros quaisquer, sendo dois inteiros por linha de entrada. A entrada de dados
termina quando os dois nu´meros lidos forem nulos. Este par de zeros na\u2dco deve
ser processado e serve apenas para marcar o te´rmino da entrada de dados.
Para cada par A,B de nu´meros lidos, se B for maior do que A, imprimir a
seque\u2c6ncia A,A+ 1, . . . , B \u2212 1, B. Caso contra´rio, imprimir a seque\u2c6ncia B,B +
1, . . . , A\u2212 1, A.
Exemplos:
Entrada Saida
4 6 4 5 6
-2 1 -2 -1 0 1
2 -3 2 1 0 -1 -2 -3
0 0
7. Um inteiro positivo N e´ perfeito se for igual a soma de seus divisores positivos
diferentes de N .
Exemplo: 6 e´ perfeito pois 1 + 2 + 3 = 6 e 1, 2, 3 sa\u2dco todos os divisores positivos
de 6 e que sa\u2dco diferentes de 6.
Fac¸a um programa em Pascal que recebe como entrada um nu´mero positivo K
e mostre os K primeiros nu´meros perfeitos.
8. Dadas as populac¸o\u2dces PA e PB de duas cidades A e B em 2009, e suas respectivas
taxas de crescimento anual XA e XB, fac¸a um programa em Pascal que receba
estas informac¸o\u2dces como entrada e determine:
\u2022 se a populac¸a\u2dco da cidade de menor populac¸a\u2dco ultrapassara´ a de maior
populac¸a\u2dco;
\u2022 e o ano em que isto ocorrera´.
6.6. EXERCI´CIOS 71
9. Escreva um programa em Pascal para ler uma seque\u2c6ncia de nu´meros inteiros,
terminada em \u22121. Para cada nu´mero inteiro lido, o programa deve verificar se
este nu´mero esta´ na base bina´ria, ou seja, se e´ composto apenas pelos d´\u131gitos 0
e 1. Caso o nu´mero esteja na base bina´ria, o programa deve imprimir seu valor
na base decimal. Caso contra´rio, deve imprimir uma mensagem indicando que
o nu´mero na\u2dco e´ bina´rio. Ao final do programa deve ser impresso, em formato
decimal, o maior nu´mero va´lido