ATP-Aulas02-03-VariaveisCompostasHomogeneas

Prévia do material em texto

Algoritmos e Técnicas de 
Programação
Aula 02: Estruturas de Dados Sequenciais
(Parte I)
2
Plano de Aula
� Variáveis Compostas Homogêneas 
(Matrizes)
� Introdução
� Matrizes Unidimensionais (Vetor)
� Matrizes Multidimensionais 
� Exercícios
3
Indrodução
� Problemas Simples ⇒ Número pequeno 
(gerenciável) e determinado de variáveis
� Área de um triângulo
� Area = (Base * Altura) / 2
� Indice de Massa Corporal
� IMC = Peso / (Altura ^ 2)
� Média das 2 Melhores Notas de 3 Avaliações
� Med = (Soma(N1,N2,N3) – Min(N1,N2,N3))/2
4
Indrodução
� Em problemas como os anteriores, cada 
variável é declarada individualmente 
conforme o tipo e a faixa de valores que a 
variável deve assumir
� Número inteiro com faixa de valores de acordo 
com a plataforma (16, 32 ou 64 bits)
� int i, j;
� Número reais (ponto flutuante):
� float x; //precisão simples (7 dígitos decimais)
� double y; //precisão dupla (15 dígitos decimais)
5
Introdução
� Problemas com muitas variáveis
� Preciptação pluviométrica (milímetros de chuva) 
diária ao longo de um ano
� Declarar 366 variáveis (p1, p2, …, p366)?
� Usuários de um laboratório ou equipamento, 
funcionando de 07:00 às 23:00h, de segunda à
sábado
� Declarar (7-2+1)*(23-7+1) = 102 variáveis?
6
Introdução
� Problemas com número mutável de variáveis
� Média aritmética das notas de 30 alunos
� Incluir ou excluir variáveis se o número de alunos 
aumentar ou diminuir?
� Folha de pagamento de uma empresa com 50 
funcionários:
� Incluir ou excluir variáveis quando houver admissões ou 
demissões?
7
Introdução
� RESPOSTA:
� ÓBVIA E FELIZMENTE, NÃO é a resposta para 
todas as perguntas acima!
� SOLUÇÃO: 
� Declarar uma MATRIZ, (Variável Composta 
Homogênea, ou agregado homogêneo)
8
MATRIZ (Var. Comp. Homogênea)
� Uma matriz é um conjunto de variáveis do mesmo 
tipo que são referenciadas por: 
� um NOME comum: o identificador da matriz; e
� um ÍNDICE: número inteiro que designa a posição de cada 
variável.
� Em linguagens de programação como Pascal e C 
(entre outras) todas as matrizes consistem em 
posições contíguas ou adjacentes na memória:
� a variável de índice k, fica imediatamente após a de índice 
k-1 e imediatamente antes daquela de indice k+1
9
Matrizes 1D e 2D
� Uma matriz pode ser:
� Unidimensional (1D): Vetor (vetor algébrico)
� Exemplo: vetor “V” com 6 elementos: 1x6
� Bidimensional (2D): Matriz (matriz algébrica)
� Exemplo: matriz “M” com 6 elementos: 2x3
 V[0] V[1] V[2] V[3] V[4] V[5] 
 
 
V
M
 M[0,0] M[0,1] M[0,2] M[1,0] M[1,1] V[1,2] 
 
 1º Vetor: M[0] 2º Vetor: M[1] 
 
