Array algorithms: max, count, search, average · Algoritmos de arrays: 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.
Cuatro trabajos clásicos de arreglos
- La mayoría del trabajo con arreglos corresponde a una de cuatro exploraciones: encontrar el máximo, contar coincidencias, buscar un valor o calcular un promedio.
- Cada uno es un único bucle
forsobre el arreglo, con una variable que guarda algo. - Una vez que se conocen estos cuatro, la mayoría de los problemas de arreglos son un pequeño cambio en uno de ellos.
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.
Encontrar el máximo
- Comience asumiendo que el primer elemento es el más grande:
int best = a[0];. - Luego examine el resto. Si un elemento es mayor que
best, se convierte en el nuevobest. - Esto funciona también para números negativos, porque se parte de un elemento real, no de
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.
Contar con una condición
- Un contador comienza en
0y suma1cada vez que un elemento pasa una prueba. - Por ejemplo, contar números pares probando
a[i] % 2 == 0dentro del bucle. - El valor final del contador es su respuesta.
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.
Búsqueda lineal
- Para buscar, recorra el arreglo y compare cada elemento con el objetivo.
- Devuelva el índice tan pronto como encuentre una coincidencia. Si el bucle termina sin coincidencia, devuelva
-1. -1es una señal común de "no encontrado" porque nunca es un í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.
Promedio sin errores de división entera
- Sume todos los elementos en un total de tipo
int, luego divida porn. - Al dividir dos
ints se descarta la fracción, así que haga un cast:(double)total / n. - Devuelva un
doublepara que quien llame obtenga el promedio exacto.
Common mistakes
- Start a max or min from the first element, then compare the rest.
- Do not read past the end of the array.
Errores comunes
- Inicie un máximo o mínimo desde el primer elemento, luego compare el resto.
- No lea más allá del final del arreglo.
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.
Ahora practique
- Pase el arreglo y su longitud
n, y seleccione la variable correcta de "recordatorio" para cada tarea. - No escriba un
main— el validador proporciona uno.
Scanning an array · Escaneo de un array
One pass keeps a running result (max, sum, count) across the array. · Un solo recorrido mantiene un resultado acumulado (máximo, suma, conteo) a lo largo del 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 · no write a main. · Completa int max(const int a[], int n) para que devuelva el elemento más grande (asume n >= 1). Inicia desde a[0] para que los negativos funcionen correctamente. No escribas una main.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
Complete int count_even(const int a[], int n) so it returns how many items are even. Use % 2. Do not · no write a main. · Completa int count_even(const int a[], int n) para que devuelva cuántos elementos son pares. Usa % 2. No escribas una main.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
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 · no write a main. · Completa int index_of(const int a[], int n, int target) para que devuelva el índice de la primera aparición de target, o -1 si no se encuentra. No escribas una main.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
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 · no write a main. · Completa double average(const int a[], int n) para que devuelva el promedio de los elementos (asume n >= 1). Castea a doble para evitar la división entera. No escribas una main.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.