Matrizes
Introduzido| English | Significado |
|---|---|
| array/əˈreɪ/ | array |
| element/ˈelɪmənt/ | elemento |
| index/ˈɪndeks/ | índice |
| lower bound/ˈləʊə baʊnd/ | limite inferior |
| upper bound/ˈʌpə baʊnd/ | limite superior |
| dimension/daɪˈmenʃn/ | dimensão |
| nested loops/ˈnestɪd luːps/ | loops aninhados |
| linear search/ˈlɪnɪə sɜːtʃ/ | busca linear |
| bubble sort/ˈbʌbl sɔːt/ | ordenação por bolha |
Assento 14C
- Um cinema tem 300 assentos. Seu sistema de reservas não possui 300 variáveis chamadas
Seat1A,Seat1B,Seat1C. Ele tem uma única matriz, e seu ingresso é um endereço nela: linha 14, assento C. - Um nome, centenas de valores, cada um encontrado por um número. Adicione uma fileira e o código não muda; faça um loop pelos números e terá verificado todos os assentos.
- Quase todo algoritmo Paper 2 percorre um array: procura-o, soma-o, ordena-o, encontra o seu maior valor.
- Esta aula é o vocabulário, as declarações e os quatro algoritmos que o examinador pede em pseudocódigo e em palavras.
O vocabulário
- Uma matriz é uma estrutura de dados que armazena um número fixo de elementos do mesmo tipo de dado sob um único identificador, cada um acessado por um índice.
- O limite inferior e o limite superior são o primeiro e o último índice válido. O número de elementos é limite superior − limite inferior + 1.
- A dimensão é quantos índices um elemento precisa: um para uma lista, dois para uma tabela.
- Em
ThisArray[n] ← 42o array tem uma dimensão, o índice é a variávelINTEGERn, e o elemento nesse índice recebe42.

Um identificador, um índice para cada elemento, limites em ambas as extremidades
Uma matriz armazena:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Uma matriz é uma coleção ordenada de itens do mesmo tipo acessados por índice. (Um registro agrupa tipos diferentes.)
Uma matriz é uma estrutura de dados que segura muitos valores do tipo ______ sob um único nome.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Cada valor é acessado pelo seu índice.
DECLARE Marks : ARRAY[0:99] OF INTEGER declara uma matriz de ____ elementos.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Limite superior menos limite inferior mais um: 99 − 0 + 1 = 100. Ambos os limites são índices válidos.
Exemplo resolvido: declarar o array que uma tarefa precisa
- Uma declaração precisa do identificador, dos limites e do tipo de dado.
- 120 leituras que podem ter uma casa decimal:
DECLARE Data : ARRAY[1:120] OF REAL - Uma tabela de 150 linhas e duas colunas de texto:
DECLARE Names : ARRAY[1:150, 1:2] OF STRING - Diga a contagem se solicitado:
[0:99]contém 100 elementos, não 99.
Qual declaração segura uma tabela de 150 linhas e 2 colunas de texto?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Duas dimensões, cada uma com um limite inferior e superior, e o tipo de elemento. A segunda opção é uma longa lista; a terceira não tem tipo; a quarta não tem limites inferiores.
Processar um array 1-D
DECLARE Names : ARRAY[1:5] OF STRING
Names[3] ← "Cara"
FOR i ← 1 TO 5
OUTPUT Names[i]
NEXT i
- Um loop
FORdo limite inferior ao superior visita cada elemento uma vez. - Para uma soma, contagem, máximo ou mínimo, defina uma variável acumuladora antes do loop e atualize-a dentro dele.
Arrays 2-D
DECLARE Grid : ARRAY[1:3, 1:4] OF INTEGER
Grid[2, 3] ← 99 // row 2, column 3
- O primeiro índice é a linha, o segundo a coluna. Laços aninhados visitam todas as células: o laço externo sobre linhas, o interno sobre colunas.
- Use 1-D para uma sequência única e 2-D quando os dados têm duas dimensões naturais, como uma grelha de assentos ou uma tabela de notas por aluno e disciplina.

