Algoritmos e Estruturas de
Dados I – Estruturas de Dados
Profa. Mercedes Gonzales
Márquez
Estruturas de Dados
•Os
tipos primitivos (inteiro, real, literal e
lógico) não são suficientes para representar
todos os tipos de informação.
•Particularmente quando temos mais de
uma informação relacionada. Ex: Lista dos
nomes dos alunos de uma sala, endereço de
alguém etc.
•Utilizaremos os tipos primitivos para
construir outras estruturas de dados mais
complexas.
Vetores
•
•
Também denominados Estruturas compostas
homogêneas unidimensionais
Permitem a manipulação de um conjunto de
informações de um mesmo tipo primitivo
◦ Declaração :
tipo primitivo : nome_vetor [numero de
elementos]
◦ Exemplo :
Um vetor com nome “dados” de 40 posições
reais terá a seguinte declaração.
Real: dados[40]
dados
1
2
3
4
5
6
7
8
9
38
39
40
2,4
7,8
3,6
5,3
9,1
9,8
6,5
9,8
4,7
1,5
2,8
4,6
Vetores
◦ Manipulação:
 Para manipular os elementos de um vetor
devemos especificar a sua posição.
dados
2,4
7,8
7,8
3,6
5,3
9,1
9,8
6,5
9,8
4,7
1,5
2,8
4,6
1
2
3
4
5
6
7
8
9
38
39
40
-dados[8]
• A posição do vetor é determinada por meio de uma
constante, de uma expressão aritmética ou de uma
variável que estiver dentro dos colchetes. Ela é
também chamada de índice.
Vetores
Exercício – Sendo o vetor v igual a
2
7,8
6
8
3
10
9
1
21
33
14
1
2
3
4
5
6
7
8
9
10
e as variáveis x=2 e y=4 escreva o valor
correspondente à solicitação
(a) v[x+1] (b) v[x+2] (c) v[x+3] (d) v[x+4]
(e) v[x*1] (f) v[x*2] (g) v[x*3] (h) v[v[x+4]]
(i) v[x+y] (j) v[8-v[2]] (k) v[v[4]] (l) v[v[v[7]]]
(m) v[v[1]*v[4]] (n) v[x+4]
Vetores
Algoritmo 2 – Leia dois vetores inteiros de 50
posições, some seus correspondentes elementos e
imprima o resultado da soma
inteiro: va[50],vb[50],vc[50],i
inicio
para i de 1 até 50 repita
leia (va[i],vb[i] )
vc[i] ← va[i] + vb[i]
escreva (vc[i])
fimpara
fim.
Vetores
Algoritmo 3 – Preencha um vetor de 100 inteiros,
colocando 1 na posição par e 0 na posição impar
inteiro: vetor[100],i
inicio
para i de 1 até 100 repita
se (mod(i,2)=0) então
vetor[i] ← 1
senão
vetor[i] ← 0
fimpara;
fim.
Vetores
Algoritmo 4 – Altere o exemplo da soma de vetores
para que esta realize a seguinte operação: produto
do primeiro vetor pelo inverso do segundo. Os
vetores possuem 20 posições e contém valores
reais.
Algoritmo <produto>
inteiro: i
real: V[20],a[20],b[20]
inicio
para i de 1 até 20 repita
V[i] ← a[i]*b[21-i]
fim para
fim.
Vetores
Algoritmo 5 – Igual que o algoritmo 4, só que o
resultado dos produtos dos valores correspondentes
devem ser armazenados a partir do centro para as
bordas, de modo alternado.
Algoritmo <produto2>
real: V[20],a[20],b[20]
inteiro: i
inicio
para i de 1 até 10 repita
v[11-i]=a[11-i]*b[10+i]
v[10+i]=a[10+i]*b[11-i]
fim para
fim.
Vetores
Algoritmo 6 – Escreva uma algoritmo que leia um
vetor de 20 elementos e conte quantos valores
pares existem no vetor.
Algoritmo <contagempares>
inteiro: V[20],i,c
inicio
c ←0
para i de 1 até 20 repita
leia (V[i])
Se (mod(V[í],2)=0) então
c ← c+1
fim se
fim para
escreva (c)
fim.
Vetores
Algoritmo 7 – Escreva um algoritmo que leia um
vetor de 50 posições de números inteiros e mostre
somente os positivos
Algoritmo <positivos>
inteiro:V[50], i
inicio
para i de 1 até 50 repita
leia (V[i])
se (V[i]>0) então
escreva (V[i])
fim se
fim para
fim.
Vetores
Algoritmo 8 – Escreva um algoritmo que leia um
vetor de 80 elementos inteiros, encontre e mostre o
menor elemento e sua posição no vetor.
Algoritmo <menorelemento>
inteiro:V[80], i, ind,menor
inicio
leia (V[1])
menorV[1]
ind1
para i de 2 até 80 repita
leia (V[i])
se (V[i]<menor) então
menorV[i]
indi
fim se
fim para
Vetores
Algoritmo 9 – Faça um algoritmo que leia um
conjunto de 10 valores inteiros e os coloque em dois
vetores conforme forem pares ou ímpares.
Algoritmo <doisvetores>
inteiro:V[10], V1[10],V2[10],i,c1,c2
inicio
c1
 c2
 para i de 1 até 10 repita
