מהי בעיית מגדלי האנוי?
מגדלי האנוי הם שם של חידה מפורסמת שהומצאה על ידי המתמטיקאי הצרפתי אדוארד לוקאס בשנת 1883. ב"מגדלי הנוי" נתון מגדל עם דיסקיות שהיקפן הולך ונעשה קטן ככל שהן עליונות (הרחבות למטה). מטרת החידה היא להעביר את כל המגדל בשלמותו לאחד משני העמודים הריקים שלידו. כמובן שיש להעביר את הדיסקיות במה שפחות צעדים וכמה שיותר מהר.
החידה משמשת ללימוד מתמטיקה ומדעי המחשב ולהמחשת מושגים כמו רקורסיה (ראו באאוריקה בתגית רקורסיה). עוד פרט מעניין - אם נסמן בנקודה כל מצב חוקי במשחק מגדלי האנוי, ונקשר בקווים את המצבים שבהם אפשר לעבור מאחד לשני, נקבל למול עינינו את גרף המשחק, בצורה של הפרקטל המוכר כ"משולש שרפינסקי".
אגב, לוקאס המציא גם אגדה שמדובר במקדש בראהמי שבו הכהנים מעבירים מגדל בן 64 דיסקיות. על פי האגדה שלו, כשיסיימו הכהנים את עבודתם, יגיע גם סוף העולם..
ישנם כללים להעברה:
א. בכל שלב תעבור רק דיסקית אחת מקום.
ב. אסור שיהיה מצב שדיסקית תהיה מונחת על דיסקית קטנה יותר.
מגדלי האנוי הם שם של חידה מפורסמת שהומצאה על ידי המתמטיקאי הצרפתי אדוארד לוקאס בשנת 1883. ב"מגדלי הנוי" נתון מגדל עם דיסקיות שהיקפן הולך ונעשה קטן ככל שהן עליונות (הרחבות למטה). מטרת החידה היא להעביר את כל המגדל בשלמותו לאחד משני העמודים הריקים שלידו. כמובן שיש להעביר את הדיסקיות במה שפחות צעדים וכמה שיותר מהר.
החידה משמשת ללימוד מתמטיקה ומדעי המחשב ולהמחשת מושגים כמו רקורסיה (ראו באאוריקה בתגית רקורסיה). עוד פרט מעניין - אם נסמן בנקודה כל מצב חוקי במשחק מגדלי האנוי, ונקשר בקווים את המצבים שבהם אפשר לעבור מאחד לשני, נקבל למול עינינו את גרף המשחק, בצורה של הפרקטל המוכר כ"משולש שרפינסקי".
אגב, לוקאס המציא גם אגדה שמדובר במקדש בראהמי שבו הכהנים מעבירים מגדל בן 64 דיסקיות. על פי האגדה שלו, כשיסיימו הכהנים את עבודתם, יגיע גם סוף העולם..
ישנם כללים להעברה:
א. בכל שלב תעבור רק דיסקית אחת מקום.
ב. אסור שיהיה מצב שדיסקית תהיה מונחת על דיסקית קטנה יותר.
