מגדלי הנוי
Your browser doesn't support Java applets, go to http://javatester.org/configuring.html
הוראות המשחק

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

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

יהי Tn מספר הצעדים הדרושים לפתרון הבעיה עבור N דסקיות. קל לראות כי T1=1 וכי T2=3 וכן מהשלבים לעיל ניתן להסיק כי: Tn=Tn-1+1+Tn-1=2Tn-1+1 אם נציב n=3 נקבל T3=2T2+1=7 וכן הלאה...
בוב קירקלנד, Bob Kirkland  ©