Algoritmos Aula 10 Matrizes e vetores

Prévia do material em texto

Algoritmos Aula 10 - Matrizes e vetores 
Introdução 
As estruturas de dados servem principalmente para 
abstrair estruturas da vida real em formas 
computacionais que sejam viáveis de serem 
implementadas. 
Nesta aula, vamos estudar as estruturas de dados 
mais fundamentais que existem e que vão nos ajudar 
a continuar a resolver muitos problemas: os vetores e 
as matrizes. 
Vamos lá! 
Estrutura de Dados 
Na ciência da computação, existe uma área de estudo 
chamada Estrutura de Dados. Para quem é da área de 
programação de computadores, esta é uma disciplina 
obrigatória e fundamental. 
As estruturas de dados servem principalmente, e de 
uma maneira resumida, para abstrair estruturas da 
vida real em formas computacionais que sejam viáveis 
de serem implementadas. 
Exemplo 
Você já deve ter visto uma planilha eletrônica. Como 
você faria se fosse uma das pessoas da equipe de 
desenvolvimento do Excel para poder implementar 
uma planilha? Usando uma tabela, não é? Logo, a 
tabela é uma estrutura de dados e serve para abstrair 
uma planilha. 
Existem muitos exemplos semelhantes, e nesta aula, 
vamos estudar as estruturas de dados mais 
fundamentais que existem e que vão nos ajudar a 
continuar a resolver muitos problemas. 
Apresentaremos a você os vetores e as matrizes. 
Problema: Nucleotídeos de uma Cadeia de DNA 
Já vamos começar a nossa aula lançando um 
problema para você: vamos supor que você acabou 
de ser contratado por um laboratório de 
bioinformática, e o primeiro problema que caiu no 
seu colo foi contar o número de nucleotídeos de uma 
cadeia de DNA. 
Antes que você ache que estamos falando em outra 
língua, vamos explicar um pouco de biologia 
molecular. 
Lembra-se das suas aulas do colégio, em que você 
aprendeu que o DNA (ácido desoxirribonucleico) é 
uma molécula enrolada que contém o nosso código 
genético? 
Resumidamente falando, o DNA é um conjunto de 
nucleotídeos (existem quatro: adenina [A], citosina 
[C], guanina [G] e tiamina [T]), que se combinam. As 
combinações formam nosso genoma ou de qualquer 
ser vivo que possua um código genético. 
Para nós, que somos da programação, o DNA será 
“apenas” uma sequência combinada dessas quatro 
letras, como por exemplo: 
AGCTTTTCATTCTGACTGCAACGGGCAATATGTCTCTGTG
TGGATTAAAAAAAGAGTGTCTGATAGCAGC 
Essa sequência de letras, por incrível que pareça, 
pode representar um pedaço do nosso genoma, que 
determina, por exemplo, a cor dos nossos olhos. 
Seu chefe no laboratório passa a seguinte tarefa: 
Quantos nucleotídeos de cada tipo existem nesta 
sequência de DNA? Qual o tamanho desta cadeia? 
Normalmente, ele vai acrescentar: “preciso disso para 
ontem”. 
E agora, como resolvemos essa? 
Vetores 
A primeira estrutura de dados que vamos estudar é 
chamada de vetor ou array. Se você quiser um nome 
mais acadêmico, pode escolher o nome “variável 
composta unidimensional”. São sinônimos. 
Um vetor, array ou variável composta unidimensional 
é uma estrutura de dados contendo um conjunto de 
dados, todos do mesmo tipo, indexados por um valor. 
Graficamente, podemos representá-lo assim: 
 
A figura mostra um array com tamanho 9, chamado 
de x, cujo conteúdo é de variáveis do tipo char. Temos 
algumas informações importantes na figura: 
Como declaramos este array em C++? 
O array precisa ter um nome. No array da figura, o 
nome é x; 
O array tem um tamanho. No array da figura, o 
tamanho é 9; 
O array possui um tipo. Todos os componentes do 
array obrigatoriamente são do mesmo tipo. No array 
da figura, o tipo é char; 
O array é dividido em índices, um para cada elemento 
do array, começando obrigatoriamente pelo número 
0; 
O array é finito. Não é possível trabalhar com índices 
maiores que o tamanho do array, nem com índices 
negativos. No nosso caso, não é possível colocar um 
valor na posição 9; isso vai gerar um erro chamado de 
index out of bounds; 
Os índices sempre são números inteiros. 
 
