Algorithmes de tableau : max, count, search, average
Tâches courantes de tableau
- Certaines tâches de tableau reviennent souvent : trouver la somme, le plus grand, le plus petit, ou compter les éléments.
- Chacun utilise la même idée : commencez avec une supposition, puis bouclez et mettez à jour.
- Ces modèles apparaissent tout le temps sur l'examen AP CSA.
Somme et comptage
- Gardez un total cumulé qui commence à 0, et ajoutez chaque valeur.
- Pour compter les éléments qui passent un test, commencez un compteur à 0 et ajoutez 1 quand le test est vrai.
- Ci-dessous, nous comptons combien de valeurs sont paires (
v % 2 == 0).
public class Main {
public static void main(String[] args) {
int[] a = {3, 4, 7, 10};
int evens = 0;
for (int v : a) {
if (v % 2 == 0) {
evens = evens + 1;
}
}
System.out.println(evens); // 2
}
}
Trouver le maximum
- Commencez en supposant que la première valeur est la plus grande :
int max = a[0];. - Bouclez à travers le reste. Si une valeur est plus grande que
max, faites-en la nouvellemax. - Cela fonctionne aussi pour les nombres négatifs, car la supposition vient du tableau lui-même.
public class Main {
public static void main(String[] args) {
int[] a = {3, 9, 2, 7};
int max = a[0];
for (int i = 1; i < a.length; i++) {
if (a[i] > max) {
max = a[i];
}
}
System.out.println(max); // 9
}
}
Trouver le minimum
- Le minimum utilise la même forme — juste inversez le test en
<. - Commencez avec
int min = a[0];et gardez la plus petite valeur que vous voyez. - Ne commencez jamais
minà 0 ; une vraie valeur du tableau est une bonne première supposition.
public class Main {
public static void main(String[] args) {
int[] a = {3, 9, 2, 7};
int min = a[0];
for (int i = 1; i < a.length; i++) {
if (a[i] < min) {
min = a[i];
}
}
System.out.println(min); // 2
}
}
Chercher une valeur
- Pour trouver où se trouve une valeur, bouclez l'index et comparez chaque élément.
- Retournez l'index dès que vous le trouvez.
- Si la boucle se termine sans correspondance, retournez
-1pour dire "non trouvé".
public class Main {
public static void main(String[] args) {
int[] a = {5, 8, 13, 21};
int target = 13;
int found = -1;
for (int i = 0; i < a.length; i++) {
if (a[i] == target) {
found = i;
break; // stop at the first match
}
}
System.out.println(found); // 2
}
}
Moyenne
- Moyenne = somme divisée par le comptage. Le comptage est
a.length. - Pour obtenir un décimal, divisez par
(double) a.length, afin que le calcul ne soit pas une division entière. (double)convertit la longueur en décimal avant la division.
public class Main {
public static void main(String[] args) {
int[] a = {2, 3, 10};
int total = 0;
for (int v : a) {
total = total + v;
}
double avg = total / (double) a.length;
System.out.println(avg); // 5.0
}
}
Erreurs courantes
- Commencez un max ou min à partir du premier élément, puis comparez le reste.
- Ne lisez pas au-delà de
a.length - 1.
À vous maintenant
- Chaque exercice complète une méthode que l'Harness appelle avec plusieurs tableaux.
- Réutilisez les modèles ci-dessus : un total cumulé, un "le meilleur jusqu'ici", ou un compteur.
- Utilisez Vérifier la réponse pour compiler votre code avec les tests fournis et voir les résultats. Conservez les interfaces de classe et de méthode montrées dans l'en-tête.
Balayage d'un tableau pour trouver le max
Un seul passage garde un max courant, le met à jour quand une valeur plus grande apparaît.
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
Complétez max(int[] a) pour qu'elle retourne la plus grande valeur du tableau. Vous pouvez supposer que le tableau a au moins une valeur. Il doit aussi fonctionner avec des nombres négatifs.
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 countEven(int[] a) pour qu'elle retourne combien de valeurs sont paires. Une valeur est paire quand v % 2 == 0. Un tableau vide retourne 0.
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 indexOf(int[] a, int target). Retournez l'indice de la première fois que target apparaît. S'il n'est pas dans le tableau, retournez -1.
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 average(int[] a). Retournez la moyenne des valeurs en tant que double. Divisez par (double) a.length pour obtenir une décimale, pas une division entière. Vous pouvez supposer que le tableau n'est pas vide.
Cliquez sur Exécuter pour voir le résultat ici.