leia (V[i])
se (mod(V[i],2)=0) então
V1[c1]V[i]
c1c1+1
senão
V2[c2]V[i]
c2 c2

fim se
fim para
fim.
Vetores
Algoritmo 10 – Escreva um algoritmo que leia um vetor G de
20 elementos literais que representa o gabarito de uma
prova. A seguir para cada um dos 50 alunos da turma, leia o
vetor de respostas R do aluno. Mostre o número de acertos
do aluno e uma mensagem APROVADO, se a nota for maior
ou igual a 6; e uma mensagem de REPROVADO, caso
contrário.
Vetores
Algoritmo <prova>
notaacertos*0.5
literal:G[20], R[20]
se (nota>=6) então
inteiro:i,j,acertos
escreva (“APROVADO”)
inicio
senão
para i de 1 até 20 repita
escreva(“REPROVADO”)
leia (G[i])
fim para
fim se
para j de 1 até 50 repita
fim para
acertos ← 0
fim
Para i de 1 até 20 repita
leia R[i]
se (R[i]=G[i]) então
acertos ← acertos+1
fim se
fim para
Vetores
Algoritmo 11 – Faça um algoritmo que leia o código
numérico inteiro e um vetor de 50 posições de
números reais. Se o código for 0 termine o
algoritmo, se for 1, mostre o vetor na ordem direta,
e se for 2, mostre o vetor na ordem inversa.
Vetores
Algoritmo <opcoes>
inteiro:i,codigo
real: vetor[50]
inicio
leia (codigo)
se (codigo>0 e codigo<=2) então
para i de 1 até 50 repita
leia (vetor[i])
fim para
se (codigo=1) então
para i de 1 até 50 repita
escreva (vetor[i])
fim para
senão
para i de 50 até 1 passo -1 repita
escreva (vetor [i])
fim para
fim se
fim se
Vetores
Algoritmo 12 – Uma locadora de vídeos tem
guardada, em um arquivo manual, a quantidade de
filmes retirados por cliente durante o ano de 2007.
Faça um algoritmo que
(a) leia um vetor de 500 posições para guardar esta
informação e
(b) crie um outro vetor contendo a quantidade de
locações gratuitas a que cada cliente tem direito,
considerando que a locadora está fazendo uma
promoção e para cada 10 filmes retirados ganha-se
uma locação grátis.
Vetores
Algoritmo <locadora>
inteiro:i,locacoes[500],gratuitas[500]
inicio
para i de 1 até 500 repita
leia (locacoes[i])
gratuitas[i] ← DIV(locacoes[i],10)
fim para
fim
Vetores
Algoritmo 13 – Dado um polinômio P(x) de grau n,
da forma
P(x) = a0xn + a1xn-1 + ... + an-1x + an,
onde a0, a1, ..., an (reais) são os coeficientes do
polinômio. Faça um algoritmo para ler:
(a)n (o grau do polinômio), n<=100
(b)os coeficientes a0, a1, ..., an e
(c)uma seqüência de 5 valores para x.
O algoritmo deve calcular o valor de P(x) para cada
valor de x.
Vetores
Algoritmo <polinomio>
inteiro:i,n
real: a[101],x
início
leia (n)
para i de 1 até n+1 repita
leia a[i]
fim para
para j de 1 até 5 repita
leia x
Px ← 0
para i de 1 até n+1 repita
Px ← Px+ a[i]*x**(n-i+1)
fim para
escreva (x,Px)
fim para
fim
Vetores
Algoritmo 14 – Escrever um algoritmo que faça a
reserva de passagens aéreas de uma companhia.
Além da leitura do número dos vôos e quantidade de
lugares disponíveis, ler vários pedidos de reserva,
constituídos do número de carteira de identidade do
cliente e do número de vôo desejado.
Para cada cliente, verificar se há disponibilidade no
vôo desejado. Em caso afirmativo, imprimir o
número da identidade do cliente, e o número de vôo,
atualizando o número de lugares disponíveis. Caso
contrário, avisar ao cliente da inexistência de
lugares.
Indicando o fim dos pedidos de reserva, existe um
passageiro cujo número de carteira de identidade é
9999. Considerar fixo e igual a 37 o número de vôos
da companhia.
Algoritmo <reservapassagens>
inteiro:i,voos[37],disp[37],cliente,nvoo
início
Para i de 1 até 37 repita
leia (voos[i],disp[i])
Fim Para
leia cliente
enquanto cliente<>9999 faça
leia nvoo
i←0
repita
i ← i+1
até que (i=37 ou voos[i]=nvoo)
se (voos[i]=nvoo) então
se (disp[i]>0) então
escreva (cliente,nvoo)
disp[i] ← disp[i]-1
senão
escreva (nvoo, “lotado”)
fim se
senão
escreva (“voo inexistente”)
fim se
leia cliente
fim enquanto
fim
Vetores
Algoritmo 15 – Faça um algoritmo que leia um vetor
de 20 inteiros e o coloque em ordem crescente,
utilizando a seguinte estratégia de ordenação:
•Selecione o elemento do vetor de 20 posições que
apresente o menor valor.
•Troque este elemento pelo primeiro.
•Repita estas operações, envolvendo agora apenas os
19 elementos restantes (trocando o de menor valor
com a segunda posição), depois os 18 elementos
(trocando o de menor valor com a terceira posição),
depois os 17,16 e assim por diante, até restar um
único elemento, o maior deles.
Vetores
Algoritmo <ordemcrescente>
inteiro:i,j,vetor[20]
inicio
para i de 1 até 19 repita
inter ← 0
menor ← vetor[i]
indice ← i
para j de i+1 até 20 repita
se (vetor[j] < menor ) então
menor ← vetor[j]
indice ← j
inter ← 1
fim se
fim para
se (inter=1) então
vetor[indice] ← vetor[i]
vetor[i] ← menor
fim se
fim para
Vetores
Algoritmo 16 – Desenvolva um algoritmo que leia um
vetor de 20 posições inteiras e o coloque em ordem
crescente, utilizando como estratégia de ordenação a
comparação de pares de elementos adjacentes,
permutando-os quando estiverem fora de ordem até
que todos estejam ordenados.
Vetores
Algoritmo <ordemcrescente2>
inteiro:i,j,t,vetor[20]
inicio
para i de 2 até 20 repita
para j de 20 até i passo -1 repita
se (vetor[j-1] > vetor[j] ) então
t ← vetor[j-1]
vetor[j-1] ← vetor[j]
vetor[j] ← t
fim se
fim para
fim para
fim
Vetores
Algoritmo 17 – Desenvolva um algoritmo que leia um
vetor de 20 posições inteiras e o coloque em ordem
crescente, utilizando como estratégia de ordenação
inserir um elemento n num vetor já ordenado de n-1
elementos.
Vetores
Algoritmo <ordemcrescente3>
inteiro:i,j,elemento,vetor[20]
inicio
para i de 2 até 20 repita
elemento ←vetor[j]
i ←j-1
enquanto (i>0 e vetor[i]>elemento)
vetor[i+1] ← vetor[i]
i ← i-1
fim enquanto
vetor[i+1] ← elemento
fim para
fim