Certo, mas e o nosso problema de bioinformática, 
como fica? 
Vetores 
Já que aprendemos o que é um array, podemos 
colocar as letras da cadeia lida de 
DNA em uma estrutura de dados, como o array, da 
seguinte forma: 
 
Veja que teremos então um array com 70 posições. 
Para sua curiosidade, temos aqui 
um array com 70 bytes. Um genoma pode chegar a 
terabytes de informação. É uma 
string gigante. 
Para simplificar o nosso trabalho, em vez de termos 
70 posições, vamos cortar o nosso 
genoma e trabalhar com 20 posições apenas: 
 
Mas não tem 20 posições? Por que o índice vai só até 
19? Não se esqueça que o array 
começa sempre no índice 0. Logo, temos então 20 
posições. 
Vamos dar um nome a este vetor: DNA. Se fôssemos 
declará-lo em C++, seria assim: 
char dna[20]; 
Não esqueça que este é apenas um exemplo. 
Poderíamos ter um array de inteiros para 
trabalhar, como, por exemplo: 
 
Manipulações com Vetores 
Podemos fazer várias operações com vetores. Veja 
atentamente os exemplos: 
Vamos supor que o seu professor de Algoritmos peça 
que você faça algumas operações com as notas das 
provas. São 15 alunos na sala e as notas podem ter 
uma casa decimal. 
Qual é o tipo de dados mais apropriado para guardar 
as notas? 
Pode ser o float, não é? 
Vamos usar um array para esta tarefa. 
Em primeiro lugar, vamos criar um array em C++:float 
notas[15]; 
Após essa declaração, teremos o um vetor criado na 
memória do computador. 
Vetor criado na memória do computador: 
 
Como podemos perceber, ele está pronto para 
receber valores; temos que preenchê-lo. 
Em C++, fazemos assim para atribuir um valor a uma 
posição do array: 
notas[0] = 7.5; 
Após essa linha, teremos o seguinte vetor na 
memória: 
 
Vamos continuar atribuindo valores para cada 
posição. Na prática, cada posição será a nota de um 
aluno. 
 
Após essas atribuições, teremos o seguinte vetor na 
memória: 
 
Não é obrigatório que a atribuição dos valores seja 
feita sequencialmente e é possível termos um vetor 
com posições em branco, sem problema algum. 
 
