Arrays · Matrizes
| English | Português |
|---|---|
| array/əˈreɪ/ | array (matriz/lista) |
| element/ˈelɪmənt/ | elemento |
| index/ˈɪndeks/ | interface |
| 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/ | laços aninhados |
| linear search/ˈlɪnɪə sɜːtʃ/ | busca linear |
| bubble sort/ˈbʌbl sɔːt/ | ordenação por bolha |
Seat 14C
- A cinema has 300 seats. Its booking system does not have 300 variables called
Seat1A,Seat1B,Seat1C. It has one array 数组, and your ticket is an address into it: row 14, seat C. - One name, hundreds of values, each found by a number. Add a row and the code does not change; loop over the numbers and you have checked every seat.
- Almost every Paper 2 algorithm walks an array: searching it, summing it, sorting it, finding its largest value.
- This lesson is the vocabulary, the declarations, and the four algorithms the examiner asks for in pseudocode and in words.
Assento 14C
- Um cinema tem 300 assentos. Seu sistema de reservas não tem 300 variáveis chamadas
Seat1A,Seat1B,Seat1C. Ele tem um array 数组, e seu ingresso é um endereço nele: fileira 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.
The vocabulary
- An array is a data structure holding a fixed number of elements 元素 of the same data type under one identifier, each reached by an index 索引.
- The lower bound 下界 and upper bound 上界 are the first and last valid index. The number of elements is upper bound − lower bound + 1.
- The dimension 维度 is how many indices an element needs: one for a list, two for a table.
- In
ThisArray[n] ← 42the array has one dimension, the index is theINTEGERvariablen, and the element at that index receives42.
One identifier, an index for each element, bounds at both ends
O vocabulário
- Um array é 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 ú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
An array stores: · Uma matriz armazena:
An array is an ordered collection of same-type items accessed by index. (A record groups different types.) · Uma matriz é uma coleção ordenada de itens do mesmo tipo acessados por índice. (Um registro agrupa tipos diferentes.)
An array is a data structure holding many values of the ______ type under one name. · Uma matriz é uma estrutura de dados que segura muitos valores do tipo ______ sob um único nome.
Each value is reached by its index. · Cada valor é acessado pelo seu índice.
DECLARE Marks : ARRAY[0:99] OF INTEGER declares an array of ____ elements. · DECLARE Marks : ARRAY[0:99] OF INTEGER declara uma matriz de ____ elementos.
Upper bound minus lower bound plus one: 99 − 0 + 1 = 100. Both bounds are valid indices. · Limite superior menos limite inferior mais um: 99 − 0 + 1 = 100. Ambos os limites são índices válidos.
Worked example: declaring the array a task needs
- A declaration needs the identifier, the bounds and the data type.
- 120 readings that may have a decimal place:
DECLARE Data : ARRAY[1:120] OF REAL - A table of 150 rows and two columns of text:
DECLARE Names : ARRAY[1:150, 1:2] OF STRING - Say the count if asked:
[0:99]holds 100 elements, not 99.
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.
Which declaration holds a table of 150 rows and 2 columns of text? · Qual declaração segura uma tabela de 150 linhas e 2 colunas de texto?
Two dimensions, each with a lower and upper bound, and the element type. The second option is one long list; the third has no type; the fourth has no lower bounds. · 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.
Processing a 1-D array
- A
FORloop from the lower bound to the upper bound visits every element once. - For a sum, count, maximum or minimum, set a running variable before the loop and update it inside.
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.
2-D arrays
- The first index is the row, the second the column. Nested loops 嵌套循环 visit every cell: the outer loop over rows, the inner over columns.
- Use 1-D for a single sequence and 2-D when the data has two natural dimensions, such as a grid of seats or a table of marks by student and subject.
Grid[row, column], always in that order
Arrays 2-D
DECLARE Grid : ARRAY[1:3, 1:4] OF INTEGER
Grid[2, 3] ← 99 // row 2, column 3
- O primeiro índice é a fileira, o segundo a coluna. Loops aninhados 嵌套循环 visitam todas as células: o loop exterior sobre fileiras, o interior 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
Index a 2-D array by [row, column] · Indexe uma matriz 2-D por [linha, coluna]
A 2-D array is a grid. Grid[row, column] reaches exactly one cell — change the row and column to see which value you land on. · 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.
In Grid[2, 3], which cell is accessed? · Em Grid[2, 3], qual célula é acessada?
The first index is the row, the second the column — so row 2, column 3. · O primeiro índice é a linha, o segundo a coluna — então linha 2, coluna 3.
Worked example: a linear search that can say "not found"
- A linear search 线性查找 checks each element in turn from the first until the target is found or the end is reached.
-1can never be a valid index, so it means "not found". Initialise it before the loop and test it after. A search that never says "not found" loses a mark.
Exemplo resolvido: uma busca linear que pode dizer "não encontrado"
- Uma busca linear 线性查找 verifica cada elemento sucessivamente do primeiro até o alvo ser encontrado ou o fim ser atingido.
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.
A linear search finds a value by: · Uma busca linear encontra um valor por:
A linear search examines elements one by one from the start until it finds the target (or reaches the end). · Uma busca linear examina elementos um por um do início até encontrar o alvo (ou atingir o fim).
Setting FoundAt to -1 before a linear search lets the program report "not found" after the loop. · Definir FoundAt como -1 antes de uma busca linear permite que o programa relate "não encontrado" após o laço.
-1 is never a valid index, so if it is unchanged after the loop the target was not in the array. · -1 nunca é um índice válido, então se permanecer inalterado após o laço, o alvo não estava na matriz.
Largest value, and where it is
- Start
Largestat the first element, never at 0: the array might be all negative. - The same shape counts or outputs the non-blank elements: compare each with the marker for unused,
""or-1, and count only those that differ.
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.
Bubble sort
- A bubble sort 冒泡排序 makes repeated passes through the array comparing adjacent pairs and swapping those out of order, until a pass makes no swaps.
- After each pass the largest unsorted value has bubbled to the end, so the next pass can stop one place earlier.
Each pass carries the largest remaining value to the end
Ordenação bolha (Bubble sort)
- Uma ordenação bolha 冒泡排序 faz passadas repetidas pelo array comparando pares adjacentes e trocando os fora de ordem, até uma passada não fazer trocas.
- 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
Put the steps of one bubble-sort pass, and its ending, in order. · Coloque as etapas de uma passagem de bubble sort e seu término em ordem.
Reset the flag, sweep and swap, shrink the limit, stop when a whole pass made no swap. · Redefina a flag, varra e troque, encolha o limite, pare quando toda uma passagem não fizer troca alguma.
Worked example: where the bubble-sort marks are
- The outer loop that repeats until a pass makes no swaps; the
Swappedflag reset toFALSEat the start of each pass and setTRUEinside theIF. - The three-line swap through a temporary variable. Two lines lose a value.
- The shrinking limit, one less each pass, because the largest value has already reached the end.
- In words, for a stepwise-refinement question: repeat until sorted; on each pass compare adjacent pairs; swap any pair out of order; after each pass the largest unsorted value is at the end.
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.
Which features earn marks in an efficient bubble sort? Select all · todos that apply. · Quais recursos ganham pontos em uma bubble sort eficiente? Selecione todos que se aplicam.
Flag, swap with a temporary, shrinking limit: those are the marks. Copying the array is not part of the algorithm. · Flag, troca com temporário, limite decrescente: esses são os pontos. Copiar a matriz não faz parte do algoritmo.
Worked example: removing and inserting
- Remove an item: find its index with a linear search; move every later element one place towards the start so the gap closes; mark the last element as unused, or reduce the count.
- Insert into a sorted array: find the first index whose element is larger; move that element and every later one one place towards the end, starting from the last; store the new value in the gap.
- Move from the end when opening a gap and from the start when closing one, or you overwrite the value you are about to move.
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.
An array holds many items of the SAME type reached by index, while a record groups fields of (possibly) DIFFERENT types reached by name. · Uma matriz segura muitos itens do MESMO tipo acessados por índice, enquanto um registro agrupa campos de (possivelmente) TIPOS DIFERENTES acessados por nome.
A 2-D array suits a grid (rows × columns); a record suits one thing described by several named fields. · Uma matriz 2-D se adapta a uma grade (linhas × colunas); um registro se adapta a uma coisa descrita por vários campos nomeados.
Marks that slip away
[0:99]holds 100 elements. Count both bounds.- An index is an
INTEGER; a declaration needs the type as well as the bounds. Grid[row, column]: row first. Swapping them reads the wrong cell in every nested loop.- A swap needs a temporary variable; a search needs a "not found" path; a bubble sort ends when a pass makes no swaps, not after a fixed number of passes.
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.
You've got it
- an array holds a fixed number of same-type elements under one identifier, reached by an index between the lower and upper bound; count = upper − lower + 1
- 1-D is a list, 2-D is a table
[row, column]walked by nested loops; declare with bounds and type - linear search:
FoundAt ← -1, loop, store the index, test after the loop; largest value: start atA[1], keep the position - bubble sort: passes of adjacent compare-and-swap with a temporary, a
Swappedflag, a shrinking limit, until a pass makes no swaps
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