Grid[row, column], sempre nessa ordem
Indexe uma matriz 2-D por [linha, coluna]
Uma matriz 2-D é uma grade. Grid[row, column] alcança exatamente uma célula — altere a linha e a coluna para ver qual valor você encontra.
Em Grid[2, 3], qual célula é acessada?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
O primeiro índice é a linha, o segundo a coluna — então linha 2, coluna 3.
Exemplo resolvido: uma busca linear que pode dizer "não encontrado"
- A pesquisa linear verifica cada elemento sequencialmente, do primeiro até encontrar o alvo ou atingir o final.
FoundAt ← -1
FOR i ← 1 TO n
IF A[i] = Target THEN
FoundAt ← i
ENDIF
NEXT i
IF FoundAt = -1 THEN
OUTPUT "Not found"
ELSE
OUTPUT "Found at ", FoundAt
ENDIF
-1nunca pode ser um índice válido, então significa "não encontrado". Inicialize-o antes do loop e teste-o depois. Uma busca que nunca diz "não encontrado" perde uma marca.
Uma busca linear encontra um valor por:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Uma busca linear examina elementos um por um do início até encontrar o alvo (ou atingir o fim).
Definir FoundAt como -1 antes de uma busca linear permite que o programa relate "não encontrado" após o laço.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
-1 nunca é um índice válido, então se permanecer inalterado após o laço, o alvo não estava na matriz.
Maior valor e onde ele está
Largest ← A[1]
Position ← 1
FOR i ← 2 TO n
IF A[i] > Largest THEN
Largest ← A[i]
Position ← i
ENDIF
NEXT i
OUTPUT Largest, " at ", Position
- Comece
Largestno primeiro elemento, nunca em 0: o array pode ser todo negativo. - A mesma forma conta ou produz os elementos não vazios: compare cada um com o marcador de não usado,
""ou-1, e conte apenas aqueles que diferem.
Ordenação bolha (Bubble sort)
- A ordem de bolha realiza múltiplas passagens pelo array comparando pares adjacentes e trocando os desordenados, até que uma passagem não realize nenhuma troca.
- Após cada passada o maior valor não ordenado bolhou para o final, logo a próxima passada pode parar um lugar antes.
REPEAT
Swapped ← FALSE
FOR Index ← 1 TO Limit - 1
IF Data[Index] > Data[Index + 1] THEN
Temp ← Data[Index]
Data[Index] ← Data[Index + 1]
Data[Index + 1] ← Temp
Swapped ← TRUE
ENDIF
NEXT Index
Limit ← Limit - 1
UNTIL Swapped = FALSE

Cada passada leva o maior valor restante para o final
Coloque as etapas de uma passagem de bubble sort e seu término em ordem.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
Redefina a flag, varra e troque, encolha o limite, pare quando toda uma passagem não fizer troca alguma.
Exemplo resolvido: onde estão as marcas da ordenação bolha
- O loop externo que repete até que uma passagem não faça trocas; a bandeira
Swappedredefinida paraFALSEno início de cada passagem e definidaTRUEdentro doIF. - A troca de três linhas através de uma variável temporária. Duas linhas perdem um valor.
- O limite decrescente, um menos a cada passada, porque o maior valor já atingiu o final.
- Em palavras, para uma questão de refinamento passo a passo: repita até ordenar; em cada passada compare pares adjacentes; troque qualquer par fora de ordem; após cada passada o maior valor não ordenado está no final.
Quais recursos ganham pontos em uma bubble sort eficiente? Selecione todos que se aplicam.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Flag, troca com temporário, limite decrescente: esses são os pontos. Copiar a matriz não faz parte do algoritmo.
Exemplo resolvido: remover e inserir
- Remover um item: encontre o seu índice com uma busca linear; mova cada elemento posterior um lugar em direção ao início para fechar a lacuna; marque o último elemento como não utilizado, ou reduza a contagem.
- Inserir num array ordenado: encontre o primeiro índice cujo elemento é maior; mova esse elemento e todos os posteriores um lugar em direção ao final, começando pelo último; armazene o novo valor na lacuna.
- Mova do fim ao abrir uma lacuna e do início ao fechá-la, caso contrário sobrescreva o valor que está prestes a mover.
Uma matriz segura muitos itens do MESMO tipo acessados por índice, enquanto um registro agrupa campos de (possivelmente) TIPOS DIFERENTES acessados por nome.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Uma matriz 2-D se adapta a uma grade (linhas × colunas); um registro se adapta a uma coisa descrita por vários campos nomeados.
Marcas que escapam
[0:99]contém 100 elementos. Conte ambos os limites.- Um índice é um
INTEGER; uma declaração precisa do tipo além dos limites. Grid[row, column]: linha primeiro. Trocá-los lê a célula errada em todos os loops aninhados.- Uma troca precisa de uma variável temporária; uma busca precisa de um caminho "não encontrado"; uma ordenação bolha termina quando uma passagem não faz nenhuma troca, não após um número fixo de passagens.
Entendeu?
- Um array armazena um número fixo de elementos do mesmo tipo sob um único identificador, acessado por um índice entre o limite inferior e o limite superior; count = upper − lower + 1
- 1-D é uma lista, 2-D é uma tabela
[row, column]percorrida por laços aninhados; declare com limites e tipo - busca linear:
FoundAt ← -1, loop, armazene o índice, teste após o loop; maior valor: comece emA[1], mantenha a posição - ordenação bolha: passagens de comparação e troca adjacentes com uma temporária, uma bandeira
Swapped, um limite decrescente, até que uma passagem não faça trocas