Array algorithms: max, count, search, average · Algoritmos de array: max, count, search, average
Four classic array jobs
- Most array work is one of four scans: find the maximum, count matches, search for a value, or take an average.
- Each one is a single
forloop over the array, with a variable that remembers something. - Once you know these four, most array problems are a small change to one of them.
Quatro tarefas clássicas de matriz
- A maioria dos trabalhos com matrizes é uma das quatro varreduras: encontrar o máximo, contar coincidências, pesquisar um valor ou calcular a média.
- Cada uma é um único loop
forsobre a matriz, com uma variável que lembra algo. - Uma vez que você conhece essas quatro, a maioria dos problemas de matriz é uma pequena alteração em uma delas.
Finding the maximum
- Start by assuming the first item is the biggest:
int best = a[0];. - Then look at the rest. If an item is bigger than
best, it becomes the newbest. - This works for negative numbers too, because you start from a real item, not
0.
Encontrando o máximo
- Comece assumindo que o primeiro item é o maior:
int best = a[0];. - Depois olhe o resto. Se um item for maior que
best, ele se torna o novobest. - Isso funciona também para números negativos, porque você começa com um item real, não com
0.
Counting with a condition
- A counter starts at
0and adds1each time an item passes a test. - For example, count even numbers by testing
a[i] % 2 == 0inside the loop. - The counter's final value is your answer.
Contando com uma condição
- Um contador começa em
0e soma1sempre que um item passa em um teste. - Por exemplo, conte números pares testando
a[i] % 2 == 0dentro do loop. - O valor final do contador é sua resposta.
Linear search
- To search, walk the array and compare each item to the target.
- Return the index as soon as you find a match. If the loop ends with no match, return
-1. -1is a common "not found" signal because it is never a valid index.
Busca linear
- Para pesquisar, percorra a matriz e compare cada item com o alvo.
- Retorne o índice assim que encontrar uma correspondência. Se o loop terminar sem correspondência, retorne
-1. -1é um sinal comum de "não encontrado" porque nunca é um índice válido.
Average without integer-division bugs
- Add all the items into an
inttotal, then divide byn. - Dividing two
ints drops the fraction, so cast:(double)total / n. - Return a
doubleso the caller gets the exact average.
Média sem erros de divisão inteira
- Some todos os itens em um total de
int, depois divida porn. - Dividir dois
ints elimina a fração, então faça cast:(double)total / n. - Retorne um
doublepara que o chamador obtenha a média exata.
Common mistakes
- Start a max or min from the first element, then compare the rest.
- Do not read past the end of the array.
Erros comuns
- Comece um max ou min do primeiro elemento, depois compare o resto.
- Não leia além do final da matriz.
Now you try
- Pass the array and its length
n, and pick the right "remember" variable for each job. - Do not write a
main— the checker provides one.
Agora você tenta
- Passe a matriz e seu comprimento
n, e escolha a variável de "lembrança" certa para cada tarefa. - Não escreva um
main— o verificador fornece um.
Scanning an array · Escaneando um array
One pass keeps a running result (max, sum, count) across the array. · Uma passada mantém um resultado acumulado (máximo, soma, contagem) através do array.
Complete int max(const int a[], int n) so it returns the largest item (assume n >= 1). Start from a[0] so negatives work. Do not · não write a main. · Complete int max(const int a[], int n) para que retorne o maior item (assuma n >= 1). Comece de a[0] para que negativos funcionem. Não escreva um main.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Complete int count_even(const int a[], int n) so it returns how many items are even. Use % 2. Do not · não write a main. · Complete int count_even(const int a[], int n) para que retorne quantos itens são pares. Use % 2. Não escreva um main.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Complete int index_of(const int a[], int n, int target) so it returns the index of the first target, or -1 if it is not there. Do not · não write a main. · Complete int index_of(const int a[], int n, int target) para retornar o índice do primeiro target, ou -1 se não houver. Não escreva um main.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Complete double average(const int a[], int n) so it returns the average of the items (assume n >= 1). Cast to avoid integer division. Do not · não write a main. · Complete double average(const int a[], int n) para que retorne a média dos itens (assuma n >= 1). Casting para evitar divisão inteira. Não escreva um main.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.