Algoritmos de array: max, count, search, average
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.
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.
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.
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.
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.
Erros comuns
- Comece um max ou min do primeiro elemento, depois compare o resto.
- Não leia além do final da matriz.
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.
Escaneando um array
Uma passada mantém um resultado acumulado (máximo, soma, contagem) através do array.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
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.
Clique em Executar para ver a saída aqui.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
Complete int count_even(const int a[], int n) para que retorne quantos itens são pares. Use % 2. Não escreva um main.
Clique em Executar para ver a saída aqui.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
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.
Clique em Executar para ver a saída aqui.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
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.
Clique em Executar para ver a saída aqui.