פיתרון מגדלי האנוי באמצעות רקורסיה

Hanoi Towers Recursive Function
בעיית מגדלי האנוי היא אחד התרגילים המפורסמים ביותר לפיתרון באמצעות פונקציה רקורסיבית. באותה מידה, מדובר גם באחד התרגילים המתסכלים ביותר.

Share This Post

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

מהי בעיית מגדלי האנוי?

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

Hanoi Towers Recursive Function

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

המאפיינים של בעיות תכנותיות שפותרים באופן רקורסיבי

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

הפיתרון לבעיית מגדלי האנוי באופן רקורסיבי

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

הפיתרון לבעייה מדרגה n תוך שימוש בפיתרון לבעיה מדרגה n-1

כיוון ששלוש העמודים מוספרו במספרים 2,1 ו-3, וכיוון שסכום המספרים הוא 6, ניתן לסכם ולומר שכאשר יש צורך להעביר דיסקית (או דיסקיות) מעמוד שמספרו x לעמוד שמספרו y, המספר של העמוד הנותר הוא התוצאה של החסרת x ו-y מ-6. כעת ניתן לנסח את הפיתרון לבעייה מדרגה n באופן הבא:

moving n-1 disks from x to 6-x-y
move 1 disk from x to y
moving n-1 disks from 6-x-y to y

בפונקציה הרקורסיבית שניצור אנחנו נעשה שימוש בפיתרון זה תוך קריאה להפעלת אותה פונקציה בכל אחד משלושת השלבים. הפונקציה תיבנה בצורה כזו כך שמייד עם הפעלת ייבדק האם n שווה ל-1, כיוון שבמקרה ש-n שווה ל-1 אז הפיתרון מאד פשוט (אין צורך להשתמש בפיתרון לבעיה מדרגה n כפי שניסחנו). בווידאו שבקישור https://youtu.be/zfE81wCbNCo?si=y4jzh8BJc4Vt_gUe ניתן למצוא הסבר מפורט תוך שימוש בשפת התכנות #C

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

הירשמו לניוזלטר שלנו

התעדכנו בחידושים הטכנולוגים

פוסטים נוספים

Karate and Software Development
מאפייני ההדרכה

הקשר שבין קראטה ופיתוח תוכנה

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

הזנק את העסק שלך!

נשמח להיפגש לקפה!

life michael academy asynchronous online courses

Java | Python | JavaScript | TypeScript

Update cookies preferences