ex1.5 רקורסיה מתקדמת

מגדלי האנוי רקורסיבי כולל תיאור מעברים

link

עליכם לממש פונקציה רקורסיבית בשם TowerOfHanoi עם החתימה הבאה:

public static int TowerOfHanoi(int n, char from, char to, char aux)

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

Move disk 3 from A to C

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

ערך החזרה

מספר שלם המייצג את מספר הצעדים הכולל.

דגשים

כדי לזהות את המבנה הרקורסיבי של האנוי יש לבצע רדוקציה לבעיה. לאחר ניתוח המקרים של 1, 2 ו-3 טבעות ניתן להסיק את כלל הנסיגה ולרשום אותו כפונקציה רקורסיבית.

מגדלי האנוי רקורסיבי

עליכם לממש פונקציה רקורסיבית בשם TowerOfHanoi עם החתימה הבאה:

public static int TowerOfHanoi(int n)

הפונקציה תפתור את חידת מגדל האנוי הקלאסית עבור n טבעות.

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

פרמטרים n: מספר שלם המייצג את כמות הטבעות להעברה.

ערך החזרה

מספר שלם המייצג את מספר הצעדים הכולל.

דגשים

כדי לזהות את המבנה הרקורסיבי של האנוי יש לבצע רדוקציה לבעיה. לאחר ניתוח המקרים של 1, 2 ו-3 טבעות ניתן להסיק את כלל הנסיגה ולרשום אותו כפונקציה רקורסיבית.

שאלה 2: פתרון האנוי באמצעות נוסחה מפורשת (Closed-Form)

במקום פתרון רקורסיבי, מצאו את הנוסחה המפורשת למספר הצעדים הנדרש להעברת n טבעות במגדל האנוי.

הנוסחה הרקורסיבית היא זו שקיבלתם בתרגיל הקודם.

המירו אותה לנוסחה מפורשת. לשם כך תוכלו להשתמש באנציקלופדיה לסדרות OEIS כדי למצוא את הנוסחה.

הדרכה למציאת נוסחה מפורשת

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

בדיקת חוקיות סודוקו

link

עליכם לממש פונקציה רקורסיבית בשם IsValidSudoku עם החתימה הבאה:

static bool IsValidSudoku(int[,] board, int row, int col, int num)

הפונקציה תקבל את הפרמטרים הבאים:

1. board - מערך דו-ממדי מסוג int[,] המייצג את לוח הסודוקו. תאים ריקים מיוצגים על ידי 0.
2. row - מספר השורה (אינדקס) בה יש לבדוק את חוקיות המיקום עבור המספר num.
3. col - מספר העמודה (אינדקס) בה יש לבדוק את חוקיות המיקום עבור המספר num.
4. num - המספר השלם (1-9) אותו אנו רוצים למקם בתא (row, col).

הפונקציה צריכה לבדוק אם ניתן למקם את num במיקום (row, col) על לוח הסודוקו board מבלי להפר את חוקי הסודוקו:

1. המספר num אינו קיים כבר באותה שורה.
2. המספר num אינו קיים כבר באותה עמודה.
3. המספר num אינו קיים כבר באותה תת-רשת (Box) בגודל 3x3.

דגשים:

1. הפונקציה צריכה להחזיר true אם המיקום חוקי עבור המספר הנתון, ו-false אחרת.
2. שימו לב שאין צורך לשנות את הלוח בפונקציה זו, אלא רק לבצע בדיקת חוקיות.
3. אורך השורה והעמודה תמיד יהיה 9, והלוח הוא 9X9.

ספירת מסלולים במטריצה

link

עליכם לממש פונקציה רקורסיבית בשם CountPaths עם החתימה הבאה:

static int CountPaths(int[,] matrix, int row, int col)

הפונקציה מקבלת שלושה פרמטרים:

1. matrix - מטריצה דו-ממדית של מספרים שלמים.
2. row - אינדקס השורה של מיקום ההתחלה הנוכחי.
3. col - אינדקס העמודה של מיקום ההתחלה הנוכחי.

הפונקציה צריכה לספור ולהחזיר את מספר המסלולים האפשריים ממיקום ההתחלה (row, col) ועד לפינה הימנית התחתונה של המטריצה. ניתן לנוע אך ורק ימינה או מטה.

כללי תנועה:

1. ימינה: מהתא (row, col) לתא (row, col + 1).
2. מטה: מהתא (row, col) לתא (row + 1, col).

מקרים שיש לטפל בהם:

1. הגעה ליעד: אם (row, col) הוא הפינה הימנית התחתונה של המטריצה, נחשב זאת כמסלול אחד.
2. חריגה מגבולות: אם (row, col) נמצא מחוץ לגבולות המטריצה, או אם row או col גדולים או שווים לממדי המטריצה, אין מסלולים מהתא הזה (החזירו 0).

הניחו שהמטריצה אינה ריקה.

פתרון מבוך רקורסיבי

link

עליכם לממש פונקציה רקורסיבית ב-C# עם החתימה הבאה:

static bool SolveMaze(int[,] maze, int row, int col, int[,] solution)

תיאור הפונקציה:

הפונקציה מקבלת מבוך maze (מטריצה דו-ממדית של מספרים שלמים), מיקום התחלתי (row, col), ומטריצת solution שתשמש לסימון המסלול.

חוקי המבוך:

1. 1 מייצג קיר (לא ניתן לעבור דרכו).
2. 0 מייצג דרך פתוחה (ניתן לעבור דרכה).

התנהגות הפונקציה:

1. הפונקציה צריכה למצוא מסלול ממיקום ההתחלה (row, col) ועד לסוף המבוך (התא הימני-תחתון [maze.GetLength(0) - 1, maze.GetLength(1) - 1]).
2. כאשר נמצא חלק מהמסלול, סמנו את התא המתאים במטריצת solution ב-1.
3. אם הפונקציה מצליחה למצוא מסלול לסיום המבוך, עליה להחזיר true.
4. אם לא נמצא מסלול מהמיקום הנוכחי לסיום המבוך, הפונקציה צריכה להחזיר false ולבצע “חזרה לאחור” (backtracking) על ידי איפוס הסימון בתא הנוכחי במטריצת solution ל-0.

הנחות:

1. המבוך תמיד יהיה מלבני (מספר שורות ועמודות שווה).
2. מיקום ההתחלה (row, col) תמיד יהיה תא חוקי בתוך גבולות המבוך ויהיה דרך פתוחה (0).
3. מטריצת ה-solution תהיה בגודל זהה למטריצת ה-maze ומאותחלת כולה ל-0.
4. אין לטפל במקרי קצה של מבוך ריק או מבוך בגודל 1x1, אלא במבוכים בגודל סביר.

דוגמה לשימוש (לא חלק מהפתרון):

int[,] maze = {
{0, 1, 0, 0},
{0, 0, 0, 1},
{1, 0, 1, 0},
{0, 0, 0, 0}
};
int rows = maze.GetLength(0);
int cols = maze.GetLength(1);
int[,] solution = new int[rows, cols];

if (Solution.SolveMaze(maze, 0, 0, solution))
{
    Console.WriteLine("Maze solved! Path:");
    // Code to print solution matrix
}
else
{
    Console.WriteLine("No solution found.");
}