Podemos manipular os índices e valores dos vetores 
de várias maneiras. Analise aqui o código em C++. 
1 #include <iostream> 
2 using namespace std; 
3 
4 int main (void){ 
5 int a=1; 
6 int b=2; 
7 float notas[15]; 
8 
9 notas[1]=8; notas[2]=9.5; notas[6]=6 ;notas[13]=5; 
10 notas[7]=7.5; notas[8]=7.5; notas[9]=8 
;notas[12]=4.5; 
11 notas[5]=4.5; notas[10]=9; 
12 
13 notas[a+b]=4; 
14 notas[4] = 2*3.5; 
15 notas[10] = 2*notas[1] – 7; 
16 notas[2*7] = 6.5; 
17 } 
Veja que fizemos alguns tipos de manipulações: 
1 - Na linha 13, somamos os valores das variáveis a(1) 
e b(2) e atribuímos na posição 
4 do vetor o valor 4. Lembre-se que é a posição 4 
porque o índice do vetor começa 
com 0; 
2 - Na linha 14, atribuímos o resultado de uma 
expressão ao índice 4 do vetor 
(posição 5); 
3 - Na linha 15, também atribuímos o resultado de 
uma expressão ao índice 10 
(posição 11). Mas aqui usamos o valor presente na 
posição 1 do vetor, assim: 
notas[10] = 2 * notas[1]-7; 
// veja a figura. O valor da posição notas[1] é 8 
// Portanto, notas[10] = 2*8 – 7; 
// notas[10] = 9; 
4 - Na linha 16, fizemos uma conta dentro do índice: 
2*7 = 14, e atribuímos o valor 
6.5 no resultado da conta: notas[14] = 6.5; 
Portanto, veja que é possível fazer várias 
combinações com os índices e valores. 
Observação: lembre-se que “vetor” e “array” são 
sinônimos! 
Para ficar mais interessante, falta apresentar a você 
uma tarefa muito importante: atravessar o vetor (o 
que também chamamos de percorrero vetor ou iterar 
sobre o vetor). 
Travessia do Vetor 
Atravessar o vetor, ou iterar sobre ele, ou percorrê-lo 
consiste em fazer uma repetição e verificar índice por 
índice o valor de cada posição, até chegar ao final do 
vetor, seja ele do tamanho que for. 
No nosso exemplo de bioinformática, diminuímos o 
tamanho da string de entrada para simplificar, mas 
como já vimos, um genoma tem terabytes de 
tamanho. 
Já pensou você declarar um vetor com um bilhão de 
posições? É por isso que máquinas que trabalham 
com esta área precisam ser rápidas, para poder 
processar os dados dentro de um tempo razoável. 
Vamos verificar aqui a solução para o nosso problema 
bioinformático e conferir aqui a execução 
Pronto, agora podemos entregar o trabalho para o 
nosso chefe, e que venham mais sequências de DNA! 
Aprendemos o básico sobre os vetores. Existem mais 
detalhes que vamos reservar para você usar sua 
curiosidade e habilidade para aprender novas funções 
da linguagem C que podem ser feitas com as strings e 
também que podem ser usadas exclusivamente com 
vetores. 
Matrizes 
A outra estrutura de dados que vamos estudar nesta 
aula são as matrizes, ou variáveis compostas 
multidimensionais. 
O que é uma matriz? Pense numa tabela. Pronto, 
aprendeu! 
Quando falamos sobre vetores na primeira parte da 
aula, você viu que as figuras representativas da 
estrutura de dados estão desenhadas 
horizontalmente? Mas e se empilhássemos vários 
vetores, desta forma? 
 
Veja que temos 7 (de 0 a 6) vetores empilhados de 13 
(0 a 12) posições, certo? Observe que é a mesma 
representação de uma tabela ou uma planilha. 
Também temos aqui índices para a dimensão 
horizontal e para a dimensão vertical. Podemos até 
chamar de x e y, mas normalmente chamamos de 
linhas e colunas. Cada uma tem a sua numeração 
correspondente. 
Da mesma forma que o vetor, uma matriz também 
tem um nome, é uma variável e, por definição, seu 
conteúdo só pode ser preenchido por valores do 
mesmo tipo. 
 
Veja a figura a seguir: 
 
