Algoritmos e Estruturas de Dados I – Estruturas de Dados

Algoritmos e Estruturas de Algoritmos e Estruturas de Dados I – Estruturas de DadosDados I – Estruturas de Dados

Profa. Mercedes Gonzales Márquez

Estruturas de DadosEstruturas de Dados

•Os tipos primitivos (inteiro, real, literal e Os tipos primitivos (inteiro, real, literal e lógico) não são suficientes para representar lógico) não são suficientes para representar todos os tipos de informação.todos os tipos de informação.•Particularmente quando temos mais de Particularmente quando temos mais de uma informação relacionada. Ex: Lista dos uma informação relacionada. Ex: Lista dos nomes dos alunos de uma sala, endereço de nomes dos alunos de uma sala, endereço de alguém etc.alguém etc.•Utilizaremos os tipos primitivos para Utilizaremos os tipos primitivos para construirconstruir outras estruturas de dados mais outras estruturas de dados mais complexas.complexas.

VetoresVetores• Também denominados Também denominados Estruturas compostas Estruturas compostas

homogêneas homogêneas uniunidimensionaisdimensionais• Permitem a manipulação de um conjunto de Permitem a manipulação de um conjunto de

informações de um mesmo tipo primitivoinformações de um mesmo tipo primitivo◦ Declaração :Declaração :tipotipo primitivo : nome_ primitivo : nome_vetorvetor [numero de elementos] [numero de elementos]

◦ Exemplo :Exemplo :Um vetor com nome “dados” de 40 posições reais Um vetor com nome “dados” de 40 posições reais terá a seguinte declaração.terá a seguinte declaração.

Real: dados[40]Real: dados[40]

1 2 3 4 5 6 7 8 9 38 39 40

6,57,8 5,3

dados

9,89,1 4,77,87,8 3,62,4 9,8 1,5 2,8 4,6

VetoresVetores◦ Manipulação:Manipulação:

Para manipular os elementos de um vetor Para manipular os elementos de um vetor devemos especificar a sua posição.devemos especificar a sua posição.

1 2 3 4 5 6 7 8 9 38 39 40

6,57,8 5,3

dados

9,89,1 4,77,87,8 3,62,4 9,8 1,5 2,8 4,6

--dados[8]dados[8]

• A posição do vetor é determinada por meio de uma A posição do vetor é determinada por meio de uma constante, de uma expressão aritmética ou de uma constante, de uma expressão aritmética ou de uma variável que estiver dentro dos colchetes. Ela é variável que estiver dentro dos colchetes. Ela é também chamada de índice.também chamada de índice.

VetoresVetores

Exercício – Sendo o vetor v igual a

1 2 3 4 5 6 7 8 9 10

17,8 3 910 147,86 82 21 33

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]

VetoresVetores

inteiro: va[50],vb[50],vc[50],iiniciopara i de 1 até 50 repita

leia (va[i],vb[i] )vc[i] ← va[i] + vb[i]escreva (vc[i])

fimparafim.

Algoritmo 2 – Leia dois vetores inteiros de 50 posições, some seus correspondentes elementos e imprima o resultado da soma

VetoresVetoresAlgoritmo 3 – Preencha um vetor de 100 inteiros, colocando 1 na posição par e 0 na posição impar

inteiro: vetor[100],iiniciopara i de 1 até 100 repita

se (mod(i,2)=0) entãovetor[i] ← 1

senãovetor[i] ← 0

fimpara;fim.

VetoresVetoresAlgoritmo 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: ireal: V[20],a[20],b[20]iniciopara i de 1 até 20 repita

V[i] ← a[i]*b[21-i]fim para

fim.

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.

VetoresVetores

Algoritmo <produto2>real: V[20],a[20],b[20]inteiro: iiniciopara 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 parafim.

Algoritmo 6 – Escreva uma algoritmo que leia um vetor de 20 elementos e conte quantos valores pares existem no vetor.

