חידה ותיקה שבה צריך להעביר את כל הטבעות הנמצאות על עמוד אחד, לעמוד שלישי, כאשר הכלל היחידי הוא שאסור להניח טבעת גדולה על גבי טבעת קטנה, אלא רק קטנה על גדולה.
למשל בציור שלמעלה צריך להעביר את כל הטבעות מעמוד A לעמוד C. מספר הטבעות יכול להיות N ככל שהוא גדול יותר זה לוקח יותר זמן לפתור את החידה (תנסו לפתור אותה עם 8 טבעות) או לכל N טבעות. אנו רוצים לראות מודל של החידה המיוצג בפייתון, ואת השלבים והדרך המובילים לפתרון החידה. אפשר להיעזר בפתרונות לחידות אחרות שהתפרסמו בפורום הזה. בהצלחה. בין הפותרים נכונה לא יוגרל שום דבר. כולם יזכו להערכה ולהערות בונות אם יש. לא לפחד להירשם לפורום, אנחנו לא שולחים ספאם, גם לא ברכות ליום הולדת, אנחנו בכלל לא מעוניינים לדעת מתי יום ההולדת שלכם, אם הוא מתרחש היום אז מזל טוב.
פתרון רקורסיבי המכיל שלושה שלבים ושתי רקורסיות, הרעיון הוא לחלק את הבעיה לסדרה של בעיות קטנות יותר, אם למשל יש לי 3 טבעות להזיז לעמוד הימני ביותר, אני יודע שאני צריך להזין את שתי הטבעות העליונות לעמוד האמצעי, וכך אני אוכל להזיז את הטבעות האחרונה ליעד שלה, לאחר השלב הזה אני נותר עם מספר טבעות קטן באחד אבל על עמוד אחר (העמוד האמצעי ולא העמוד השמאלי) כך שהעמוד השמאלי הוא הופך להיות עמוד הביניים בדרך ליעד לכן לאחר השלב השני של הזזת הטבעת הבודדות (שזה המהלך היחיד אותו אנו רוצים להדפיס) אנו מפעילים שוב את הפונקציה המקורית רק שהפעם מהעמוד שהיה במקור עמוד הביניים ליעד:
def tower(n,s,i,d):#n=מספר הטבעות s=מקור הטבעות i=עמוד מקשר d=היעד של הטבעות if n==0: pass else: tower(n-1,s,d,i) print(s,d) tower(n-1,i,s,d) tower(5,"a","b","c") #for 5 rings
>>>
b c #- c-ל b-הטבעת הראשונה עוברת מ
a c
b a
c b
c a
b a
b c
a c
a b
c b
a c
b a
b c
a c