פורטל:מתמטיקה/מאמר נבחר/8

משחק מגדלי האנוי עשוי עץ לבוד

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

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

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

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

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

לערך המלא