View
0
Download
0
Category
Preview:
Citation preview
Linguagem C – vetores multidimensionais
IF61A/IF71A - Computação 1
Prof. Leonelo Almeida
Universidade Tecnológica Federal do Paraná
Até agora ...
• Introdução à linguagem C
▫ ...
▫ Operadores aritméticos, de comparação e lógicos
▫ Entrada e saída de dados
▫ Estruturas condicionais
▫ Estruturas de repetição
▫ Vetores
Aula de hoje
• Um programa para ler e armazenar as notas dos alunos de uma turma.
▫ Cada aluno fez 4 avaliações.
▫ Considere que uma turma pode ter até 50 alunos.
Aula de hoje
• Um programa para ler e armazenar as notas dos alunos de uma turma.
▫ Cada aluno fez 4 avaliações.
▫ Considere que uma turma pode ter até 50 alunos.
▫ Possível solução:
float nota1[50], nota2[50], nota3[50], nota4[50];
Aula de hoje
• E se fôssemos cadastrar todas as notas que o alunos tem durante a graduação?
▫ Suponha que sejam 200 notas
Aula de hoje
• E se fôssemos cadastrar todas as notas que o alunos tem durante a graduação?
▫ Suponha que sejam 200 notas
▫ Possível solução:
float nota1[50], nota2[50], ... , nota200[50];
▫ Cansativo, não?
Aula de hoje
Vetores multidimensionais
(Matrizes)
Vetores multidimensionais (Matrizes)
• São vetores que possuem duas ou mais dimensões
▫ São um conjunto de variáveis de um mesmo tipo de dado, tal como os vetores
Declaração de matrizes
<tipo> identificador [<linhas>][<colunas>];
0,0 0,1 0,2 ... 0, colunas-1
linhas-1,0 linhas-1,1 linhas-1,2 ... linhas-1, colunas-1
Declaração de matrizes
<tipo> identificador [<linhas>][<colunas>];
• Exemplo: float notas [50][200];
0,0 0,1 0,2 ... 0, 199
49,0 49,1 49,2 ... 49,199
Acessando matrizes
• Para acessar o valor de uma certa posição da matriz
▫ identificador [<linha>][<coluna>];
• Exemplo int nota[5][10];
int a;
nota[1][9] = 20;
a = nota[1][9];
Usando matrizes- Exemplo
int contL, contC, mat[5][10];
for (contL=0; contL<5; contL++) {
for (contC=0; contC<10; contC++) {
mat[contL][contC] = contL*contC;
printf(“%d”, mat[contL][contC]);
}
}
O que esse programa imprimirá quando for executado?
Matrizes multidimensionais
<tipo> identificador
[<dim0>][<dim1>][<dim2>]...[<dimN>];
• Exemplo de uso:
▫ Uma matriz para armazenar a quantidade de chuva em um dado dia, mês e ano: double chuva[31][12][3000];
chuva[23][3][1979] = 6.0;
Leitura de uma matriz
int matriz[4][4], i, j;
for (i = 0; i < 4; i++)
for (j = 0; j < 4; j++) {
printf ("Matriz[%d][%d]: ", i, j);
scanf ("%d", &matriz[i][j]);
}
Escrita de uma matriz
int matriz[4][4], i, j;
for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++)
printf ("%d ", matriz[i][j]);
printf ("\n");
}
Matriz de tamanho informado pelo
usuário #include <stdio.h>
#include <locale.h>
main() {
int linha, coluna, i, j;
printf("informe o número de linhas e colunas:");
scanf("%d%d", &linha, &coluna);
int mat[linha][coluna];
for (i=0; i<linha; i++)
for(j=0; j<coluna; j++) {
printf("informe a posição [%d, %d]", i+1, j+1);
scanf("%d",&mat[i][j]);
}
for (i=0; i<linha; i++) {
printf("\n");
for(j=0; j<coluna; j++)
printf("[%4d]", mat[i][j]);
}
}
Ordenação de vetores
• E se eu quisesse ordenar um vetor de 1000 inteiros?
Ordenação de vetores
• E se eu quisesse ordenar um vetor de 1000 inteiros?
• Há diversos algoritmos que solucionam esse problema
▫ Diferenças no desempenho:
Consumo de memória
Consumo de processamento
Ordenação de vetores
algoritmo melhor caso caso médio pior caso
bubble sort n n2 n2
insertion sort n n2 n2
selection sort n2 n2 n2
quick sort n*log n n*log n n2
merge sort n*log n n*log n n*log n
Custo em número de comparações
Insertion Sort
• Lógica do algoritmo:
▫ A cada passo, uma porção de 0 até i-1 do vetor já está ordenada.
▫ Devemos inserir o item da posição i na posição correta para deixar o vetor ordenado até a posição i.
▫ No passo seguinte consideramos que o vetor está ordenado até i.
Insertion Sort
• Exemplo: (5,3,2,1,90,6).
▫ O valor sublinhado representa onde está o índice i
▫ (5; 3; 2; 1; 90; 6) : vetor ordenado de 0 - 0.
▫ (3; 5; 2; 1; 90; 6) : vetor ordenado de 0 - 1.
▫ (2; 3; 5; 1; 90; 6) : vetor ordenado de 0 - 2.
▫ (1; 2; 3; 5; 90; 6) : vetor ordenado de 0 - 3.
▫ (1; 2; 3; 5; 90; 6) : vetor ordenado de 0 - 4.
▫ (1; 2; 3; 5; 6; 90) : vetor ordenado de 0 - 5.
Busca
Busca sequencial
• Lógica do algoritmo:
▫ Percorra todo o vetor comparando a chave com o valor de cada posição.
▫ Se for igual para alguma posição, então devolva esta posição.
▫ Se o vetor todo foi percorrido então devolva -1.
Busca binária • Requer que os valores estejam ordenados
• Lógica do algoritmo:
▫ Verifique se a chave de busca e igual ao valor da posição do meio do vetor.
▫ Caso seja igual, devolva esta posição.
▫ Caso o valor desta posição seja maior, então repita o processo, mas considere que o vetor tem metade do tamanho, indo até posição anterior a do meio.
▫ Caso o valor desta posição seja menor, então repita o processo mas considere que o vetor tem metade do tamanho e inicia na posição seguinte a do meio.
Atividades
1. Faça um programa que leia duas matrizes do tipo float 2x3 e imprima a soma delas.
2. Agora mude seu programa para que permita que o usuário escolha a operação que deseja fazer: soma, subtração e matriz oposta.
3. Faça um programa que, dada uma string informada pelo usuário, diga se ela é um palíndromo. Ex.: “saudavel leva duas”, “subi no onibus”
Atividades
4. Leia uma matriz de tamanho informado pelo usuário e imprima a sua transposta.
5. Calcule o determinante de uma matriz 2x2 informada pelo usuário.
6. Agora calcule o determinante de uma matriz 3x3 informada pelo usuário.
7. Agora calcule o determinante de uma matriz nxn informada pelo usuário.
Exercícios complementares
1. Faça um programa que ordene um vetor de inteiros. Utilize um dos métodos apresentados anteriormente.
2. Faça um programa que busque um valor dentro de um vetor de caracteres. O programa deve imprimir a posição do valor.
3. Agora suponha que o vetor possa conter valores iguais. Faça com que o programa retorne a quantidade de ocorrências e a posição da última ocorrência do valor buscado.
4. Faça um programa que implemente uma busca binária em um vetor de inteiros.
Recommended