שאלת מבחן במבוא למדעי המחשב - האוניברסיטה הפתוחה 2024 - מעקב אחר קוד

במחלקה `Q5` נתונות השיטות הסטטיות הבאות: ```java public class Q5 { public static int what(int[] a) { int p=0; for(int i=1; i<a.length; i++) if(a[p]<a[i]) p=i; return a[p]; } public static int secret(int []a, int k) { int [] temp = new int[what(a)+1]; int i, total = 0; for (i=0; i<a.length; i++) temp[a[i]]++; for (i=0; i<temp.length && total<k; i++) total+=temp[i]; return i-1; } public static void main (String [] args) { int []a = {71,5,2,12,84,71,85,192,71,85}; for (int i=1; i<=a.length; i++) System.out.println(i+": "+secret(a, i)); } } ``` סעיף א (2 נקודות) נניח שנתון מערך חד ממדי `a`, שמלא במספרים שלמים. מה מבצעת השיטה `what` אם נפעיל אותה עם הפרמטר שהוא המערך `a`? הסבירו בקצרה מה השיטה עושה ולא כיצד היא מבצעת זאת. שימו לב, עליכם לתת תיאור ממצה של מה עושה השיטה באופן כללי, ולא תיאור של מה עושה כל שורה בשיטה, או איך היא מבצעת זאת. התייחסו למקרי קצה. סעיף ב (4 נקודות) נניח שנתון מערך חד ממדי `a`, שמלא במספרים אי שליליים. מה מבצעת השיטה `secret` אם נפעיל אותה עם הפרמטרים שהם המערך `a` ומספר שלם `k`? הסבירו בקצרה מה השיטה עושה ולא כיצד היא מבצעת זאת. שימו לב, עליכם לתת תיאור ממצה של מה עושה השיטה באופן כללי, ולא תיאור של מה עושה כל שורה בשיטה, או איך היא מבצעת זאת. התייחסו למקרי קצה. סעיף ג (10 נקודות) אם נריץ את השיטה `main`, מה יודפס על הפלט? (לא בהכרח כל השורות יתמלאו)

רמז: השיטה `secret` משתמשת במערך עזר כדי לספור את תדירות הופעתם של המספרים במערך הקלט, טכניקה המהווה בסיס למיון ספירה.

פתרון: ### סעיף א השיטה `what` מחזירה את האיבר **המקסימלי** (הגדול ביותר) במערך `a`. היא עוברת על כל איברי המערך ומעדכנת מצביע `p` לאינדקס הנוכחי בכל פעם שמוצאת ערך גדול מ-`a[p]`. בסוף, מחזירה את `a[p]` — ערך המקסימום. השיטה עובדת עבור מערכים המכילים מספרים שלמים כלשהם (חיוביים, שליליים ואפסים). $\blacksquare$ ### סעיף ב **מה עושה `secret(a, k)`:** השיטה `secret` מחפשת במערך `a` (המכיל מספרים **אי-שליליים**) את ה-**k-הקטן ביותר** (סדר עולה). היא: 1. יוצרת מערך עזר `temp` בגודל `what(a)+1` (גדול מהמקסימום ב-1). 2. עבור כל איבר `a[i]`, מגדילה ב-1 את `temp[a[i]]` — כך `temp[v]` שומר כמה פעמים מופיע הערך `v` ב-`a`. 3. עוברת על `temp` בסדר עולה, סופרת איברים מצטבר, ומחזירה את הערך `j` שכאשר מגיעים לפעם ה-`k` המצטברת נמצאת ב-`j`. לדוגמה: `a = {3, 1, 4, 1, 5, 9, 2, 6}`, `k = 3` — הערכים בסדר עולה: 1, 1, 2, 3, 4, 5, 6, 9; ה-3 הקטן הוא **2**. **מקרים מיוחדים:** - אם `k <= 0` — השיטה מחזירה -1. - אם `k > n` (גדול ממספר האיברים) — תגיע לסוף הלולאה ותחזיר את הערך המקסימלי. ### סעיף ג נריץ את `main`: ``` a = {3, 1, 4, 1, 5, 9, 2, 6} ``` - `what(a)` = 9 (המקסימום). - `secret(a, 3)` = 2 (הערך ה-3 הקטן: 1, 1, **2**). - `secret(a, 7)` = 6 (הערך ה-7 הקטן: 1, 1, 2, 3, 4, 5, **6**). הפלט שיודפס: ``` 9 2 6 ```