Matrizes em Algoritmos e Programação

Prévia do material em texto

Matrizes
Aula 14
Bárbara Purkott Cezar
1Faculdade de Computação
Universidade Federal de Mato Grosso do Sul
Algoritmos e Programação
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 1 / 28
Conteúdo da aula
1 Introdução
2 Definição, declaração e uso
3 Declaração e inicialização simultâneas
4 Exemplo
5 Exercícios
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 2 / 28
Introdução
I uma variável composta homogênea pode ter qualquer número de
dimensões
I as matrizes são variáveis compostas homogêneas bidimensionais
I a extensão de variáveis compostas homogêneas para três ou
mais dimensões é simples e imediata
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 3 / 28
Introdução
I uma variável composta homogênea pode ter qualquer número de
dimensões
I as matrizes são variáveis compostas homogêneas bidimensionais
I a extensão de variáveis compostas homogêneas para três ou
mais dimensões é simples e imediata
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 3 / 28
Introdução
I uma variável composta homogênea pode ter qualquer número de
dimensões
I as matrizes são variáveis compostas homogêneas bidimensionais
I a extensão de variáveis compostas homogêneas para três ou
mais dimensões é simples e imediata
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 3 / 28
Definição, declaração e uso
I na matemática, uma matriz é uma tabela ou um quadro contendo
m linhas e n colunas e usada, entre outros usos, para a resolução
de sistemas de equações lineares e transformações lineares
I uma matriz com m linhas e n colunas é chamada de uma matriz
m por n e denota-se m× n
I os valores m e n são chamados de dimensões, tipo ou ordem da
matriz
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 4 / 28
Definição, declaração e uso
I na matemática, uma matriz é uma tabela ou um quadro contendo
m linhas e n colunas e usada, entre outros usos, para a resolução
de sistemas de equações lineares e transformações lineares
I uma matriz com m linhas e n colunas é chamada de uma matriz
m por n e denota-se m× n
I os valores m e n são chamados de dimensões, tipo ou ordem da
matriz
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 4 / 28
Definição, declaração e uso
I na matemática, uma matriz é uma tabela ou um quadro contendo
m linhas e n colunas e usada, entre outros usos, para a resolução
de sistemas de equações lineares e transformações lineares
I uma matriz com m linhas e n colunas é chamada de uma matriz
m por n e denota-se m× n
I os valores m e n são chamados de dimensões, tipo ou ordem da
matriz
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 4 / 28
Definição, declaração e uso
I um elemento de uma matriz A que está na linha i e na coluna j é
chamado de elemento i, j ou (i, j)-ésimo elemento de A
I este elemento é denotado por Ai,j ou A(i, j)
I uma matriz onde uma de suas dimensões é igual a 1 é
geralmente chamada de vetor
I uma matriz de dimensões 1× n, contendo uma linha e n colunas,
é chamada de vetor linha ou matriz linha, e uma matriz de
dimensões m× 1, contendo m linhas e uma coluna, é chamada de
vetor coluna ou matriz coluna
I na linguagem C, as matrizes são declaradas similarmente aos
vetores
tipo identificador[dimensão1][dimensão2];
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 5 / 28
Definição, declaração e uso
I um elemento de uma matriz A que está na linha i e na coluna j é
chamado de elemento i, j ou (i, j)-ésimo elemento de A
I este elemento é denotado por Ai,j ou A(i, j)
I uma matriz onde uma de suas dimensões é igual a 1 é
geralmente chamada de vetor
I uma matriz de dimensões 1× n, contendo uma linha e n colunas,
é chamada de vetor linha ou matriz linha, e uma matriz de
dimensões m× 1, contendo m linhas e uma coluna, é chamada de
vetor coluna ou matriz coluna
I na linguagem C, as matrizes são declaradas similarmente aos
vetores
tipo identificador[dimensão1][dimensão2];
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 5 / 28
Definição, declaração e uso
I um elemento de uma matriz A que está na linha i e na coluna j é
chamado de elemento i, j ou (i, j)-ésimo elemento de A
I este elemento é denotado por Ai,j ou A(i, j)
I uma matriz onde uma de suas dimensões é igual a 1 é
geralmente chamada de vetor
I uma matriz de dimensões 1× n, contendo uma linha e n colunas,
é chamada de vetor linha ou matriz linha, e uma matriz de
dimensões m× 1, contendo m linhas e uma coluna, é chamada de
vetor coluna ou matriz coluna
I na linguagem C, as matrizes são declaradas similarmente aos
vetores
tipo identificador[dimensão1][dimensão2];
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 5 / 28
Definição, declaração e uso
I um elemento de uma matriz A que está na linha i e na coluna j é
chamado de elemento i, j ou (i, j)-ésimo elemento de A
I este elemento é denotado por Ai,j ou A(i, j)
I uma matriz onde uma de suas dimensões é igual a 1 é
geralmente chamada de vetor
I uma matriz de dimensões 1× n, contendo uma linha e n colunas,
é chamada de vetor linha ou matriz linha, e uma matriz de
dimensões m× 1, contendo m linhas e uma coluna, é chamada de
vetor coluna ou matriz coluna
I na linguagem C, as matrizes são declaradas similarmente aos
vetores
tipo identificador[dimensão1][dimensão2];
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 5 / 28
Definição, declaração e uso
I um elemento de uma matriz A que está na linha i e na coluna j é
chamado de elemento i, j ou (i, j)-ésimo elemento de A
I este elemento é denotado por Ai,j ou A(i, j)
I uma matriz onde uma de suas dimensões é igual a 1 é
geralmente chamada de vetor
I uma matriz de dimensões 1× n, contendo uma linha e n colunas,
é chamada de vetor linha ou matriz linha, e uma matriz de
dimensões m× 1, contendo m linhas e uma coluna, é chamada de
vetor coluna ou matriz coluna
I na linguagem C, as matrizes são declaradas similarmente aos
vetores
tipo identificador[dimensão1][dimensão2];
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 5 / 28
Definição, declaração e uso
I Exemplo:
int A[20][30];
2
1
0
18
19
0 1 2 28 29A
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 6 / 28
Definição, declaração e uso
I na linguagem C, a primeira linha de uma matriz tem índice 0, a
segunda linha tem índice 1, e assim por diante
I do mesmo modo, a primeira coluna da matriz tem índice 0, a
segunda tem índice 1 e assim por diante
I para referenciar o valor da célula da linha 0 e da coluna 3 da
matriz A , devemos usar o identificador da variável e os índices 0
e 3 envolvidos por colchetes, ou seja, A[0][3]
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 7 / 28
Definição, declaração e uso
I na linguagem C, a primeira linha de uma matriz tem índice 0, a
segunda linha tem índice 1, e assim por diante
I do mesmo modo, a primeira coluna da matriz tem índice 0, a
segunda tem índice 1 e assim por diante
I para referenciar o valor da célula da linha 0 e da coluna 3 da
matriz A , devemos usar o identificador da variável e os índices 0
e 3 envolvidos por colchetes, ou seja, A[0][3]
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 7 / 28
Definição, declaração e uso
I na linguagem C, a primeira linha de uma matriz tem índice 0, a
segunda linha tem índice 1, e assim por diante
I do mesmo modo, a primeira coluna da matriz tem índice 0, a
segunda tem índice 1 e assim por diante
I para referenciar o valor da célula da linha 0 e da coluna 3 da
matriz A , devemos usar o identificador da variável e os índices 0
e 3 envolvidos por colchetes, ou seja, A[0][3]
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 7 / 28
Definição, declaraçãoe uso
I apesar de visualizarmos uma matriz na forma de uma tabela
bidimensional, essa não é a forma de armazenamento dessa
variável na memória
memoria linha 0 linha 1 linha 19
A[0][0] A[0][29] A[1][0] A[1][29] A[19][0] A[19][29]
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 8 / 28
Declaração e inicialização simultâneas
I da mesma forma como com os vetores, uma matriz pode ser
inicializada no momento de sua declaração
I variáveis compostas de qualquer dimensão podem ser
inicializadas seguindo as mesmas regras
I para uma matriz, a declaração e inicialização simultâneas deve
ser realizada agrupando os inicializadores de uma dimensão
int A[4][7] = { {0, 1, 1, 0, 0, 0, 2},
{1, 2, 0, 1, 5, 7, 1},
{2, 2, 2, 1, 1, 2, 1},
{3, 7, 9, 6, 2, 1, 0} };
I a linguagem C possui algumas pequenas regras para declarar e
inicializar matrizes ou variáveis compostas homogêneas de
qualquer dimensão
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 9 / 28
Declaração e inicialização simultâneas
I da mesma forma como com os vetores, uma matriz pode ser
inicializada no momento de sua declaração
I variáveis compostas de qualquer dimensão podem ser
inicializadas seguindo as mesmas regras
I para uma matriz, a declaração e inicialização simultâneas deve
ser realizada agrupando os inicializadores de uma dimensão
int A[4][7] = { {0, 1, 1, 0, 0, 0, 2},
{1, 2, 0, 1, 5, 7, 1},
{2, 2, 2, 1, 1, 2, 1},
{3, 7, 9, 6, 2, 1, 0} };
I a linguagem C possui algumas pequenas regras para declarar e
inicializar matrizes ou variáveis compostas homogêneas de
qualquer dimensão
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 9 / 28
Declaração e inicialização simultâneas
I da mesma forma como com os vetores, uma matriz pode ser
inicializada no momento de sua declaração
I variáveis compostas de qualquer dimensão podem ser
inicializadas seguindo as mesmas regras
I para uma matriz, a declaração e inicialização simultâneas deve
ser realizada agrupando os inicializadores de uma dimensão
int A[4][7] = { {0, 1, 1, 0, 0, 0, 2},
{1, 2, 0, 1, 5, 7, 1},
{2, 2, 2, 1, 1, 2, 1},
{3, 7, 9, 6, 2, 1, 0} };
I a linguagem C possui algumas pequenas regras para declarar e
inicializar matrizes ou variáveis compostas homogêneas de
qualquer dimensão
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 9 / 28
Declaração e inicialização simultâneas
I da mesma forma como com os vetores, uma matriz pode ser
inicializada no momento de sua declaração
I variáveis compostas de qualquer dimensão podem ser
inicializadas seguindo as mesmas regras
I para uma matriz, a declaração e inicialização simultâneas deve
ser realizada agrupando os inicializadores de uma dimensão
int A[4][7] = { {0, 1, 1, 0, 0, 0, 2},
{1, 2, 0, 1, 5, 7, 1},
{2, 2, 2, 1, 1, 2, 1},
{3, 7, 9, 6, 2, 1, 0} };
I a linguagem C possui algumas pequenas regras para declarar e
inicializar matrizes ou variáveis compostas homogêneas de
qualquer dimensão
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 9 / 28
Declaração e inicialização simultâneas
Regras:
I se um inicializador não é grande o suficiente para inicializar um
variável composta homogênea, então o restante dos elementos
serão inicializados com 0 (zero)
int A[4][7] = { {0, 1, 1, 0, 0, 0, 2},
{3, 7, 9, 6, 2, 1, 0} };
I se um inicializador mais interno não é longo o suficiente para
inicializar uma linha, então o restante dos elementos na linha é
inicializado com 0 (zero)
int A[4][7] = { {0, 1, 1},
{1, 2, 0, 1, 5, 7, 1},
{2, 2, 2, 1, 1, 2},
{3, 7, 9, 6, 2, 1, 0} };
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 10 / 28
Declaração e inicialização simultâneas
Regras:
I se um inicializador não é grande o suficiente para inicializar um
variável composta homogênea, então o restante dos elementos
serão inicializados com 0 (zero)
int A[4][7] = { {0, 1, 1, 0, 0, 0, 2},
{3, 7, 9, 6, 2, 1, 0} };
I se um inicializador mais interno não é longo o suficiente para
inicializar uma linha, então o restante dos elementos na linha é
inicializado com 0 (zero)
int A[4][7] = { {0, 1, 1},
{1, 2, 0, 1, 5, 7, 1},
{2, 2, 2, 1, 1, 2},
{3, 7, 9, 6, 2, 1, 0} };
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 10 / 28
Declaração e inicialização simultâneas
Regras:
I as chaves internas, que determinam as inicializações das linhas,
podem ser omitidas. Neste caso, uma vez que o compilador tenha
lido elementos suficientes para preencher uma linha, ele o faz e
inicia o preenchimento da próxima linha
int A[4][7] = {0, 1, 1, 0, 0, 0, 2,
1, 2, 0, 1, 5, 7, 1,
2, 2, 2, 1, 1, 2, 1,
3, 7, 9, 6, 2, 1, 0};
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 11 / 28
Exemplo
#include <stdio.h>
int main(void)
{
int i, j;
float soma_c3, soma_l2, B[3][5];
for (i = 0; i < 3; i++)
for (j = 0; j < 5; j++) {
printf("Informe B[%d][%d]: ", i, j);
scanf("%f", &B[i][j]);
}
soma_c3 = 0.0;
for (i = 0; i < 3; i++)
soma_c3 = soma_c3 + B[i][2];
printf("Valor da soma da terceira coluna é %f\n", soma_c3);
soma_l2 = 0.0;
for (j = 0; j < 5; j++)
soma_l2 = soma_l2 + B[1][j];
printf("Valor da soma da segunda linha é %f\n", soma_l2);
return 0;
}
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 12 / 28
Exercícios
1. Dadas duas matrizes de números inteiros A e B, de dimensões
m× n, com 1 6 m, n 6 100, fazer um programa que calcule a
matriz Cm×n = A+ B.
#include <stdio.h>
#define MAX 100
int main(void)
{
int m, n, i, j, A[MAX][MAX], B[MAX][MAX], C[MAX][MAX];
printf("Informe as dimensões (m, n) das matrizes: ");
scanf("%d%d", &m, &n);
for (i = 0; i < m; i++)
for (j = 0; j < n; j++) {
printf("Informe A[%2d][%2d]: ", i, j);
scanf("%d", &A[i][j]);
}
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 13 / 28
Exercícios
for (i = 0; i < m; i++)
for (j = 0; j < n; j++) {
printf("Informe B[%2d][%2d]: ", i, j);
scanf("%d", &B[i][j]);
}
for (i = 0; i < m; i++)
for (j = 0; j < n; j++)
C[i][j] = A[i][j] + B[i][j];
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++)
printf("%2d ", C[i][j]);
printf("\n");
}
return 0;
}
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 14 / 28
Exercícios
2. Dada uma matriz de números inteiros Am×n, com 1 6 m, n 6 100,
imprimir o número de linhas e o número de colunas nulas da
matriz.
Exemplo:
Se a matriz A tem m = 4 linhas, n = 4 colunas e conteúdo
1 0 2 3
4 0 5 6
0 0 0 0
0 0 0 0

