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

לפניכם המחלקות `IntNode` ו- `IntList` . כל אחת בקובץ נפרד, כמובן. ```java public class IntNode { private int _data; private IntNode _next; public IntNode (int data, IntNode node) { _data = data; _next = node; } public IntNode getNext() { return _next; } public void setNext(IntNode node) { _next = node; } public int getData() { return _data; } public void setData(int data) { _data = data; } } //------------------------------------------------------------------------- public class IntList { private IntNode _head; public IntList() { _head = null; } } ``` נתונה רשימה מקושרת של קודקודים מסוג `IntNode`, כאשר `_head` מצביע על האיבר הראשון ברשימה: `_head -> [4] -> [2] -> [2] -> [5] -> [1] -> null` אנחנו נכתוב אותה כך {4, 2, 2, 5, 1}. בשאלה זו הניחו שכל המספרים ברשימה חיוביים. תזכורת: השיטה `Math.max(x, y)` מחזירה את המקסימום בין `x` ו- `y`. השיטה הבאה (`method1`) נמצאת בתוך המחלקה `IntList`: ```java public int method1() { if (_head == null) return 0; int m1 = 0; int m2 = _head.getData(); IntNode q = _head ; for (IntNode p = _head.getNext(); p != null; q = q.getNext(), p = p.getNext()) { if (q.getData() < p.getData ()) m2 = m2 + p.getData (); else { m1 = Math.max(m1, m2); m2 = p.getData(); } } return Math.max(m1, m2); } ``` סעיף א: (3 נקודות) נפעיל את השיטה `method1` על הרשימה {1, 2, 3, 2, 5, 1, 7}. איזה ערך תחזיר השיטה? סעיף ב: (4 נקודות) נפעיל את השיטה `method1` על הרשימה {1, 2, 2, 4}. איזה ערך תחזיר השיטה? סעיף ג: (7 נקודות) מה מבצעת השיטה `method1` באופן כללי? הסבירו בקצרה מה השיטה עושה ולא כיצד היא מבצעת זאת. הניחו שכל המספרים ברשימה חיוביים. שימו לב, עליכם לתת תיאור ממצה של מה עושה השיטה באופן כללי, ולא תיאור של מה עושה כל שורה בשיטה, או איך היא מבצעת זאת. מה משמעותו של הערך המוחזר מהשיטה `method1`? התייחסו למקרי קצה.

רמז: כדי להבין מה השיטה מבצעת, בצעו מעקב שיטתי אחר ערכי המשתנים `m1` ו-`m2` לאורך ריצת הלולאה, ושימו לב מתי כל אחד מהם מתעדכן.

פתרון: ### סעיף א נבצע מעקב אחר ערכי המשתנים `m1` ו-`m2` עבור הרשימה `{1, 2, 3, 2, 5, 1, 7}`: 1. **אתחול:** `m1` מאותחל ל-`0`. `m2` מאותחל לערך האיבר הראשון, `1`. 2. **איטרציה 1:** `q=1, p=2`. התנאי `1 < 2` מתקיים. `m2` הופך ל-`m2 + p.getData() = 1 + 2 = 3`. 3. **איטרציה 2:** `q=2, p=3`. התנאי `2 < 3` מתקיים. `m2` הופך ל-`m2 + p.getData() = 3 + 3 = 6`. 4. **איטרציה 3:** `q=3, p=2`. התנאי `3 < 2` **אינו** מתקיים. לכן, `m1` מתעדכן ל-`Math.max(m1, m2) = Math.max(0, 6) = 6`. המשתנה `m2` מתאפס ומתחיל ספירה חדשה מערכו של `p`, כלומר `m2 = 2`. 5. **איטרציה 4:** `q=2, p=5`. התנאי `2 < 5` מתקיים. `m2` הופך ל-`m2 + p.getData() = 2 + 5 = 7`. 6. **איטרציה 5:** `q=5, p=1`. התנאי `5 < 1` **אינו** מתקיים. `m1` מתעדכן ל-`Math.max(m1, m2) = Math.max(6, 7) = 7`. המשתנה `m2` מתאפס לערכו של `p`, כלומר `m2 = 1`. 7. **איטרציה 6:** `q=1, p=7`. התנאי `1 < 7` מתקיים. `m2` הופך ל-`m2 + p.getData() = 1 + 7 = 8`. 8. **סיום הלולאה.** 9. **החזרה:** השיטה מחזירה `Math.max(m1, m2) = Math.max(7, 8) = 8`. הערך המוחזר הוא **8**. ### סעיף ב נבצע מעקב אחר ערכי המשתנים `m1` ו-`m2` עבור הרשימה `{1, 2, 2, 4}`: 1. **אתחול:** `m1 = 0`, `m2 = 1`. 2. **איטרציה 1:** `q=1, p=2`. התנאי `1 < 2` מתקיים. `m2` הופך ל-`1 + 2 = 3`. 3. **איטרציה 2:** `q=2, p=2`. התנאי `2 < 2` **אינו** מתקיים. `m1` מתעדכן ל-`Math.max(0, 3) = 3`. המשתנה `m2` מתאפס לערכו של `p`, כלומר `m2 = 2`. 4. **איטרציה 3:** `q=2, p=4`. התנאי `2 < 4` מתקיים. `m2` הופך ל-`2 + 4 = 6`. 5. **סיום הלולאה.** 6. **החזרה:** השיטה מחזירה `Math.max(m1, m2) = Math.max(3, 6) = 6`. הערך המוחזר הוא **6**. ### סעיף ג השיטה מחזירה את **הסכום המקסימלי של תת-רשימה רציפה של איברים העולים באופן מונוטוני ממש**. **הסבר:** השיטה מזהה את כל תת-הרשימות הרציפות המקסימליות אשר איבריהן מקיימים סדר עולה ממש (כל איבר גדול ממש מקודמו). עבור כל תת-רשימה כזו, היא מחשבת את סכום איבריה. הערך המוחזר על ידי השיטה הוא הסכום הגדול ביותר מבין כל סכומי תת-הרשימות הללו. **מקרי קצה:** * **רשימה ריקה:** אם הרשימה ריקה (`_head == null`), השיטה תחזיר `0`. * **רשימה עם איבר אחד:** אם ברשימה יש איבר בודד, הלולאה כלל לא תתבצע, והשיטה תחזיר את ערכו של אותו איבר (מכיוון ש-`m1=0` ו-`m2` יכיל את ערך האיבר, וכל המספרים חיוביים). זהו התוצאה הנכונה, שכן הסכום המקסימלי הוא פשוט האיבר עצמו.