Upload
zeke
View
61
Download
2
Embed Size (px)
DESCRIPTION
Profa. Mercedes Gonzales Márquez. Algoritmos e Estruturas de Dados I – Estruturas de Dados. 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 . - PowerPoint PPT Presentation
Citation preview
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