então A tem 2 linhas nulas e 1 coluna nula.
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 15 / 28
Exercícios
3. Dizemos que uma matriz de números inteiros An×n é uma matriz
de permutação se em cada linha e em cada coluna houver n− 1
elementos nulos e um único elemento 1.
Exemplo:
A matriz

0 1 0 0
0 0 1 0
1 0 0 0
0 0 0 1
 é de permutação, mas a matriz
 2 −1 0−1 2 0
0 0 1
 não é de permutação.
Dada uma matriz de números inteiros An×n, com 1 6 n 6 100,
verificar se A é de permutação.
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 16 / 28
Exercícios
4. Dizemos que uma matriz quadrada de números inteiros distintos
é um quadrado mágico se a soma dos elementos de cada linha,
a soma dos elementos de cada coluna e a soma dos elementos
da diagonal principal e secundária são todas iguais.
Exemplo:
A matriz  8 0 74 5 6
3 10 2

é um quadrado mágico.
Dada uma matriz quadrada de números inteiros An×n, com
1 6 n 6 100, verificar se A é um quadrado mágico.
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 17 / 28
Exercícios
5. (a) Imprimir as n primeiras linhas do triângulo de Pascal, com
1 6 n 6 100.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
...
(b) Imprimir as n primeiras linhas do triângulo de Pascal usando
apenas um vetor.
ViduaniMartinez (FACOM) Matrizes Algoritmos e Programação 18 / 28
Exercícios
6. Faça um programa que, dada uma matriz de números reais Am×n,
determine At. Suponha que 1 6 m, n 6 100.
7. Dada uma matriz de números reais A com m linhas e n colunas,
1 6 m, n 6 100, e um vetor de números reais v com n elementos,
determinar o produto de A por v.
8. Um vetor de números reais x com n elementos é apresentado
como resultado de um sistema de equações lineares Ax = b,
cujos coeficientes são representados em uma matriz de números
reais Am×n e o lados direitos das equações em um vetor de
números reais b de m elementos. Dados A, x e b, verificar se o
vetor x é realmente solução do sistema Ax = b, supondo que
1 6 m, n 6 100.
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 19 / 28
Exercícios
6. Faça um programa que, dada uma matriz de números reais Am×n,
determine At. Suponha que 1 6 m, n 6 100.
7. Dada uma matriz de números reais A com m linhas e n colunas,
1 6 m, n 6 100, e um vetor de números reais v com n elementos,
determinar o produto de A por v.
8. Um vetor de números reais x com n elementos é apresentado
como resultado de um sistema de equações lineares Ax = b,
cujos coeficientes são representados em uma matriz de números
reais Am×n e o lados direitos das equações em um vetor de
números reais b de m elementos. Dados A, x e b, verificar se o
vetor x é realmente solução do sistema Ax = b, supondo que
1 6 m, n 6 100.
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 19 / 28
Exercícios
6. Faça um programa que, dada uma matriz de números reais Am×n,
determine At. Suponha que 1 6 m, n 6 100.
7. Dada uma matriz de números reais A com m linhas e n colunas,
1 6 m, n 6 100, e um vetor de números reais v com n elementos,
determinar o produto de A por v.
8. Um vetor de números reais x com n elementos é apresentado
como resultado de um sistema de equações lineares Ax = b,
cujos coeficientes são representados em uma matriz de números
reais Am×n e o lados direitos das equações em um vetor de
números reais b de m elementos. Dados A, x e b, verificar se o
vetor x é realmente solução do sistema Ax = b, supondo que
1 6 m, n 6 100.
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 19 / 28
Exercícios
9. Dadas duas matrizes de números reais Am×n e Bn×p, com
1 6 m, n, p 6 100, calcular o produto de A por B.
10. Um jogo de palavras cruzadas pode ser representado por uma
matriz Am×n onde cada posição da matriz corresponde a um
quadrado do jogo, sendo que 0 indica um quadrado branco e −1
indica um quadrado preto. Indicar em uma dada matriz Am×n de 0
e −1, com 1 6 m, n 6 100, as posições que são início de palavras
horizontais e/ou verticais nos quadrados correspondentes
(substituindo os zeros), considerando que uma palavra deve ter
pelo menos duas letras. Para isso, numere consecutivamente tais
posições.
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 20 / 28
Exercícios
9. Dadas duas matrizes de números reais Am×n e Bn×p, com
1 6 m, n, p 6 100, calcular o produto de A por B.
10. Um jogo de palavras cruzadas pode ser representado por uma
matriz Am×n onde cada posição da matriz corresponde a um
quadrado do jogo, sendo que 0 indica um quadrado branco e −1
indica um quadrado preto. Indicar em uma dada matriz Am×n de 0
e −1, com 1 6 m, n 6 100, as posições que são início de palavras
horizontais e/ou verticais nos quadrados correspondentes
(substituindo os zeros), considerando que uma palavra deve ter
pelo menos duas letras. Para isso, numere consecutivamente tais
posições.
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 20 / 28
Exercícios
10. Exemplo:
Dada a matriz
0 −1 0 −1 −1 0 −1 0
0 0 0 0 −1 0 0 0
0 0 −1 −1 0 0 −1 0
−1 0 0 0 0 −1 0 0
0 0 −1 0 0 0 −1 −1

