אלגוריתמי מערכים: מקסימום, ספירה, חיפוש, ממוצע
ארבע משימות קלאסיות למערך
- רוב העבודה עם מערכים היא אחד מארבע סריקות: מציאת מקסימום, ספירת התאמות, חיפוש ערך, או לקיחת ממוצע.
- כל אחת מהן היא לולאה
forיחידה על המערך, עם משתנה הזוכר משהו. - ברגע שידעתם את ארבע אלו, רוב בעיות המערך הן שינוי קטן באחת מהן.
מציאת הערך המקסימלי
- התחל בהנחה שהפריט הראשון הוא הגדול ביותר:
int best = a[0];. - לאחר מכן סורק את שאר הפריטים. אם פריט גדול יותר מ-
best, הוא הופך ל-bestחדש. - דבר זה עובד גם עבור מספרים שליליים, משום שמתחילים מפריט אמיתי ולא מ-
0.
ספירה עם תנאי
- סופר מתחיל בערך
0ומוסיף1בכל פעם שפריט עובר בדיקה. - לדוגמה, לספור מספרים זוגיים על ידי בדיקת
a[i] % 2 == 0בתוך הלולאה. - הערך הסופי של הסופר הוא התשובה שלך.
חיפוש ליניארי
- כדי לבצע חיפוש, לעבור על המערך ולהשוות כל פריט למטרה.
- להחזיר את ה-אינדקס ברגע שמצאים התאמה. אם הלולאה נגמרת ללא התאמה, להחזיר
-1. -1הוא אות נפוץ ל"לא נמצא" כי לעולם לא אינדקס תקף.
ממוצע ללא שגיאות חילוק שלמים
- לחבר את כל הפריטים לתוצאת סיכום ב-
int, ואז לחלק ב-n. - חלוקה של שני
ints מבטלת את השבר, ולכן יש להמיר סוג:(double)total / n. - להחזיר ערך
doubleכך שהקורא יקבל את הממוצע המדויק.
טעויות נפוצות
- התחל מקסימום או מינימום מהאלמנט הראשון, ואז השווה לשאר.
- לא לקרוא מעבר לסוף המערך.
כעת תנסו בעצמכם
- לעבור על המערך ואת אורכו
n, ולבחור את משתנה הזיכרון הנכון לכל משימה. - אל תכתוב
main— הבוקר מספק אותו already.
סריקה של מערכת
מעבר אחד שומר על תוצאה רצה (מקסימום, סך, ספירה) לאורך המערך.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
השלם int max(const int a[], int n) כדי להחזיר את הפריט הגדול ביותר (הנח n >= 1). התחל מ-a[0] כדי ששליליים יעבדו. אל ת כתוב main.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
שלים את int count_even(const int a[], int n) כך שתחזיר כמה פריטים במערך הם זוגיים. השתמש ב-% 2. אל תכתוב main.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
השלם int index_of(const int a[], int n, int target) כך שתחזיר את האינדקס של ה-target הראשון, או -1 אם הוא לא קיים. אל תכתב פונקציה main.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
השלם double average(const int a[], int n) כך שתחזיר את הממוצע של הפריטים (הנחה: n >= 1). ביצע סוגיית סדר כדי למנוע חילוק שלמים. אל תכתב פונקציה main.
לחץ על הרץ כדי לראות את התוצא כאן.