יישום אלגוריתמים על מערכים
הוצג| English | משמעות |
|---|---|
| traversal/træˈvɜːsl/ | מעבר על המבנה |
| index/ˈɪndeks/ | מדדק |
| linear search/ˈlɪnɪə sɜːtʃ/ | חיפוש ליניארי |
אלגוריתמים סטנדרטיים למערכים
- רוב משימות המערכות הן סיור (traversal) בתוך אחת ממספר דפוסים סטנדרטיים.
- סכום / ממוצע: צבור סך כל, ואז חלק ב-
length. - ספירה: הגדל בעוד שרכיב תואם לתנאי.
- מינימום / מקסימום: מעקב אחר הערך הקטן או הגדול שנצפה עד כה.
מציאת המקסימום
- התחל ב-
max = a[0](האלמנט הראשון), ואז עבור מהאינדקס1. if (a[i] > max) { max = a[i]; }בתוך הלולאה.- לאחר הלולאה,
maxמכיל את הערך הגדול ביותר במערכת. - התחל מהאלמנט הראשון, לא מ-
0—0עשוי להיות גדול מכל הערכים.
חיפוש אחר ערך
- כדי לבדוק האם ערך קיים, סור והשווה כל רכיב.
- החזר את המדד בו נמצא, או
-1אם הלולאה הסתיימה ללא התאמה. if (a[i] == target) return i;בתוך הלולאה;return -1;לאחר מכן.- זהו חיפוש ליניארי (יחידה 4.14 מטפלת בה לעומק).
הזזה ושינוי
- חלק מאלגוריתמים מזיזים או משנים אלמנטים — למשל, להזיז הכל שמאלה, או להכפיל כל ערך.
- שינוי דורש את לולאת המדדים כדי שתוכל להעניק ערך ל-
a[i] = .... - שמור על גבולות בקריאת
a[i+1]— המדד האחרון אין לו שכנות. - עקוב אחר המדדים בקפדנות כדי למנוע גישה מחוץ לגבולות.
**התחל חיפוש מקסימום/מינימום עם האלמנט הראשון, לא עם 0. ה-int max = 0; יכשל אם כל הערכים שליליים (ידווח בטעות על 0). השתמש ב-int max = a[0]; והתחל את המחזור מאינדקס 1. וכשאלגוריתם קורא a[i+1], עצור את המחזור ב-i < a.length - 1, אחרת האיטרציה האחרונה תיקרא מעבר לסוף.
מציאת המקסימום של a:
int max = a[0];for (int i = 1; i < a.length; i++) { if (a[i] > max) max = a[i]; }- עבור
a = {3, 9, 5}: ערך מקסימום הופך ל9.
אלגוריתמים על מערכים משלבים עיבר עם דפוס: סכום/ממוצע, ספירה, מינימום/מקסימום, או חיפוש (החזרת האינדקס או -1). יש לאייל מינימום/מקסימום בעזרת האלמנט הראשון, ולא 0. שינוי אלמנטים דורש לולאת אינדקס, וקריאת a[i+1] דורשת גבול צמוד יותר כדי להישאר בתחום המותר.
מציאת הערך המקסימלי
max מתחיל ב-a[0]=3, הופך ל-9, ולאחר מכן נשאר (a = {3,9,5}).
כדי למצוא את הערך המקסימלי במערך, יש להתחיל את max ב-...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
התחלה ב-0 תיכשל אם כל הערכים שליליים.
עבור a = {3, 9, 5}, מהו הערך המקסימלי?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
9 הוא האלמנט הגדול ביותר.
חיפוש ליניארי מחזיר מה אם היעד לא נמצא?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
לפי מקובל, -1 פירושו 'לא נמצא'.
אלגוריתם שקורא a[i+1] צריך לעגן תוך כדי ש-...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
עצירה מוקדת בשלב אחד משאירה את a[i+1] בתחומים.
שינוי אלמנטים במערך (a[i] = ...) דורש לולאת אינדקס, ולא for-each.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
for-each לא יכול להחזיר ערך לתוך המערך.