אלגוריתמי מערכים: מקסימום, ספירה, חיפוש, ממוצע
משימות נפוצות עם מערכים
- משימות מסוימות על מערכים מופיעות שוב ושוב: למצוא את ה-סכום, את ה-גדול ביותר, את ה-קטן ביותר או לספור פריטים.
- כל אחת מהן משתמשת באותה רעיון: להתחיל בניחוש, ולאחר מכן לעבור על המערכת ולעדכן אותו.
- דפוסי אלו מופיעים כל הזמן במבחן AP CSA.
סכום וספירה
- שמרו על סכום מצטבר שמתחיל ב-0, והוסיפו כל ערך.
- כדי לספור פריטים שעומדים במבחן, התחילו סופר ב-0 והוסיפו 1 כאשר הבדיקה היא נכונה.
- למטה אנו סופרים כמה ערכים הם זוגיים (
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
}
}
מציאת המקסימום
- התחילו בהנחה שהערך הראשון הוא הגדול ביותר:
int max = a[0];. - עבור על שאר האלמנטים. אם ערך גדול יותר מ-
max, הפוך אותו לmaxחדש. - זה עובד גם עבור מספרים שליליים, כי הניחוש מגיע מהמערכת עצמה.
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
}
}
מציאת המינימום
- המינימום משתמש באותה צורה – רק הפכו את הבדיקה ל-
<. - התחילו עם
int min = a[0];ושמרו על הערך הקטן ביותר שראיתם. - לעולם אל תתחילו עם
minבערך 0; ערך אמיתי מהמערכת הוא ניחוש ראשון בטוח.
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
}
}
חיפוש ערך
- למצוא איפה ערך נמצא, חלוק את האינדקס והשווה כל אלמנט.
- החזר את האינדקס ברגע שמצאת אותו.
- אם החיפוש מסתיים ללא התאמה, החזר
-1כדי לציין "לא נמצא".
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
}
}
ממוצע
- ממוצע = סכום חלקי למספר. מספר זה הוא
a.length. - כדי לקבל תוצאה בעלת נקודה עשרית, חלק ב-
(double) a.length, כך שהחישוב לא יהיה חילוק שלם. (double)ממיר את האורך לערך עם נקודה עשרית לפני החילוק.
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
}
}
טעויות נפוצות
- התחל מקסימום או מינימום מהאלמנט הראשון, ואז השווה לשאר.
- אל תעבור מעבר ל-
a.length - 1.
כעת תנסו בעצמכם
- כל משימה משלימה שיטה שה-Harness קורא לה עם כמה מערכים.
- השתמש בחוזרים בדגמים הנ
- השתמשו ב-Check answer כדי לקמפיל את הקוד שלך עם הבדיקות הסופקות ולצפות בתוצאות. שמרו את ממשקי המחלקה והשיטה המוצגים בתחילת העבודה.
סריקת מערך למציאת המקסימום
מעבר אחד שומר על מקסימום נצחי, ומעדכן אותו כאשר מופיע ערך גדול יותר.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
השלם max(int[] a) כך שיחזיר את הערך הגדול ביותר במערך. ניתן להניח שהמערך מכיל לפחות ערך אחד. הוא חייב לעבוד גם עם מספרים שליליים.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
השלם countEven(int[] a) כך שיחזיר כמה ערכים הם זוגיים. ערך הוא זוגי כאשר v % 2 == 0. מערך ריק מחזיר 0.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
השלם indexOf(int[] a, int target). החזר את האינדקס של הפעם הראשונה שבה target מופיע. אם הוא לא נמצא במערך, החזר -1.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
השלם average(int[] a). החזר את הממוצע של הערכים כמספר עשרוני double. חלק ב(double) a.length כדי לקבל ערך עשרוני ולא חלוקה שלמה. ניתן להניח שהמערך אינו ריק.
לחץ על הרץ כדי לראות את התוצא כאן.