apostila
259 pág.

apostila


DisciplinaAlgoritmos e Estrutura de Dados I706 materiais7.916 seguidores
Pré-visualização50 páginas
caso contra´rio e, em seguida,
imprima a intercalac¸a\u2dco dos dois.
Exemplo de intercalac¸a\u2dco: v: 1 4 6 9; w: 2, 3, 5, 7.
Sa´\u131da: 1, 2, 3, 4, 5, 6, 7, 9.
7. Dados dois nu´meros naturais m e n, uma frase com m letras e uma palavra
com n letras, escreva um procedimento que determine o nu´mero de vezes que a
palavra ocorre na frase e a posic¸a\u2dco em que cada ocorre\u2c6ncia inicia.
Exemplo:
Para M = 30, N = 3, a palavra ANA e a frase:
ANA E MARIANA GOSTAM DE BANANA
A palavra ANA ocorre 4 vezes, nas posic¸~oes 1, 11, 26, 28.
8. Dada uma seque\u2c6ncia de N nu´meros, determinar quantos nu´meros dintintos
compo\u2dce a seque\u2c6ncia e o nu´mero de vezes que cada um deles ocorre na mesma.
Exemplo:
N=5 1 2 3 2 3 a seque\u2c6ncia tem tre\u2c6s nu´meros distintos, 1, 2 e 3. Ocorre\u2c6ncias: 1
ocorre 1 vez 2 ocorre 2 vezes 3 ocorre 2 vezes
9. Dadas duas seque\u2c6ncias com n nu´meros inteiros entre 0 e 1, interpretados como
nu´meros bina´rios:
(a) imprimir o valor decimal dos nu´meros;
(b) calcular a soma de ambos (em bina´rio), usando o \u201cvai-um\u201d;
(c) imprimir o valor decimal da soma.
10. Escreva um programa em que leia os seguintes valores: um inteiro B, um inteiro
N (1 \u2264 N \u2264 10), e N valores inteiros. A ideia e´ que estes valores sejam
entendidos como a representac¸a\u2dco de um nu´mero na\u2dco negativo na base B. Estes
valores devera\u2dco ser inseridos em um vetor de tamanho N + 1, onde a primeira
posic¸a\u2dco armazena a base B e as outras N posic¸o\u2dces o restante dos nu´meros lidos.
Note que o intervalo de valores poss´\u131veis para cada d´\u131gito na base B e´ [0, B\u22121].
Seu programa deve retornar o valor em decimal do nu´mero representado no
vetor. Se o nu´mero representado no vetor na\u2dco for va´lido na base B enta\u2dco devera´
ser retornado o co´digo de erro \u201c-1\u201d. Por exemplo, se B = 3 o nu´mero 2102 na
base 3 equivale ao valor decimal 65; se B = 4 o nu´mero 35 e´ inva´lido na base 4.
10.1. VETORES 165
11. Fac¸a um programa em que, dadas duas seque\u2c6ncias com N nu´meros inteiros en-
tre 0 e 9, interpretadas como dois nu´meros inteiros de N algarismos, calcular a
seque\u2c6ncia de nu´meros que representa a soma dos dois inteiros, usando o \u201cvai-
um\u201d. Por exemplo:
N=6,
4 3 4 2 5 1
+ 7 5 2 3 3 7
1 1 8 6 5 8 8
12. Dada uma seque\u2c6ncia x1, x2, . . . , xn de nu´meros inteiros, determinar um seg-
mento de soma ma´xima. Exemplo: na seque\u2c6ncia 5, 2, -2, -7, 3, 14, 10, -3, 9, -6,
4, 1, a soma do maior segmento e´ 33, obtida pela soma dos nu´meros de 3 ate´ 9.
13. Implemente um programa que leia um vetor de 1 milha\u2dco de inteiros em um vetor
de inteiros. Gere um nu´mero aleato´rio e o procure neste vetor de duas maneiras
diferentes: uma usando busca com sentinela e outra usando busca bina´ria. Seu
programa deve imprimir uma tabela com o nu´mero de comparac¸o\u2dces feitas em
cada um dos casos acima (busca com sentinela e busca bina´ria). Desconsidere
o tempo gasto com ordenac¸a\u2dco no caso da busca bina´ria. A busca com sentinela
deve ser feita em um vetor na\u2dco ordenado. Gere 200 nu´meros aleato´rios e imprima
a me´dia de comparac¸o\u2dces para cada um dos dois algoritmos sendo testados.
14. Suponha que um exe´rcito tenha 20 regimentos e que eles esta\u2dco em processo de
formac¸a\u2dco. Inicialmente o primeiro tem 1000 homens, o segundo 950, o terceiro
900, e assim por diante, ate´ o vige´simo que tem 50. Suponhamos que a cada
semana 100 homens sa\u2dco enviados para cada regimento, e no final da semana o
maior regimento e´ enviado para o front. Imaginemos que o general do quinto
regimento e´ companheiro de xadrez do comandante supremo, e que eles esta\u2dco
no meio de uma partida. O comandante supremo enta\u2dco envia apenas 30 homens
para o quinto regimento a cada semana, esperando com isto poder acabar o jogo
com seu colega. Escreva um programa em que diga, a cada semana, qual e´ o
regimento enviado ao front e mostre o status dos outros regimentos. O programa
deve tambe´m determinar exatamente quantas semanas levara´ o quinto regimento
para ser deslocado ao front.
15. Suponha que voce\u2c6 esteja usando o me´todo da ordenac¸a\u2dco por selec¸a\u2dco. Qual
das seque\u2c6ncias abaixo requerira´ o menor nu´mero de trocas? Quantas? Qual
requerira´ o maior nu´mero de trocas? Quantas? Explique.
(a) 10, 9, 8, 7, 6, 5, 4, 3, 2, 1.
(b) 5, 4, 3, 2, 1, 10, 9, 8, 7, 6.
(c) 10, 1, 9, 2, 8, 3, 7, 4, 6, 5.
(d) 2, 3, 4, 5, 6, 7, 8, 9, 10, 1.
(e) 1, 10, 2, 9, 3, 8, 4, 7, 5, 6.
166 CAPI´TULO 10. ESTRUTURAS DE DADOS
16. Suponha que voce\u2c6 tem uma varia´vel do tipo vetor declarada como: array [1..50]
of real;. Fac¸a uma func¸a\u2dco que inicialize o vetor de modo que os elementos
de \u131´ndices \u131´mpares recebam o valor inicial -2.0 e os elementos de \u131´ndices pares
recebam o valor inicial 7.0. Sua func¸a\u2dco deve fazer uso de apenas um comando
de repetic¸a\u2dco, que incrementa de um em um, e de nenhum comando de desvio
condicional.
17. Qual dos seguintes problemas requer o uso de vetores para uma soluc¸a\u2dco elegante?
(a) Ler cerca de duzentos nu´meros e imprimir os que esta\u2dco em uma certa faixa;
(b) Computar a soma de uma seque\u2c6ncia de nu´meros;
(c) Ler exatamente duzentos nu´meros e ordena´-los em ordem crescente;
(d) Encontrar o segundo menor elemento de uma seque\u2c6ncia de entrada;
(e) Encontrar o menor inteiro de uma seque\u2c6ncia de inteiros.
18. Considere um vetor declarado como: array [1..50] of integer que tem a par-
ticularidade de todos os elementos estarem entre 1 e 30, sendo que nenhum e´
repetido. Fac¸a um programa que ordene o vetor de maneira eficiente explorando
esta caracter´\u131stica e fazendo o menor nu´mero poss´\u131vel de trocas.
19. Dada uma seque\u2c6ncia x1, x2, . . . , xk de nu´meros reais, verifique se existem dois
segmentos consecutivos iguais nesta seque\u2c6ncia, isto e´, se existem i e m tais que:
xi, xi+1, . . . , xi+m\u22121 = xi+m, xi+m+1, . . . , xi+2m\u22121.
Imprima, caso existam, os valores de i e de m. Caso contra´rio, na\u2dco imprima
nada. Exemplo: Na seque\u2c6ncia 7,9,5,4,5,4,8,6, existem i = 3 e m = 2.
20. Um coeficiente binomial, geralmente denotado
(
n
k
)
, representa o nu´mero de
poss´\u131veis combinac¸o\u2dces de n elementos tomados k a k. Um \u201cTria\u2c6ngulo de Pascal\u201d,
uma homenagem ao grande matema´tico Blaise Pascal, e´ uma tabela de valores
de coeficientes combinatoriais para pequenos valores de n e k. Os nu´meros que
na\u2dco sa\u2dco mostrados na tabela te\u2c6m valor zero. Este tria\u2c6ngulo pode ser constru´\u131do
automaticamente usando-se uma propriedade conhecida dos coeficientes bino-
miais, denominada \u201cfo´rmula da adic¸a\u2dco\u201d:
(
r
k
)
=
(
r\u22121
k
)
+
(
r\u22121
k\u22121
)
. Ou seja, cada
elemento do tria\u2c6ngulo e´ a soma de dois elementos da linha anterior, um da
mesma coluna e um da coluna anterior. Veja um exemplo de um tria\u2c6ngulo de
Pascal com 7 linhas:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
10.1. VETORES 167
Fac¸a um programa em que imprima na tela um tria\u2c6ngulo de Pascal com 10
linhas. Seu programa deve obrigatoriamente fazer uso de exatamente dois ve-
tores durante o processo de construc¸a\u2dco. Um deles contera´ a u´ltima linha \u131´mpar
gerada, enquanto que o outro contera´ a u´ltima linha par gerada. Lembre-se que
os elementos que na\u2dco aparecem na tabela tem valor nulo. Voce\u2c6 deve sempre ter
o controle do tamanho da u´ltima linha impressa (o tamanho u´til dos vetores em
cada passo). Voce\u2c6 deve tambe´m usar um procedimento para imprimir o vetor.
Observe que na\u2dco ha´ entrada de dados, os dois vetores sa\u2dco gerados, um a partir
do outro. O u´nico elemento da primeira linha tem o valor 1. Voce\u2c6 deve obri-
gatoriamente declarar um tipo vetor com tamanho ma´ximo Tam max vetor, e
o seu programa devera´ tomar cuidado para manipular corretamente vetores de
tamanho menor do que o tamanho ma´ximo, impedindo que haja uma atribuic¸a\u2dco
em posic¸a\u2dco ilegal de memo´ria.
21. Resolva o problema do tria\u2c6ngulo de Pascal usando apenas um vetor.
22. Seja um polino\u2c6mio p(x) = a0 + a1x + a2x
2 + . . . + anx
n de