Array algorithms: max, count, search, average · אלגוריתמי מערכים: מקסימום, ספירה, חיפוש, ממוצע
Four classic array jobs
- Most array work is one of four scans: find the maximum, count matches, search for a value, or take an average.
- Each one is a single
forloop over the array, with a variable that remembers something. - Once you know these four, most array problems are a small change to one of them.
ארבע משימות קלאסיות למערך
- רוב העבודה עם מערכים היא אחד מארבע סריקות: מציאת מקסימום, ספירת התאמות, חיפוש ערך, או לקיחת ממוצע.
- כל אחת מהן היא לולאה
forיחידה על המערך, עם משתנה הזוכר משהו. - ברגע שידעתם את ארבע אלו, רוב בעיות המערך הן שינוי קטן באחת מהן.
Finding the maximum
- Start by assuming the first item is the biggest:
int best = a[0];. - Then look at the rest. If an item is bigger than
best, it becomes the newbest. - This works for negative numbers too, because you start from a real item, not
0.
מציאת הערך המקסימלי
- התחל בהנחה שהפריט הראשון הוא הגדול ביותר:
int best = a[0];. - לאחר מכן סורק את שאר הפריטים. אם פריט גדול יותר מ-
best, הוא הופך ל-bestחדש. - דבר זה עובד גם עבור מספרים שליליים, משום שמתחילים מפריט אמיתי ולא מ-
0.
Counting with a condition
- A counter starts at
0and adds1each time an item passes a test. - For example, count even numbers by testing
a[i] % 2 == 0inside the loop. - The counter's final value is your answer.
ספירה עם תנאי
- סופר מתחיל בערך
0ומוסיף1בכל פעם שפריט עובר בדיקה. - לדוגמה, לספור מספרים זוגיים על ידי בדיקת
a[i] % 2 == 0בתוך הלולאה. - הערך הסופי של הסופר הוא התשובה שלך.
Linear search
- To search, walk the array and compare each item to the target.
- Return the index as soon as you find a match. If the loop ends with no match, return
-1. -1is a common "not found" signal because it is never a valid index.
חיפוש ליניארי
- כדי לבצע חיפוש, לעבור על המערך ולהשוות כל פריט למטרה.
- להחזיר את ה-אינדקס ברגע שמצאים התאמה. אם הלולאה נגמרת ללא התאמה, להחזיר
-1. -1הוא אות נפוץ ל"לא נמצא" כי לעולם לא אינדקס תקף.
Average without integer-division bugs
- Add all the items into an
inttotal, then divide byn. - Dividing two
ints drops the fraction, so cast:(double)total / n. - Return a
doubleso the caller gets the exact average.
ממוצע ללא שגיאות חילוק שלמים
- לחבר את כל הפריטים לתוצאת סיכום ב-
int, ואז לחלק ב-n. - חלוקה של שני
ints מבטלת את השבר, ולכן יש להמיר סוג:(double)total / n. - להחזיר ערך
doubleכך שהקורא יקבל את הממוצע המדויק.
Common mistakes
- Start a max or min from the first element, then compare the rest.
- Do not read past the end of the array.
טעויות נפוצות
- התחל מקסימום או מינימום מהאלמנט הראשון, ואז השווה לשאר.
- לא לקרוא מעבר לסוף המערך.
Now you try
- Pass the array and its length
n, and pick the right "remember" variable for each job. - Do not write a
main— the checker provides one.
כעת תנסו בעצמכם
- לעבור על המערך ואת אורכו
n, ולבחור את משתנה הזיכרון הנכון לכל משימה. - אל תכתוב
main— הבוקר מספק אותו already.
Scanning an array · סריקה של מערכת
One pass keeps a running result (max, sum, count) across the array. · מעבר אחד שומר על תוצאה רצה (מקסימום, סך, ספירה) לאורך המערך.
Complete int max(const int a[], int n) so it returns the largest item (assume n >= 1). Start from a[0] so negatives work. Do not write a main. · השלם את int max(const int a[], int n) כך שתחזיר את הפריט הגדול ביותר (הנח that n >= 1). התחל מa[0] כדי שגם שליליים יעבדו. אל תכתוב פקודת main.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.
Complete int count_even(const int a[], int n) so it returns how many items are even. Use % 2. Do not write a main. · שלים את int count_even(const int a[], int n) כך שתחזיר כמה פריטים במערך הם זוגיים. השתמש ב-% 2. אל תכתוב main.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.
Complete int index_of(const int a[], int n, int target) so it returns the index of the first target, or -1 if it is not there. Do not write a main. · השלם int index_of(const int a[], int n, int target) כך שתחזיר את האינדקס של ה-target הראשון, או -1 אם הוא לא קיים. אל תכתב פונקציה main.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.
Complete double average(const int a[], int n) so it returns the average of the items (assume n >= 1). Cast to avoid integer division. Do not write a main. · השלם double average(const int a[], int n) כך שתחזיר את הממוצע של הפריטים (הנחה: n >= 1). ביצע סוגיית סדר כדי למנוע חילוק שלמים. אל תכתב פונקציה main.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.