10
Matrizes Multidimensionais (3D, 4D…)
� Em C e em outras linguagens de 
programação é possível declarar matrizes 
multidimensionais, ou seja, com quantas 
dimensões se queira.
� Na prática matrizes com mais de 3 
dimensões implicam em:
� código menos legível 
� código mais susceptível a erros 
� código menos eficiente, devido à aritmética 
inerente a cada índice
11
Matrizes 1D em C
� Declaração: Sintaxe
� tipo identificador[tamanho];
tipo: qualquer tipo já conhecido do compilador
Identificador: nome da matriz
tamanho: número de elementos da matriz (≥1)
� Exemplos
char s[6]; //s: vetor de até 6 caracteres
int v[8]; //v: vetor de até 8 inteiros
float p[3]; //p: vetor de até 3 reais
12
Matrizes 1D em C
� Declaração e inicialização de vetores
� Tipo Nome[N] = {v0, v1, …, vN-1};
ou
� Tipo Nome[] = {v0, v1, …, vN-1}; 
Tipo: qualquer tipo já conhecido do compilador
Nome: identificador da matriz
N: número de elementos da matriz
� Exemplos:
char s[4] = {'A', 'T', 'P', '\0'};
int v[5] = {12, 0, -45, 8, 31};
float p[3] {3.14, -2.4, 9.81};
13
Exercício 1
� Declare um vetor (matriz 1D) com capacidade 
para 25 inteiros;
� Gere e armazene no vetor os quadrados dos 
20 primeiros inteiros positivos;
� Mostre na tela os quadrados dos 20 primeiros 
inteiros positivos armazenados no vetor.
14
Solução 1
//1o void: main não retorna valor 
//2o void: main não aceitará parâmetros
void main(void)
{
int v[25]; //declara o vetor v com 25 int.
int i;
//Armazena os 20 primeiros quadrados
for (i=0; i<20; i++)
v[i] = (i+1)*(i+1);
//Imprime os 20 primeiros quadrados
for (i=0; i<20; i++)
printf("%2d: %d\n", i, v[i]);
}
15
Exercício 2
� Declare 2 vetores (“a”, “b”) com capacidade 
para armazenar 6 inteiros, inicializando “a” com 
os valores (2, 3, 5, 7, 11, 13). Implemente 
código para copiar os valores de “a” para “b”, na 
ordem invertida: (13, 11, 7, 5, 3, 2) 
16
Solução 2
void main(void)
{
int i;
//O tamanho do vetor "a" é definido pelo compilador!
int a[] = {2, 3, 5, 7, 11, 13};
int b[6];
for(i=0; i<6; i++)
b[i] = a[5-i];
for (i=0; i<6; i++)
printf("%d: %d\n", i, b[i]);
}
17
Exercício 3
� Declare um vetor v de caracteres e pré-inicialize-o
com os caracteres da palavra “algoritmo”; a 
seguir, inverta a ordem dos caracteres dentro do 
vetor: o m t i r o g l a; 
� Sugestão: utilize um índice i começando em 0 e outro j
começando 8; enquanto i for menor que j, troque v[i]
com v[j], incremente i e decremente j. 
� Para verificar o resultado da inversão, imprima os 
caracteres da esquerda para a direita para obter: 
omtirogla.
18
Solução 3
#include <stdio.h>
#include <stdlib.h>
void main(void)
{ char v[10] = {'a','l','g','o','r','i','t','m','o', '\0'};
int i, j;
char t; //auxiliar para a troca
i = 0;
j = 8;
while (i < j)
{
t = v[i];
v[i] = v[j];
v[j] = t;
i++;
j--;
}
//continua...
19
Solução 3 (cont.)
//2a parte: impressão
for (i=0; i<10; i++)
printf("%c", v[i]);
printf("\n\n");
system("pause");
}
20
Passagem de Parâmetros para Funções em C
� Denominam-se parâmetros formais de uma função os 
parâmetros (ou argumentos) que aparecem entre 
parênteses logo após o nome da função:
� Exemplo:
int func(int a, int* b)
Os parâmetros formais de “func” são “a” e “b”:
� “a” é um parâmetro passado por valor: é o endereço de uma 
cópia (na pilha de execução) do valor de uma variável inteira 
ou literal inteiro.
� “b” é um parâmetro passado por referência: (um ponteiro do 
tipo inteiro que “guarda” o endereço de uma variável inteira)
� ponteiro é uma variável que armazena endereços de memória
(variável, função, ou qualquer outro endereço)
21
Vetores Como Parâmetros de Funções
� Vetores (e quaisquer matrizes) são passados
implicitamente por referência, SEMPRESEMPRE!
� Exemplo:
void ZeraVetor(int v[], int n)
{
int i;
for(i=0; i<n; i++)
v[i] = 0;
}
� v é um ponteiro por se tratar de um vetor e é
implícito pela ausência do * (símbolo que define 
ponteiros, explicitamente)
22
Vetores Como Parâmetros de Funções
� Embora incomum, é possível usar no cabeçalho da 
função um inteiro literal entre colchetes (como se 
fosse o número de elementos):
void ZeraVetor(int v[10], int n)
void ZeraVetor(int v[99], int n)
� Este número é ignorado pelo compilador, pois o 
parâmetro v é um ponteiro para o 1º elemento de 
um vetor, não importando sua capacidade.
� É uma boa prática passar o número elementos (n) a 
ser processado como um parâmetro da função. 
� Isso confere independência e generalidade à função!
23
Exemplo Completo:
#include <stdio.h>
//zera parcialmente n elementos de um vetor v, com QQ tam.
void ZeraVetor(int v[], int n)
{
int i;
for(i=0; i<n; i++)
v[i] = 0;
}
void main(void)
{ int a[5];
int b[8];
ZeraVetor(a, 5);
ZeraVetor(b, 8);
//outros processamentos...
}
24
Exercício 4
� Implemente em C uma função denominada 
SomaVetores, que calcule a soma dos vetores 
a e b (passadoscomo parâmetros), contendo 
n inteiros, e armazene o vetor resultante (a+b) 
em c, também passado como parâmetro. 
� Entrada: a, b e n
� Processamento: ci = ai + bi, para i = 0, 1, ..., n-1
� Saida: c
25
Solução 4: Parcial - Somente Módulo ou 
Função
� A função abaixo é genérica: permite somar vetores 
de inteiros, com qualquer capacidade. Obviamente 
a e b devem ter o mesmo número de elementos 
(mesmo com capacidades diferentes) e c deve ter 
capacidade suficiente para todos os elementos. 
void SomaVetores(int a[], int b[], int c[], int n)
{
int i;
for(i=0; i<n; i++)
c[i] = a[i] + b[i];
}
26
Solução Mais Completa: Integração da 
função a um programa
#include <stdio.h>
#include <stdlib.h>
void SomaVetores(int a[], int b[], int c[], int n){
int i;
for(i=0; i<n; i++)
c[i] = a[i] + b[i];
}
void main(void){
int x[5] = {13, 45, 18, 32}; //o último elem. fica indefinido
int y[8] = {17, 11, 12, 16}; //o restante fica indefinidos
int z[6];
int i;
//x, y e z têm capac. diferentes mas usam apenas 4 elem.
SomaVetores(x, y, z, 4);
}
27
Matrizes 2D em C
� Declaração: Sintaxe
� Tipo Identificador[Lin][Col];
Tipo: qualquer tipo já conhecido do compilador
Identificador: nome da matriz
Lin: número de linhas da matriz
Col: número de colunas da matriz
� Uma Matriz 2D (Lin x Col) pode ser vista como 
um vetor de “Lin” vetores de “Col” elementos.
� O arranjo é 2D dos elementos é mera abstração, 
pois a memória é linear (outra abstração!)
28
Matriz 2D
� Exemplos:
� Matriz 2 x 3 ⇒ tipo M[2][3]
� Matriz 3 x 2 ⇒ tipo M[3][2]
 M[0][0] M[0][1] M[0][2] M[1][0] M[1][1] M[1][2] 
 
 1º Vetor: M[0] 2º Vetor: M[1] 
 
 M[0][0] M[0][1] M[1][0] M[1][1] M[2][0] M[1][1] 
 
 M[0] M[1] M[2] 
 