a saída deverá ser
1 −1 2 −1 −1 3 −1 4
5 6 0 0 −1 7 0 0
8 0 −1 −1 9 0 −1 0
−1 10 0 11 0 −1 12 0
13 0 −1 14 0 0 −1 −1
 .
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 21 / 28
Exercícios
11. Os elementos aij de uma matriz de números inteiros An×n
representam os custos de transporte da cidade i para a cidade j.
Dados uma matriz An×n, com 1 6 n 6 100, um número inteiro
m > 0 representando a quantidade de itinerários, um número k
representando o número de cidades em cada um dos itinerários,
calcular o custo total para cada itinerário.
Exemplo:
Dado
A =

4 1 2 3
5 2 1 400
2 1 3 8
7 1 2 5

m = 1, k = 8 e o itinerário 0 3 1 3 3 2 1 0, o custo total desse
itinerário é
a03+a31+a13+a33+a32+a21+a10 = 3+1+400+5+2+1+5 = 417.
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 22 / 28
Exercícios
12. Dados um caça-palavra, representado por uma matriz A de letras
de dimensão m× n, com 1 6 m, n 6 50, e uma lista de k > 0
palavras, encontrar a localização (linha e coluna) no
caça-palavras em que cada uma das palavras pode ser
encontrada.
a a t g d k h
q y u s z j l l c
b m a m o r a w e
p f x v n te q
o
o
o
o
c
c
c
g
g
g
j
j
j
u a
a
a
a
u
c
u
t
t
t
u
d
d
d
k
k
k
h
h
h
q
q
q
y
y
y
s
s
s
s
z
z
z
z
l
l
l
l
c
c
b
b
b
m
m
m
o
o
o
o
r
r
r
a
a
a
w
e
e p
a
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 23 / 28
Exercícios
12. Uma palavra é encontrada no caça-palavras se uma seqüência
ininterrupta de letras na tabela coincide com a palavra. Considere
que as letras são apenas as minúsculas. A busca por uma palavra
deve ser feita em qualquer das oito direções no caça-palavras.
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 24 / 28
Exercícios
13. Considere n cidades numeradas de 0 a n− 1 que estão
interligadas por uma série de estradas de mão única, com
1 6 n 6 100. As ligações entre as cidades são representadas
pelos elementos de uma matriz quadrada An×n, cujos elementos
aij assumem o valor 1 ou 0, conforme exista ou não estrada direta
que saia da cidade i e chegue à cidade j. Assim, os elementos da
coluna j indicam as estradas que chegam à cidade j. Por
convenção aii = 1.
A figura a seguir mostra um exemplo para n = 4.
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 25 / 28
Exercícios
13.
A
1 1 0
1 1 0
00
0
1 1
1 1 1
0
0
1
1
1
2
2
3
0 1 2 3
3
1
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 26 / 28
Exercícios
13. (a) Dado k, determinar quantas estradas saem e quantas chegam à
cidade k.
(b) A qual das cidades chega o maior número de estradas?
(c) Dado k, verificar se todas as ligações diretas entre a cidade k e
outras são de mão dupla.
(d) Relacionar as cidades que possuem saídas diretas para a cidade k.
(e) Relacionar, se existirem:
(i) As cidades isoladas, isto é, as que não têm ligação com nenhuma
outra;
(ii) As cidades das quais não há saída, apesar de haver entrada;
(iii) As cidades das quais há saída sem haver entrada.
(f) Dada uma seqüência de m inteiros cujos valores estão entre 0 e
n− 1, verificar se é possível realizar o roteiro correspondente. No
exemplo dado, o roteiro representado pela seqüência 2 0 1 2 3,
com m = 5, é impossível.
(g) Dados k e p, determinar se é possível ir da cidade k para a cidade p
pelas estradas existentes. Você consegue encontrar o menor
caminho entre as duas cidades?
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 27 / 28
Exercícios
13. (a) Dado k, determinar quantas estradas saem e quantas chegam à
cidade k.
(b) A qual das cidades chega o maior número de estradas?
(c) Dado k, verificar se todas as ligações diretas entre a cidade k e
outras são de mão dupla.
(d) Relacionar as cidades que possuem saídas diretas para a cidade k.(e) Relacionar, se existirem:
(i) As cidades isoladas, isto é, as que não têm ligação com nenhuma
outra;
(ii) As cidades das quais não há saída, apesar de haver entrada;
(iii) As cidades das quais há saída sem haver entrada.
(f) Dada uma seqüência de m inteiros cujos valores estão entre 0 e
n− 1, verificar se é possível realizar o roteiro correspondente. No
exemplo dado, o roteiro representado pela seqüência 2 0 1 2 3,
com m = 5, é impossível.
(g) Dados k e p, determinar se é possível ir da cidade k para a cidade p
pelas estradas existentes. Você consegue encontrar o menor
caminho entre as duas cidades?
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 27 / 28
Exercícios
13. (a) Dado k, determinar quantas estradas saem e quantas chegam à
cidade k.
(b) A qual das cidades chega o maior número de estradas?
(c) Dado k, verificar se todas as ligações diretas entre a cidade k e
outras são de mão dupla.
(d) Relacionar as cidades que possuem saídas diretas para a cidade k.
(e) Relacionar, se existirem:
(i) As cidades isoladas, isto é, as que não têm ligação com nenhuma
outra;
(ii) As cidades das quais não há saída, apesar de haver entrada;
(iii) As cidades das quais há saída sem haver entrada.
(f) Dada uma seqüência de m inteiros cujos valores estão entre 0 e
n− 1, verificar se é possível realizar o roteiro correspondente. No
exemplo dado, o roteiro representado pela seqüência 2 0 1 2 3,
com m = 5, é impossível.
(g) Dados k e p, determinar se é possível ir da cidade k para a cidade p
pelas estradas existentes. Você consegue encontrar o menor
caminho entre as duas cidades?
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 27 / 28
Exercícios
13. (a) Dado k, determinar quantas estradas saem e quantas chegam à
cidade k.
(b) A qual das cidades chega o maior número de estradas?
(c) Dado k, verificar se todas as ligações diretas entre a cidade k e
outras são de mão dupla.
(d) Relacionar as cidades que possuem saídas diretas para a cidade k.
(e) Relacionar, se existirem:
(i) As cidades isoladas, isto é, as que não têm ligação com nenhuma
outra;
(ii) As cidades das quais não há saída, apesar de haver entrada;
(iii) As cidades das quais há saída sem haver entrada.
(f) Dada uma seqüência de m inteiros cujos valores estão entre 0 e
n− 1, verificar se é possível realizar o roteiro correspondente. No
exemplo dado, o roteiro representado pela seqüência 2 0 1 2 3,
com m = 5, é impossível.
(g) Dados k e p, determinar se é possível ir da cidade k para a cidade p
pelas estradas existentes. Você consegue encontrar o menor
caminho entre as duas cidades?
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 27 / 28
Exercícios
13. (a) Dado k, determinar quantas estradas saem e quantas chegam à
cidade k.
(b) A qual das cidades chega o maior número de estradas?
(c) Dado k, verificar se todas as ligações diretas entre a cidade k e
outras são de mão dupla.
(d) Relacionar as cidades que possuem saídas diretas para a cidade k.
(e) Relacionar, se existirem:
(i) As cidades isoladas, isto é, as que não têm ligação com nenhuma
outra;
(ii) As cidades das quais não há saída, apesar de haver entrada;
(iii) As cidades das quais há saída sem haver entrada.
(f) Dada uma seqüência de m inteiros cujos valores estão entre 0 e
n− 1, verificar se é possível realizar o roteiro correspondente. No
exemplo dado, o roteiro representado pela seqüência 2 0 1 2 3,
com m = 5, é impossível.
(g) Dados k e p, determinar se é possível ir da cidade k para a cidade p
pelas estradas existentes. Você consegue encontrar o menor
caminho entre as duas cidades?
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 27 / 28
Exercícios
13. (a) Dado k, determinar quantas estradas saem e quantas chegam à
cidade k.
(b) A qual das cidades chega o maior número de estradas?
(c) Dado k, verificar se todas as ligações diretas entre a cidade k e
outras são de mão dupla.
(d) Relacionar as cidades que possuem saídas diretas para a cidade k.
(e) Relacionar, se existirem:
(i) As cidades isoladas, isto é, as que não têm ligação com nenhuma
outra;
(ii) As cidades das quais não há saída, apesar de haver entrada;
(iii) As cidades das quais há saída sem haver entrada.
(f) Dada uma seqüência de m inteiros cujos valores estão entre 0 e
n− 1, verificar se é possível realizar o roteiro correspondente. No
exemplo dado, o roteiro representado pela seqüência 2 0 1 2 3,
com m = 5, é impossível.
(g) Dados k e p, determinar se é possível ir da cidade k para a cidade p
pelas estradas existentes. Você consegue encontrar o menor
caminho entre as duas cidades?
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 27 / 28
Exercícios
13. (a) Dado k, determinar quantas estradas saem e quantas chegam à
cidade k.
(b) A qual das cidades chega o maior número de estradas?
(c) Dado k, verificar se todas as ligações diretas entre a cidade k e
outras são de mão dupla.
(d) Relacionar as cidades que possuem saídas diretas para a cidade k.
(e) Relacionar, se existirem:
(i) As cidades isoladas, isto é, as que não têm ligação com nenhuma
outra;
(ii) As cidades das quais não há saída, apesar de haver entrada;
(iii) As cidades das quais há saída sem haver entrada.
(f) Dada uma seqüência de m inteiros cujos valores estão entre 0 e
n− 1, verificar se é possível realizar o roteiro correspondente. No
exemplo dado, o roteiro representado pela seqüência 2 0 1 2 3,
com m = 5, é impossível.
(g) Dados k e p, determinar se é possível ir da cidade k para a cidade p
pelas estradas existentes. Você consegue encontrar o menor
caminho entre as duas cidades?
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 27 / 28
Exercícios
13. (a) Dado k, determinar quantas estradas saem e quantas chegam à
cidade k.
(b) A qual das cidades chega o maior número de estradas?
(c) Dado k, verificar se todas as ligações diretas entre a cidade k e
outras são de mão dupla.
(d) Relacionar as cidades que possuem saídas diretas para a cidade k.
(e) Relacionar, se existirem:
(i) As cidades isoladas, isto é, as que não têm ligação com nenhuma
outra;
(ii) As cidades das quais não há saída, apesar de haver entrada;
(iii) As cidades das quais há saída sem haver entrada.
(f) Dada uma seqüência de m inteiros cujos valores estão entre 0 e
n− 1, verificar se é possível realizar o roteiro correspondente. No
exemplo dado, o roteiro representado pela seqüência 2 0 1 2 3,
com m = 5, é impossível.
(g) Dados k e p, determinar se é possível ir da cidade k para a cidade p
pelas estradas existentes. Você consegue encontrar o menor
caminho entre as duas cidades?
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 27 / 28
Exercícios
13. (a) Dado k, determinar quantas estradas saem e quantas chegam à
cidade k.
(b) A qual das cidades chega o maior número de estradas?
(c) Dado k, verificar se todas as ligações diretas entre a cidade k e
outras são de mão dupla.
(d) Relacionar as cidades que possuem saídas diretas para a cidade k.
(e) Relacionar, se existirem:
(i) As cidades isoladas, isto é, as que não têm ligação com nenhuma
outra;
(ii) As cidades das quais não há saída, apesar de haver entrada;
(iii) As cidades das quais há saída sem haver entrada.
(f) Dada uma seqüência de m inteiros cujos valores estão entre 0 e
n− 1, verificar se é possível realizar o roteiro correspondente. No
exemplo dado, o roteiro representado pela seqüência 2 0 1 2 3,
com m = 5, é impossível.
(g) Dados k e p, determinar se é possível ir da cidade k para a cidade p
pelas estradas existentes. Você consegue encontrar o menor
caminho entre as duas cidades?
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 27 / 28
Exercícios
14. Dada uma matriz de números inteiros Am×n, com 1 6 m, n 6 100,
verificar se existem elementos repetidos emA.
Viduani Martinez (FACOM) Matrizes Algoritmos e Programação 28 / 28
	Introdução
	Definição, declaração e uso
	Declaração e inicialização simultâneas
	Exemplo
	Exercícios