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
(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 o u´ltimo elemento gerado.
O que era o u´ltimo passa a ser o penu´ltimo. A ordem da atualizac¸a\u2dco destes valo-
res e´ relevante no co´digo em func¸a\u2dco do esquema de funcionamento de memo´ria do
computador. Trocando-se a ordem dos comandos o algoritmo para de funcionar.
O algoritmo da figura 7.1 e´ normalmente o mais utilizado para este problema,
isto e´, define-se os dois primeiros e depois sucessivamente soma-se os dois u´ltimos e
1Vale a pena ler: http://pt.wikipedia.org/wiki/Nu´mero de Fibonacci.
75
76 CAPI´TULO 7. APLICAC¸O\u2dcES DAS TE´CNICAS ELEMENTARES
const max=93; (\u2217 A partir do 94o estoura a capacidade do tipo qword \u2217)
begin
ultimo:= 1; (\u2217 inicializacao das variaveis principais \u2217)
penultimo:= 1;
writeln (\u20191 \u2019 ,penultimo) ; (\u2217 imprime os dois primeiros valores \u2217)
writeln (\u20192 \u2019 ,ultimo) ;
cont:= 3 ; (\u2217 calcula do terceiro em diante \u2217)
while cont <= max do
begin
soma:= penultimo + ultimo ;
writeln (cont , \u2019 \u2019 ,soma) ;
penultimo:= ultimo ; (\u2217 a ordem destes dois comandos \u2217)
ultimo:= soma; (\u2217 eh relevante no codigo \u2217)
cont:= cont + 1;
end;
end.
Figura 7.1: Gerando nu´meros da seque\u2c6ncia de Fibonacci.
atualiza-se o u´ltimo como sendo esta soma recentemente gerada e o penu´ltimo como
sendo o que era o u´ltimo. Existem va´rios outros que sa\u2dco apresentados como exerc´\u131cios.
Um problema similar mas alternativo a este e´, por exemplo, saber qual e´ o primeiro
nu´mero de Fibonacci maior do que um determinado valor. Uma pequena alterac¸a\u2dco
no controle de parada e no local do comando de impressa\u2dco resolve o novo problema.
Isto e´ apresentado na figura 7.2. A diferenc¸a ba´sica e´ que neste caso na\u2dco e´ preciso
contar os nu´meros, pois o crite´rio de parada e´ diferente. Mas e´ importante observar
que a parte da gerac¸a\u2dco dos nu´meros da seque\u2c6ncia na\u2dco mudou.
const max=1000;
begin
ultimo:= 1; (\u2217 inicializacao das variaveis principais \u2217)
penultimo:= 1;
soma:= penultimo + ultimo ;
while soma<= max do (\u2217 calcula do terceiro em diante \u2217)
begin
penultimo:= ultimo ;
ultimo:= soma;
soma:= penultimo + ultimo ;
end;
writeln (soma) ;
end.
Figura 7.2: Imprimindo o primeiro nu´mero de Fibonacci maior do que 1000.
Uma das maiores belezas dos nu´meros de Fibonacci e´ que a raza\u2dco entre dois
termos consecutivos converge para um nu´mero irracional conhecido como nu´mero
a´ureo (tambe´m podendo ter outros nomes parecidos). Tambe´m e´ denotado pela letra
grega \u3d5 e e´ aproximadamente 1.6180339887499.
7.2. MAIOR SEGMENTO CRESCENTE 77
De fato, vejamos a raza\u2dco entre dois termos consecutivos para alguns nu´meros
pequenos:
1
1
= 1,
2
1
= 2,
3
2
= 1.5,
5
3
= 1.66,
8
5
= 1.60,
13
8
= 1.625,
21
13
= 1.615, . . .
O algoritmo que calcula o nu´mero a´ureo com a precisa\u2dco desejada, mostrando
os valores intermedia´rios, e´ apresentado na figura 7.3. Notamos que ele verifica a
converge\u2c6ncia da seque\u2c6ncia para a raza\u2dco a´urea, fazendo as contas ate´ que o erro seja
menor que a precisa\u2dco desejada. A func¸a\u2dco abs e´ nativa do Pascal e retorna o valor
absoluto do nu´mero dado como argumento.
Neste exemplo, novamente o ca´lculo central na\u2dco mudou, isto e´, os nu´meros con-
tinuam a ser gerados da mesma maneira. O que muda e´ o que fazer com eles. No
caso, e´ preciso obter a raza\u2dco do u´ltimo pelo penu´ltimo. Tambe´m e´ o primeiro exemplo
apresentado que usa nu´meros reais ao inve´s de inteiros.
const PRECISAO=0.00000000000001;
begin
ultimo:= 1; (\u2217 inicializacao das variaveis principais \u2217)
penultimo:= 1;
naureo anterior:= \u22121; (\u2217 para funcionar o primeiro teste \u2217)
naureo:= 1;
writeln (naureo:15:14) ;
(\u2217 calcula do terceiro em diante \u2217)
while abs(naureo \u2212 naureo anterior) >= PRECISAO do
begin
soma:= penultimo + ultimo ;
naureo anterior:= naureo ;
naureo:= soma/ultimo ;
writeln (naureo:15:14)