VetoresVetores

Algoritmo <contagempares>inteiro: V[20],i,cinicio

c ←0para i de 1 até 20 repita

leia (V[i])Se (mod(V[i],2)=0) então

c ← c+1fim se

fim paraescreva (c)

fim.

Algoritmo 7 – Escreva um algoritmo que leia um vetor de 50 posições de números inteiros e mostre somente os positivos

VetoresVetores

Algoritmo <positivos>inteiro:V[50], iiniciopara i de 1 até 50 repita

leia (V[i])se (V[i]>0) então

escreva (V[i])fim se

fim parafim.

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.

VetoresVetores

Algoritmo <menorelemento>inteiro:V[80], i, ind,menorinicio

leia (V[1])menorV[1]ind1para i de 2 até 80 repita

leia (V[i])se (V[i]<menor) então

menorV[i]indi

fim sefim para

fim.

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.

VetoresVetores

Algoritmo <doisvetores>inteiro:V[10], V1[10],V2[10],i,c1,c2inicio

c1c2para i de 1 até 10 repita

leia (V[i])se (mod(V[i],2)=0) então

V1[c1]V[i]c1c1+1

senãoV2[c2]V[i]c2 c2

fim sefim para

fim.

Algoritmo 10 – Ler um vetor v de 10 elementos inteiros e obter um vetor fat cujos componentes são os fatoriais dos respectivos componentes de v.

VetoresVetores

Algoritmo <doisvetores>inteiro:v[10], fat[10],i,jinicio

para i de 1 até 10 repitaleia (v[i])fat[i]1Para j de 1 até v[i] repita

fat[i]fat[i]*jFim Para

fim.

Algoritmo 11 – 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.

VetoresVetores

VetoresVetores

Algoritmo <prova>literal:G[20], R[20]inteiro:i,j,acertosinicio

para i de 1 até 20 repitaleia (G[i])

fim parapara j de 1 até 50 repita

acertos ← 0Para i de 1 até 20 repita

leia R[i]se (R[i]=G[i]) então

acertos ← acertos+1

fim sefim para

notaacertos*0.5se (nota>=6) então

escreva (“APROVADO”)senão

escreva(“REPROVADO”)

fim sefim para

fim

Algoritmo 12 – Faça um algoritmo que leia um 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.

VetoresVetores

VetoresVetoresAlgoritmo <opcoes>inteiro:i,codigoreal: vetor[50]inicio

leia (codigo)se (codigo>0 e codigo<=2) então

para i de 1 até 50 repitaleia (vetor[i])

fim parase (codigo=1) então

para i de 1 até 50 repitaescreva (vetor[i])

fim parasenão

para i de 50 até 1 passo -1 repitaescreva (vetor [i])

fim parafim se

fim sefim

Algoritmo 13 – Faça um algoritmo que leia dois conjuntos de números inteiros tendo cada um 20 elementos e apresente os elementos comuns (interseção de conjuntos).

VetoresVetores

VetoresVetoresAlgoritmo <intersecao>

real: a[20], b[20], c[20]inteiro: i, j, kInicio

Para i de 1 até 20 repita Leia( a[i] ,b[i])

Fim_para k ← 0

Para i de 1 até 20 repita Para j de 1 até 20 repita

Se( a[i] = b[j] ) então k ← k+1 c[k] ← a[i]

Fim_se Fim_para

Fim_para

Se ( k=0 ) então Escreva(“Interseção Vazia. “)

Senão Escreva(“Conjunto Interseção:”)

Fim se Para i de 1 até k repita

Escreva( c[i] ) Fim_para

Fim_se Fim

Obs. Com este algoritmo, se houver elementos repetidos, também se repetirão na saída. Como evitar isso?  

Algoritmo 14 – 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.

VetoresVetores

VetoresVetores

Algoritmo <locadora>inteiro:i,locacoes[500],gratuitas[500]iniciopara i de 1 até 500 repita

