Array algorithms: max, count, search, average · Algorithmes de tableau : max, count, search, average
Common array jobs
- Some array tasks come up again and again: find the sum, the biggest, the smallest, or count items.
- Each one uses the same idea: start with a guess, then loop and update it.
- These patterns appear all the time on the AP CSA exam.
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.
Sum and count
- Keep a running total that starts at 0, and add each value.
- To count items that pass a test, start a counter at 0 and add 1 when the test is true.
- Below we count how many values are even (
v % 2 == 0).
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
}
}
Find the maximum
- Start by guessing the first value is the biggest:
int max = a[0];. - Loop through the rest. If a value is bigger than
max, make it the newmax. - This works for negative numbers too, because the guess comes from the array itself.
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
}
}
Find the minimum
- The minimum uses the same shape — just flip the test to
<. - Start with
int min = a[0];and keep the smallest value you see. - Never start
minat 0; a real value from the array is a safe first guess.
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
}
}
Search for a value
- To find where a value is, loop the index and compare each element.
- Return the index as soon as you find it.
- If the loop finishes with no match, return
-1to mean "not found".
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
}
}
Average
- Average = sum divided by count. The count is
a.length. - To get a decimal, divide by
(double) a.length, so the math is not integer division. (double)turns the length into a decimal before the division.
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
}
}
Common mistakes
- Start a max or min from the first element, then compare the rest.
- Do not read past
a.length - 1.
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.
Now you try
- Each task completes a method the Harness calls with several arrays.
- Reuse the patterns above: a running total, a "best so far", or a counter.
- Press Run to compile, then Check answer.
À 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.
- Appuyez sur Run pour compiler, puis sur Check answer.
Scanning an array for the max · Balayage d'un tableau pour trouver le max
One pass keeps a running max, updating it when a bigger value appears. · Un seul passage garde un max courant, le met à jour quand une valeur plus grande apparaît.
Complete max(int[] a) so it returns the largest value in the array. You may assume the array has at least one value. It must work with negative numbers too. · 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.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Complete countEven(int[] a) so it returns how many values are even. A value is even when v % 2 == 0. An empty array returns 0. · 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.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Complete indexOf(int[] a, int target). Return the index of the first · premier time · temps target appears. If it is not in the array, return -1. · 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.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Complete average(int[] a). Return the average of the values as a double. Divide by (double) a.length so you get a decimal, not integer division. You may assume the array is not empty. · 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.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.