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

חלק א – עליכם לענות על כל השאלות בחלק זה במחברת הבחינה שאלה 1 (25 נקודות) נתון מערך דו-ממדי mat המלא במספרים אפס או אחד. נגדיר מסלול חוקי במערך כמסלול שעובר מתא המקור (source) לתא היעד (destination) ועובר רק בתאים שערכם הוא 1. אפשר לעבור מתא אחד לשני רק אם הוא שכן שלו מימין, משמאל, למעלה או למטה. לא באלכסון. כמו כן, אסור שיהיו מעגלים במסלול, כלומר, אי אפשר לבקר בתא שכבר היינו בו. כתבו שיטה סטטית רקורסיבית המקבלת כפרמטרים מערך mat מלא באפסים ואחדים, וכן שני מספרים שלמים x ו- y, ומחזירה את אורכו של המסלול הארוך ביותר האפשרי במערך מתא המקור (0,0) לתא היעד $(x, y)$. לדוגמא, במערך להלן, אם הפרמטרים הם $x = 2$, $y = 5$, אורכו של המסלול הארוך ביותר מתא המקור (0,0) לתא היעד (2,5) הוא 16, ומסומן במערך. $$ \begin{array}{c|c|c|c|c|c|c|c|} & \multicolumn{1}{c}{0} & \multicolumn{1}{c}{1} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{3} & \multicolumn{1}{c}{4} & \multicolumn{1}{c}{5} & \multicolumn{1}{c}{6} \\ \cline{2-8} 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \cline{2-8} 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ \cline{2-8} 2 & 1 & 1 & 1 & 1 & 0 & 1 & 1 \\ \cline{2-8} \end{array} $$ חתימת השיטה היא: ```java public static int longestPath(int mat[][], int x, int y) ``` השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות כלל. כך גם כל שיטות העזר שתכתבו (אם תכתבו) לא יכולות להכיל לולאות. אפשר להשתמש בהעמסת-יתר (overloading). מותר לשנות את המערך במהלך השיטה, אבל בסופה הוא צריך לחזור למצבו המקורי. אין צורך לדאוג ליעילות השיטה, אבל כמובן שצריך לשים לב לא לעשות קריאות רקורסיביות מיותרות! אל תשכחו לתעד את מה שכתבתם!

רמז: כדי למצוא את המסלול הארוך ביותר, יש לחקור את כל המסלולים האפשריים. חשבו על פונקציה רקורסיבית שבודקת את כל שכניה ואיך ניתן להשתמש בתוצאות המוחזרות מהם. כיצד ניתן למנוע מעגלים ולזכור אילו תאים כבר נכללו במסלול הנוכחי?