29
Matrizes 2D em C
� Declaração e inicialização de matrizes 2D
� Exemplo
int v[3][4] =
{{11, 12, 13, 14},
{21, 22, 23, 24},
{31, 32, 33, 34}
};
tipo Nome[L][C] = 
{{v0,0,v0,1,…v0,C-1}, 
{v1,0,v1,1,…v1,C-1}, 
…,
{vL-1,0,vL-1,1,…vL-1,C-1}};
11 12 13 14
21 22 23 24
31 32 33 34
 
 
 
 
 
30
Matrizes como Argumento de funções
� Em C, ao declarar uma função cujo 
argumento é uma matriz, pode-se omitir a 
primeira dimensão, mas todas as demais 
dimensões devem ser declaradas
� suponha a matriz: int m[4][5]
� Uma função que deva receber esta matriz como 
argumento pode ser declarada como:
� void func(int a[ ][5]); ou
� void func(int a[4][5]);
31
Exercício 5
� Implemente uma função para gerar uma matriz 
identidade (A) de ordem 3, com elementos 
inteiros. Uma matriz identidade é quadrada 
(número de linhas igual ao de colunas), onde os 
elementos da diagonal principal (Aii) são iguais à
unidade e todos os demais são nulos:
1 0 0
0 1 0
0 0 1
A
 
 
=  
 
 
32
Solução 5
void MatrizIdent3x3(int A[3][3]){
int i, j;
for (i=0; i<3; i++)
for (j=0; j<3; j++)
if (i==j)
A[i][j] = 1;
else
A[i][j] = 0;
}
33
Exercício 6
� Implemente uma função que retorne 1 caso uma 
matriz A (4x4) simétrica (Aij = Aji) ou 0 caso 
contrário.
34
Solução 6
int MatrizSimetrica4x4(int a[4][4]){
int i, j;
for (i=0; i<4; i++)
for (j=0; j<4; j++)
if (a[i][j] != a[j][i]) //não simétrica
return 0; //sai da função com falso
//se veio até aqui, seguramemente é simétrica
return 1;
}
35
Exercício 7
� Declare uma Matriz 3x4 de inteiros e 
implemente:
� a) código para preencher seus elementos com 
inteiros aleatórios entre 0 e 19, usando rand() e 
obtendo o resto da divisão por 20: 
� rand() % 20;
� b) uma função para mostrar a matriz na tela, no 
formato tradicional (linha por linha).
36
Solução 7
void GeraMatrizAleaoria3x4(int a[3][4]){
int i, j;
for (i=0; i<3; i++)
for (j=0; j<4; j++)
a[i][j] = rand() % 20; // 0 <= rand() < 2^31=2.147.483.648
}
void MostraMatriz3x4(int A[3][4]){
int i, j;
for (i=0; i<3; i++) {
for (j=0; j<4; j++)
printf("%4d", A[i][j]);
printf("\n"); //salta para a próxima nova linha
}
}
37
Limitações das funções de processamento 
de Matrizes 2D Anteriores
� Vejamos o cabeçalho da função MostraMatriz3x4, 
do exemplo anterior:
void MostraMatriz3x4(int A[3][4])
� Esta função só opera corretamente se o parâmetro 
for uma matriz 3 linhas x 4 colunas, declaradas 
como:
int m[3][4];
� Se precisássemos mostrar matrizes 3x3, 4x3 e 4x4
(entre outras) em um mesmo programa, teríamos que 
implementar uma função “MostraMatriz?x?” sob 
medida para cada capacidade da matriz?
� Felizmente, NÃO!
38
Bases para a generalização...
� Como vimos, uma função pode processar um vetor 
de qualquer capacidade, bastando lhe passar o 
número de elementos (n):
void Processa(TipoElem v[], int n)
� A função pode fazer isso porque v é um ponteiro para o 
primeiro elemento (v[0]) e o tamanho de cada elemento 
“TipoElem” é conhecido em tempo de compilação. 
� Portanto, um elemento v[k] está a k * sizeof(TipoElem) 
bytes após v[0] ou v.
�� ConclusãoConclusão: o tamanho e o endereço do primeiro 
elemento permitem localizar qualquer outro na memória.
39
Bases para a generalização...
� Na realidade, uma matriz m x n é um vetor de m linhas, 
e cada uma delas é um vetor de n colunas:
00 01 0 1
10 11 1 1
1,0 1,1 1, 1
n
n
m m m n mxn
a a a
a a a
a a a
−
−
− − − −
 
 
 
 
  
 
�
�
� � � �
�
( ) ( ) ( )( )00 01 0 1 10 11 1 1 1,0 1,1 1, 1n n m m m na a a a a a a a a− − − − − −� � � �
40
Bases para a generalização...
� Como a matriz é um vetor de linhas, o endereço de uma 
linha i está deslocado de i x TamLin (tamanho da linha) 
bytes em relação ao endereço base da matriz: 
( ) ( ) ( )( )00 01 0 1 10 11 1 1 20 21 2 1n n na a a a a a a a a− − −� � � �
M [0] = M M [2]
M [2] = M [0] + 2 x TamLin
TamLin = n x TamElem TamElem
41
Bases para a generalização...
� Com exceção da capacidade associada à primeira dimensão da 
matriz, o compilador requer todas as demais, caso contrário o 
tamanho do elemento não poderia ser determinado!
� Podemos declarar:
void (TipoElem v[], int n)
void (TipoElem v[][5], int n)
� Mas NÃO podemos declarar:
void (TipoElem v[][], int n) //Errado!
� Portanto, se passarmos uma matriz 2D como parâmetro, o número 
de colunas terá que ser informado de modo literal, ou seja:
� O código gerado pelo compilador só processará corretamente 
matrizes com esse número de colunas, independentemente de 
quantas linhas tenham.
42
Solução para a Generalização
� A solução consiste em passar como parâmetros 
para a função:
� a matriz 2D como um vetor (matriz 1D) 
� o número máximo (capacidade) de colunas: Nx
� o número real de colunas n (≤ Nx), além de m (número de 
linhas do vetor).
� Portanto, o cálculo do início de cada linha (antes 
feito automaticamente pelo compilador) agora terá
que ser explicitamente feito pelo programador, com 
pouco trabalho a mais, como se verá.
43
Exemplo
� Implementar uma função para mostrar uma 
matriz 2D de qualquer capacidade no 
formato tradicional (linhas x colunas)
44
Solução do Exemplo
//Mostra uma matriz 2D com até "Nx" colunas
//contendo "m" linhas e "n" colunas
void MostraMatriz(int a[], int Nx, int m, int n)
{
int i, j;
for (i=0; i<m; i++) {
for (j=0; j<n; j++)
printf("%4d", a[i*Nx+j]);//em vez de A[i][j]
//A[i*Nx] = início da linha i na memória
printf("\n"); //começa nova linha
}
}
45
Solução do Exemplo - Continuação
� Eis um exemplo de como a função MostraMatriz pode ser 
chamada:
void main(){
int A[5][8], I[3][3] = {{1, 0, 0}, {0, 1, 0},
{0, 0, 1}};
int n, m;
LeiaMatriz(A, &m, &n);
//Mostra A, com m linhas x ncolunas
//Obviamente, m <= 5 e n <= 8
MostraMatriz(A[0], 8, m, n);
//Mostra a matriz Identidade 3x3
MostraMatriz(I[0], 3, 3, 3);
system("pause");
}
46
Solução do Exemplo - Continuação
//Mostra uma matriz 2D com até "Nx" colunas
//contendo "m" linhas e "n" colunas
void MostraMatriz(int a[], int Nx, int m, int n)
{
int i, j;
for (i=0; i<m; i++) {
for (j=0; j<n; j++)
printf("%4d", a[i*Nx+j]);
//A[i*Nx] = início da linha i na memória
printf("\n"); //começa nova linha
}
}
47
Exercício 8
� Implementar uma função para gerar uma 
Matriz Identidade de qualquer ordem:
� Solução:
void MatrizIdent(int A[], int Nx, int ordem){
int i, j;
for (i=0; i<ordem; i++)
for (j=0; j<ordem; j++)
if (i==j)
A[i*Nx+j] = 1; //em vez de A[i][j]
else
A[i*Nx+j] = 0;
}
48
Exercício 9
� Considere a função “MatrizIdent” da solução anterior e a 
função “main” abaixo:
void main(){
int a[4][3];
MatrizIdent(a[0], 3, 2);
MatrizIdent(a[0], 3, 3);
MatrizIdent(a[0], 2, 2);
}
� Esboce graficamente como ficaria sequencia de 0s e 1s na 
memória, após cada uma das três chamadas de 
“MatrizIdent”. Use um arranjo linear, tal qual abaixo:
⋅ ⋅ ⋅ ⋅ ⋅ ⋅
a
49
Solução:
� MatrizIdent(a[0], 3, 2);
� MatrizIdent(a[0], 3, 3);
� MatrizIdent(a[0], 2, 2);
⋅ ⋅ ⋅ 1 0 0 1 ⋅ ⋅ ⋅
a
⋅ ⋅ ⋅ 1 0 0 0 1 0 0 0 1 ⋅ ⋅ ⋅
a
⋅ ⋅ ⋅ 1 0 0 1 ⋅ ⋅ ⋅
a