Essa figura mostra uma matriz chamada “a”, com n 
colunas e i linhas. Cada par linha x coluna é denotado 
por aij ou também a[i,j].Em C++, declaramos uma 
matriz de duas dimensões assim: 
tipo nome_da_matriz [ ] [ ]; 
Atenção 
Repare que essa é a declaração de uma matriz de 
duas dimensões. Quer dizer que podemos ter mais 
dimensões. Existem também várias aplicações para 
matrizes com três dimensões (os cubos), quatro 
dimensões, cinco etc. Porém, este conhecimento não 
faz parte do nosso contexto. 
As regras que foram apresentadas para os vetores 
(índices negativos ou maiores que o tamanho da 
estrutura, nome da estrutura etc.) também são 
aplicáveis para as matrizes. 
Vamos apresentar um programa e incluir nele a forma 
de declaração de uma matriz em C++, e sua forma de 
travessia. É muito parecido com o vetor, porém agora, 
temos que trabalhar com dois índices para cada valor. 
Este exemplo é bem simples. Ele vai pedir para o 
usuário preencher uma matriz de 3x3 e depois vamos 
imprimir a matriz na tela. 
para analisá-lo e veja aqui: 
1 #include <iostream> 
2 #include <stdlib.h> 
3 using namespace std; 
4 
5 int main(){ 
6 int matriz[3][3]; 
7 int linha, coluna; 
8 
9 system("cls"); 
10 for(linha = 0 ; linha < 3 ; linha++) 
11 for(coluna = 0 ; coluna<3 ; coluna++){ 
12 
 cout<<"Posicao 
["<<linha+1<<"]["<<coluna+1<<"]: "; 
13 cin>>matriz[linha][coluna]; 
14 } 
15 
16 for(linha = 0 ; linha<3 ; linha++){ 
17 for(coluna = 0 ; coluna < 3 ; coluna++) 
18 cout<<matriz[linha][coluna]<<" "; 
19 cout<<"\n"; 
20 } 
21 return 0; 
22 } 
O objetivo é bem simples: o programa pede para o 
usuário preencher uma matriz 3x3 e, 
depois de preenchida, ele percorre a matriz 
mostrando os números preenchidos. 
Nas linhas 10 a 14, criamos dois loopings para fazer a 
leitura dos valores. Nas matrizes, 
como estamos trabalhando com linhas e colunas, 
precisamos criar loopings aninhados, 
para poder fazer a leitura de uma linha completa e 
depois variar a leitura nas colunas. 
Esse processo é semelhante para a travessia, 
compreendida nas linhas 16 a 20. 
A linha 12 mostra uma soma que é feita nas linhas e 
colunas. Este recurso é apenas visual, 
para que o usuário trabalhe com o índice 1 no lugar 
do 0. Na matemática, quando 
aprendemos sobre cálculo de matrizes, 
determinantes etc., não usamos o índice 0. Mas 
em C++ sim, não se esqueça! 
Tanto as operações que vimos para os vetores quanto 
a travessia são bem semelhantes 
nas matrizes. O único detalhe é que precisamos 
considerar as linhas, além das colunas. 
Temos um exemplo mais detalhado. 
Suponha que temos uma classe com 10 alunos e duas 
provas por aluno. Precisamos calcular e imprimir a 
média de cada aluno. 
Veja aqui como podemos organizar a solução. 
Matrizes 
Suponha que temos uma classe com 10 alunos e duas 
provas por aluno. Precisamos 
calcular e imprimir a média de cada aluno. Veja como 
podemos organizar a solução: 
 
