Algorithmes de tableau : max, count, search, average
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.
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.
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.
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.
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.
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.
À 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.
Parcourir un tableau
Un seul passage conserve un résultat cumulatif (max, somme, compteur) à travers le tableau.
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Cliquez sur Exécuter pour voir le résultat ici.