leia (locacoes[i])gratuitas[i] ← DIV(locacoes[i],10)

fim parafim

Algoritmo 15 – 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 sequência de 5 valores para x.

O algoritmo deve calcular o valor de P(x) para cada valor de x.

VetoresVetores

Algoritmo <polinomio>inteiro:i,nreal: a[101],xinício

leia (n)para i de 1 até n+1 repita

leia a[i]fim parapara j de 1 até 5 repita

leia xPx ← 0para i de 1 até n+1 repita

Px ← Px+ a[i]*x**(n-i+1)fim paraescreva (x,Px)

fim parafim

VetoresVetores

Algoritmo 16 – 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.

VetoresVetores

Algoritmo <reservapassagens>inteiro:i,voos[37],disp[37],cliente,nvoo

inícioPara i de 1 até 37 repita

leia (voos[i],disp[i])Fim Paraleia clienteenquanto cliente<>9999 faça

leia nvooi ← 0repita

i ← i+1até que (i=37 ou voos[i]=nvoo)se (voos[i]=nvoo) então

se (disp[i]>0) entãoescreva (cliente,nvoo)disp[i] ← disp[i]-1

senãoescreva (nvoo, “lotado”)

fim sesenão

escreva (“voo inexistente”)fim seleia cliente

fim enquantofim

Algoritmo 17 – 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. Este algoritmo é conhecido como algoritmo de seleção.Animação emhttp://www.youtube.com/watch?feature=player_embedded&v=LuANFAXgQEw

VetoresVetores

VetoresVetoresAlgoritmo <ordemcrescente>inteiro:i,j,vetor[20]inicio

para i de 1 até 19 repitainter ← 0menor ← vetor[i]indice ← ipara j de i+1 até 20 repita

se (vetor[j] < menor ) entãomenor ← vetor[j]indice ← jinter ← 1

fim sefim parase (inter=1) então

vetor[indice] ← vetor[i]vetor[i] ← menor

fim sefim para

fim

VetoresVetores

Algoritmo <ordemcrescente>inteiro:i,j,vetor[20],aux,indiceinicio

Leia (n)para i de 1 até n-1 repita

indice ← ipara j de i+1 até n repita

se (vetor[j] < v[indice]) entãoindice ← j

fim sefim paraaux ← vetor[i]vetor[i] ← v[indice]vetor[indice] ← aux

fim parafim

Algoritmo 18 – Algoritmo 17 de forma mais simples e considerando n elementos (n<=20).

Algoritmo 19 – Desenvolva um algoritmo que leia um vetor de n posições inteiras (n<=20) 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 (Algoritmo da Bolha).(Animação emhttp://www.youtube.com/watch?feature=player_embedded&v=gWkvvsJHbwY)

VetoresVetores

VetoresVetoresAlgoritmo <ordemcrescente2>inteiro:i,j,aux,vetor[20]inicioLeia (n)para i de 1 até n-1 repita

para j de 1 até n-i repitase (vetor[j] > vetor[j+1] )

entãoaux ← vetor[j]vetor[j+1] ← vetor[j]vetor[j] ← aux

fim sefim para

fim parafim

Algoritmo 20 – Desenvolva um algoritmo que leia um vetor de n posições inteiras (n<=20) e o coloque em ordem crescente, utilizando como estratégia de ordenação inserir um elemento k num vetor já ordenado de  k-1 elementos.

VetoresVetores

VetoresVetoresAlgoritmo <ordemcrescente3>inteiro:i,j,elemento,vetor[20]inicioLeia (n)para j de 2 até n repita

elemento ←vetor[j]i ←j-1enquanto (i>0 e vetor[i]>elemento)

vetor[i+1] ← vetor[i]i ← i-1

fim enquantovetor[i+1] ← elemento

fim parafim

Tarefas:• Resolva a lista de exercícios propostos de

estrutura de repetição que estará disponível no dia 31/05 no site da disciplina.

VetoresVetores