Array algorithms: max, count, search, average · Algorithmes de tableau : 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.
Quatre tâches classiques de tableau
- La plupart des travaux sur les tableaux consistent en quatre scans : trouver le maximum, compter les correspondances, chercher une valeur, ou calculer la moyenne.
- Chacun est une simple boucle
forsur le tableau, avec une variable qui retient quelque chose. - Une fois que vous connaissez ces quatre, la plupart des problèmes de tableau sont une petite modification de l'un d'eux.
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.
Trouver le maximum
- Commencez par supposer que le premier élément est le plus grand :
int best = a[0];. - Ensuite, regardez le reste. Si un élément est plus grand que
best, il devient le nouveaubest. - Cela fonctionne aussi avec les nombres négatifs, car vous partez d'un élément réel, pas 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.
Compter avec une condition
- Un compteur commence à
0et ajoute1à chaque fois qu'un élément passe un test. - Par exemple, compter les nombres pairs en testant
a[i] % 2 == 0à l'intérieur de la boucle. - La valeur finale du compteur est votre réponse.
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.
Recherche linéaire
- Pour chercher, parcourir le tableau et comparer chaque élément à la cible.
- Retournez l'index dès que vous trouvez une correspondance. Si la boucle se termine sans correspondance, retournez
-1. -1est un signal courant de "non trouvé" car c'est jamais un index valide.
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.
Moyenne sans bugs de division entière
- Additionnez tous les éléments dans un total
int, puis divisez parn. - Diviser deux
intfait perdre la fraction, donc castez :(double)total / n. - Retournez un
doublepour que l'appelant obtienne la moyenne exacte.
Common mistakes
- Start a max or min from the first element, then compare the rest.
- Do not read past the end of the array.
Erreurs courantes
- Commencez un max ou min à partir du premier élément, puis comparez le reste.
- Ne lisez pas au-delà de la fin du tableau.
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.
À vous maintenant
- Passez le tableau et sa longueur
n, et choisissez la bonne variable de "retention" pour chaque tâche. - N'écrivez pas de
main— le vérificateur en fournit une.
Scanning an array · Parcourir un tableau
One pass keeps a running result (max, sum, count) across the array. · Un seul passage conserve un résultat cumulatif (max, somme, compteur) à travers le tableau.
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 · non write a main. · Complétez int max(const int a[], int n) pour qu'il retourne l'élément le plus grand (supposez n >= 1). Commencez à a[0] pour que les négatifs fonctionnent. Ne pas écrire de main.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Complete int count_even(const int a[], int n) so it returns how many items are even. Use % 2. Do not · non write a main. · Complétez int count_even(const int a[], int n) pour qu'il retourne combien d'éléments sont pairs. Utilisez % 2. Ne pas écrire de main.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
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 · non write a main. · Complétez int index_of(const int a[], int n, int target) pour qu'il retourne l'index du premier target, ou -1 s'il n'y est pas. Ne pas écrire de main.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
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 · non write a main. · Complétez double average(const int a[], int n) pour qu'il retourne la moyenne des éléments (supposez n >= 1). Castez pour éviter la division entière. Ne pas écrire de main.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.