פורטל:מדעי המחשב/מאמר נבחר/2

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש
משחק מגדלי האנוי עשוי עץ לבוד
משחק מגדלי האנוי עשוי עץ לבוד

מגדלי האנויאנגלית: Towers of Hanoi) הוא משחק חידה מתמטי, שמקורו בסוף המאה ה-19. המשחק הוא אמצעי הדגמה פופולרי לעקרון הרקורסיה ולמושגים בסיסיים אחרים בקומבינטוריקה ובמדעי המחשב.

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

מטרת המשחק היא להעביר את כל הדיסקיות למוט אחר, תחת שני החוקים הללו:

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

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

לערך המלא