apostila
259 pág.

apostila


DisciplinaAlgoritmos e Estrutura de Dados I706 materiais7.917 seguidores
Pré-visualização50 páginas
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 (bina´rio) da seque\u2c6ncia.
Dica: dado o nu´mero 10011 em base bina´ria, seu valor correspondente em base
decimal sera´ dado por
1.24 + 0.23 + 0.22 + 1.21 + 1.20 = 19
Exemplo:
Entrada: Saida:
10011 19
121 numero nao binario
1010 10
101010101 341
0 0
-1
O maior numero binario foi 341
10. Dado o programa abaixo, mostre o acompanhamento de sua execuc¸a\u2dco para tre\u2c6s
valores de entrada (valores pequenos). Em seguida, descreva o que o programa
faz, comprovando suas afirmac¸o\u2dces.
program questao1(input , output) ;
var
x: integer ;
y, m: longint ;
begin
read(x) ;
y := 0;
m := 1;
while x > 0 do
begin
y := y + (x mod 2) \u2217 m;
x := x div 2;
m := m \u2217 10;
end;
writeln(y)
end.
11. Considere o seguinte co´digo fonte escrito em Pascal :
72 CAPI´TULO 6. TE´CNICAS ELEMENTARES
program prova (input ,output) ;
var
i , j , VAL, N: integer ;
begin
for i := 1 to 4 do
begin
read (VAL) ;
writeln (VAL, i ) ;
for j:= 3 to 5 do
begin
read (VAL) ;
N:= VAL + i \u2212j ;
writeln (VAL, j ,N) ;
end;
read (VAL) ;
end;
end.
Suponha que voce\u2c6 de\u2c6 como entrada de dados uma seque\u2c6ncia crescente 1, 2, 3,
4, . . . , na medida em que forem sendo executados os comandos \u201cread\u201d. Qual a
sa´\u131da que sera´ mostrada na tela do computador?
12. Fac¸a um programa em Pascal que, dada uma seque\u2c6ncia de nu´meros naturais
positivos terminada por 0 (zero), imprimir o histograma da seque\u2c6ncia dividido
em quatro faixas (o histograma e´ a contagem do nu´mero de elementos em cada
faixa):
\u2022 Faixa 1: 1 \u2013 100;
\u2022 Faixa 2: 101 \u2013 250;
\u2022 Faixa 3: 251 \u2013 20000;
\u2022 Faixa 4: acima de 20001.
Exemplo:
Entrada: 347 200 3 32000 400 10 20 25 0
Sa\u131´da: Faixa 1: 4
Faixa 2: 1
Faixa 3: 2
Faixa 4: 1
13. Sabe-se que um nu´mero da forma n3 e´ igual a soma de n nu´meros \u131´mpares
consecutivos.
Exemplos:
\u2022 13 = 1
\u2022 23 = 3 + 5
\u2022 33 = 7 + 9 + 11
6.6. EXERCI´CIOS 73
\u2022 43 = 13 + 15 + 17 + 19
Dado M , escreva um program em Pascal que determine os \u131´mpares consecutivos
cuja soma e´ igual a n3 para n assumindo valores de 1 a M .
14. Fac¸a um programa em Pascal que dado um inteiro positivo n, escreva todos
os termos, do primeiro ao n-e´simo, da se´rie abaixo. Voce\u2c6 pode assumir que o
usua´rio nunca digita valores menores que 1 para n.
5, 6, 11, 12, 17, 18, 23, 24, . . .
15. Fac¸a um programa em Pascal que, dado dois nu´mero naturais m e n determinar,
entre todos os pares de nu´meros naturais (x, y) tais que x <= m e y <= n, um
par para o qual o valor da expressa\u2dco xy\u2212x2 +y seja ma´ximo e calcular tambe´m
esse ma´ximo.
16. Leia do teclado uma seque\u2c6ncia de N > 0 nu´meros quaisquer. Para cada valor
lido, se ele for positivo, imprimir os primeiros 10 mu´ltiplos dele.
74 CAPI´TULO 6. TE´CNICAS ELEMENTARES
Cap´\u131tulo 7
Aplicac¸o\u2dces das te´cnicas elementares
Neste cap´\u131tulo vamos escrever soluc¸o\u2dces para problemas cujo grau de dificuldade e´
similar aos dos problemas do cap´\u131tulo anterior, com o objetivo de fixar conceitos.
Nestes problemas as te´cnicas devem ser combinadas com intelige\u2c6ncia, pios deve-se
pensar em como resolver problemas complexos usando-se apenas os elementos ba´sicos.
A partir de agora omitiremos os cabec¸alhos dos programas em Pascal.
7.1 Nu´meros de Fibonacci
Esta e´ uma das mais famosas seque\u2c6ncias de nu´meros que existe. Trata-se dos nu´meros
de Fibonacci1. Esta seque\u2c6ncia e´ gerada de modo bastante simples. Os dois primeiros
valores sa\u2dco 1 e 1. Os seguintes sa\u2dco obtidos pela soma dos dois anteriores. Assim, a
seque\u2c6ncia de Fibonacci e´: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . .
Problema: Imprimir os primeiros nu´meros da seque\u2c6ncia de Fibonacci.
Como gerar e imprimir os elementos desta seque\u2c6ncia e´ o nosso desafio. A soluc¸a\u2dco
exige que se guarde sempre os dois u´ltimos elementos gerados, sena\u2dco na\u2dco e´ poss´\u131vel
resolver o problema. Observamos que a frase do para´grafo anterior da´ a dica: \u201cos
seguintes sa\u2dco obtidos pela soma dos dois anteriores\u201d.
Na soluc¸a\u2dco apresentada na figura 7.1 consideramos duas varia´veis importantes,
uma para armazenar o u´ltimo elemento ja´ produzido pelo algoritmo, a outra para
guardar o penu´ltimo. Com estes dois, e´ poss´\u131vel produzir a soma deles, isto e´, o
pro´ximo elemento.
A atualizac¸a\u2dco destas varia´veis deve ser feita sempre que o pro´ximo elemento for
obtido, pois a soma do u´ltimo com o penu´ltimo e´ agora