פתרון: הבעיה דורשת למצוא את המסלול הארוך ביותר במבוך המיוצג על ידי מערך דו-ממדי, מתא המקור $(0,0)$ לתא יעד $(x,y)$. זוהי בעיה קלאסית שניתן לפתור באמצעות **רקורסיה** עם **נסיגה רקורסיבית (backtracking)**. הרעיון המרכזי הוא לחקור באופן רקורסיבי את כל המסלולים החוקיים האפשריים מהמקור ליעד, ולבחור את הארוך מביניהם. כדי לממש זאת, נשתמש בשיטת עזר רקורסיבית. השיטה הציבורית `longestPath` תשמש כמעטפת שתפעיל את הרקורסיה מההתחלה. ### אסטרטגיית הפתרון: 1. **שיטת עזר רקורסיבית**: נגדיר שיטת עזר פרטית (או מועמסת) שתקבל, בנוסף למערך וליעד, גם את הקואורדינטות של התא הנוכחי במסלול. חתימתה יכולה להיות: `longestPathHelper(mat, r, c, dest_r, dest_c)`. 2. **מניעת מעגלים (מעקב)**: על פי הגדרת הבעיה, אסור לבקר באותו תא יותר מפעם אחת במסלול. כדי לאכוף זאת, בכל פעם שאנו מבקרים בתא $(r,c)$, נסמן אותו כ"תא שכבר ביקרנו בו". מכיוון שמותר לשנות את המערך, דרך נוחה לעשות זאת היא לשנות את ערך התא `mat[r][c]` מ-1 ל-0 באופן זמני. כך, בקריאות הרקורסיביות הבאות באותו מסלול, התא הזה ייחשב כ"קיר" ולא נוכל לחזור אליו. 3. **תנאי עצירה (Base Cases)**: * **כישלון**: קריאה רקורסיבית מסתיימת בכישלון אם התא הנוכחי $(r,c)$ נמצא מחוץ לגבולות המערך, או אם ערכו הוא 0 (כלומר, הוא "קיר" או תא שכבר ביקרנו בו במסלול הנוכחי). במקרים אלו, אין מסלול חוקי מכאן, והשיטה תחזיר ערך מיוחד (sentinel) המציין כישלון, למשל -1. * **הצלחה**: הקריאה הרקורסיבית מגיעה לתנאי עצירה חיובי כאשר התא הנוכחי $(r,c)$ הוא תא היעד. במקרה זה, מצאנו מסלול חוקי. אורך המסלול מתא היעד לעצמו הוא 1 (התא עצמו). לכן, השיטה תחזיר 1. 4. **הצעד הרקורסיבי**: * אם התא הנוכחי $(r,c)$ הוא תא חוקי (בגבולות המערך וערכו 1), נבצע את הצעדים הבאים: * נסמן את התא הנוכחי כמבוקר: `mat[r][c] = 0`. * נקרא רקורסיבית לשיטה עבור כל אחד מארבעת השכנים: למעלה, למטה, ימינה ושמאלה. * נשמור את אורכי המסלולים המוחזרים מכל אחת מארבע הקריאות. * **נסיגה (Backtrack)**: לאחר שכל הקריאות הרקורסיביות חזרו, **חובה לשחזר את ערך התא המקורי**: `mat[r][c] = 1`. שחזור זה מאפשר למסלולים פוטנציאליים אחרים, שאינם חלק מהמסלול הנוכחי, להשתמש בתא זה. * נחשב את `max_path_from_neighbors`, שהוא האורך המקסימלי מבין ארבעת הערכים שהוחזרו מהשכנים. אם כל השכנים החזירו -1 (כלומר, מאף אחד מהם אין מסלול ליעד), אז גם מהתא הנוכחי אין מסלול, ונחזיר -1. * אחרת, אורך המסלול הארוך ביותר מהתא הנוכחי הוא 1 (עבור התא הנוכחי) ועוד האורך המקסימלי שנמצא מהשכנים: `1 + max_path_from_neighbors`. 5. **שיטת המעטפת הציבורית**: השיטה `public static int longestPath(int mat[][], int x, int y)` תבדוק תחילה אם תא המקור $(0,0)$ חסום. אם כן, היא תחזיר 0. אחרת, היא תקרא לשיטת העזר הרקורסיבית עם נקודת ההתחלה $(0,0)$. אם שיטת העזר מחזירה -1 (לא נמצא מסלול), שיטת המעטפת תחזיר 0. אחרת, היא תחזיר את האורך שהתקבל. ### מימוש ב-Java: ```java public class PathFinder { /** * השיטה הציבורית הראשית. * משמשת כמעטפת לקריאה הרקורסיבית ומתחילה את החיפוש מתא המקור (0,0). * @param mat המטריצה הדו-ממדית עם 0 ו-1. * @param x קואורדינטת השורה של תא היעד. * @param y קואורדינטת העמודה של תא היעד. * @return אורך המסלול הארוך ביותר, או 0 אם אין מסלול כזה. */ public static int longestPath(int mat[][], int x, int y) { // אם תא המקור חסום, לא ניתן להתחיל מסלול. if (mat[0][0] == 0) { return 0; } // קריאה לשיטת העזר הרקורסיבית שמתחילה את החיפוש מהמקור (0,0). int pathLength = longestPathHelper(mat, 0, 0, x, y); // שיטת העזר מחזירה -1 אם לא נמצא מסלול. במקרה זה, האורך הוא 0. return (pathLength == -1) ? 0 : pathLength; } /** * שיטת עזר רקורסיבית המממשת את אלגוריתם הנסיגה (backtracking). * @param mat המטריצה. * @param r השורה הנוכחית. * @param c העמודה הנוכחית. * @param dest_r שורת היעד. * @param dest_c עמודת היעד. * @return אורך המסלול הארוך ביותר מהתא (r,c) ליעד, או -1 אם אין מסלול. */ private static int longestPathHelper(int[][] mat, int r, int c, int dest_r, int dest_c) { // תנאי עצירה (כישלון): יציאה מגבולות המערך. if (r < 0 || r >= mat.length || c < 0 || c >= mat[0].length) { return -1; } // תנאי עצירה (כישלון): הגעה ל"קיר" או לתא שכבר ביקרנו בו במסלול הנוכחי. if (mat[r][c] == 0) { return -1; } // תנאי עצירה (הצלחה): הגענו לתא היעד. if (r == dest_r && c == dest_c) { return 1; } // --- צעד רקורסיבי --- // סימון התא הנוכחי כ"מבוקר" על-ידי הפיכתו לקיר זמני. mat[r][c] = 0; // קריאות רקורסיביות לארבעת הכיוונים האפשריים. int pathDown = longestPathHelper(mat, r + 1, c, dest_r, dest_c); int pathUp = longestPathHelper(mat, r - 1, c, dest_r, dest_c); int pathRight = longestPathHelper(mat, r, c + 1, dest_r, dest_c); int pathLeft = longestPathHelper(mat, r, c - 1, dest_r, dest_c); // נסיגה (Backtrack): שחזור ערך התא המקורי כדי לאפשר למסלולים אחרים להשתמש בו. mat[r][c] = 1; // מציאת אורך המסלול המקסימלי מבין כל השכנים. int maxFromNeighbors = Math.max(Math.max(pathDown, pathUp), Math.max(pathRight, pathLeft)); // אם אף שכן לא מצא מסלול ליעד (כולם החזירו -1), אז אין מסלול מהתא הנוכחי. if (maxFromNeighbors == -1) { return -1; } // אורך המסלול הנוכחי הוא 1 (עבור התא הזה) + המקסימום שנמצא מהשכנים. return 1 + maxFromNeighbors; } } ```