Vamos usar duas estruturas: uma para as provas e 
outra para as médias. Na estrutura de 
provas, o índice 0 corresponde à P1 (prova1) e o 
índice 1 corresponde à P2 (prova 2). 
Cada aluno tem uma linha correspondente que vai de 
0 a 9, totalizando os 10 alunos da 
classe. No vetor de médias, cada índice corresponde à 
média entre P1 e P2 de cada aluno. 
Vamos ao programa: 
1 #include <iostream> 
2 #include <stdlib.h> 
3 using namespace std; 
4 
5 int main(){ 
6 int alunos=10, provas=2; 
7 float notas[alunos][provas], medias[alunos]; 
8 int i,j; 
9 
10 for(i=0; i<alunos; i++){ 
11 for(j=0;j<provas; j++){ 
12 cout<<"Aluno "<<i+1<<" Prova "<<j+1<<" - Digite a 
nota: "; 
13 cin>>notas[i][j]; 
14 } 
15 } 
16 
17 for(i=0;i<alunos;i++){ 
18 medias[i]=0.0; 
19 for(j=0;j<provas;j++){ 
20 medias[i]=medias[i]+notas[i][j]; 
21 } 
22 medias[i]=medias[i]/provas; 
23 } 
24 for (i=0; i<alunos;i++){ 
25 cout<<"Aluno "<<i+1<<" Media = 
"<<medias[i]<<endl; 
26 } 
27 return 0; 
28 } 
Veja a execução do programa. 
As linhas 10 a 15 fazem a leitura das provas de cada 
aluno. Para ficar mais atraente, somamos 1 às 
variáveis i e j, para não apresentar o índice 0 para o 
usuário. Isto foi feito tanto para cada aluno quanto na 
prova. Assim aparece prova1 e prova2, para ficar mais 
realista. 
Após a leitura das notas, as linhas 17 a 23 calculam a 
média para cada aluno e atribuem o resultado para o 
vetor “médias” no índice correspondente. 
Enfim, as linhas 24 a 26 percorrem o vetor de médias 
mostrando os valores para o usuário. 
Atividades 
1. Agora, vamos exercitar tudo o que aprendemos! 
O nosso chefe do laboratório de informática nos 
passou outra tarefa: dada uma sequência de DNA, ele 
precisa da transcrição desta sequência em mRNA. 
O que é isso? O RNA é outro nucleotídeo presente nas 
nossas células. 
Vamos lá, dada então uma sequência de DNA, como a 
seguir: 
GATGGAACTTGACTACGTAAATT 
Devemos transformá-la em RNA. Para isso, temos que 
percorrer a string do DNA e substituir todas as 
ocorrências do caractere “T” pelo “U”. Neste caso, o 
resultado é: 
GAUGGAACUUGACUACGUAAAUU 
Como você faria isso? 
Resposta: 
1) Temos que criar um vetor para receber a cadeia de 
DNA; 
2) Temos que criar outro para o cadeia de RNA, que 
vamos usar como resultado; 
3) Percorremos a cadeia de DNA e verificamos o valor 
de cada índice. Se for “G”, fica 
como está; “A” também, mas se aparecer um “T”, 
vamos copiar no vetor do RNA 
como “U”. 
Veja uma sugestão para o programa: 
1 #include <iostream> 
2 #include <string.h> 
3 using namespace std; 
4 
5 int main (void){ 
6 chardna[] = "GATGGAACTTGACTACGTAAATT"; 
7 char nuc; 
8 int i; 
9 int tam; 
10 
11 tam = strlen(dna); 
12 
13 char rna[tam]; 
14 
15 for (i=0;i<=tam;i++){ 
16 nuc = dna[i]; 
17 if (nuc=='T'){ 
18 rna[i]='U'; 
19 } 
20 else { 
21 rna[i]=nuc; 
22 } 
23 } 
24 cout<<"mRNA resultante:"<<endl; 
25 for (i=0;i<=tam;i++){ 
26 cout<<rna[i]; 
27 } 
28 return 0; 
29 } 
2. (Ano: 2012 - Banca: FUNIVERSA - Órgão: PC-DF - 
Prova: Perito Criminal – Informática) A estrutura de 
dados formada por vários elementos do mesmo tipo 
que podem ser acessados por meio do uso de um 
índice é o(a): 
Array 
GABARITO 
Conforme vimos durante a aula, um array é uma 
estrutura que possui os mesmos tipos de dados como 
valores que podem ser acessados por meio de um 
índice. 
3. (Ano: 2009 - Banca: CESPE - Órgão: ANAC - Prova: 
Analista Administrativo - Tecnologia da Informação) 
Um array é um agregado, possivelmente 
heterogêneo, de elementos de dados. Nele, um 
elemento individual é identificado por sua posição em 
relação ao primeiro. 
Errado 
GABARITO 
Um array nunca é heterogêneo. 
4. (Ano: 2010 - Banca: CESPE - Órgão: Banco da 
Amazônia - Prova: Técnico Científico - Tecnologia da 
Informação) 
Os dados armazenados em uma estrutura do tipo 
matriz não podem ser acessados de maneira 
aleatória. Portanto, usa-se normalmente uma matriz 
quando o volume de inserção e remoção de dados é 
maior que o volume de leitura dos elementos 
armazenados. 
Errado 
GABARITO 
É claro que podem ser acessados de maneira 
aleatória. Os exemplos que vimos foram de maneira 
sequencial, mas assim como os vetores, eles podem 
ser acessados de maneira aleatória, sem problema 
algum. 
5. Ano: 2010 - Banca: AOCP - Órgão: Colégio Pedro II - 
Prova: Técnico de Tecnologia da Informação) 
Em algoritmos e estruturas de dados, existe um tipo 
de estrutura chamada de vetor. Sobre vetores, 
assinale a alternativa INCORRETA: 
• Trata-se de variáveis do mesmo tipo, que 
possuem um mesmo identificador (nome), e são 
alocadas aleatoriamente na memória. 
Como as variáveis têm o mesmo nome, o que as 
distingue é um índice que referencia sua localização 
dentro da estrutura. 
Na seguinte declaração: “nome” é o nome da variável, 
“tamanho” é a quantidade de variáveis que vão 
compor o vetor e “tipo” é o tipo básico dos dados que 
serão armazenados no vetor. 
Em pseudocódigo, uma sintaxe válida de atribuição 
em um vetor pode ser: 1 X[1] ← 45. 
Vetor também é conhecido como variável composta 
homogênea unidimensional. 
GABARITO 
Os vetores são alocados sequencialmente na 
memória.