חידה ותיקה שבה צריך להעביר את כל הטבעות הנמצאות על עמוד אחד, לעמוד שלישי, כאשר הכלל היחידי הוא שאסור להניח טבעת גדולה על גבי טבעת קטנה, אלא רק קטנה על גדולה.
למשל בציור שלמעלה צריך להעביר את כל הטבעות מעמוד A לעמוד C. מספר הטבעות יכול להיות N ככל שהוא גדול יותר זה לוקח יותר זמן לפתור את החידה (תנסו לפתור אותה עם 8 טבעות) או לכל N טבעות. אנו רוצים לראות מודל של החידה המיוצג בפייתון, ואת השלבים והדרך המובילים לפתרון החידה. אפשר להיעזר בפתרונות לחידות אחרות שהתפרסמו בפורום הזה. בהצלחה. בין הפותרים נכונה לא יוגרל שום דבר. כולם יזכו להערכה ולהערות בונות אם יש. לא לפחד להירשם לפורום, אנחנו לא שולחים ספאם, גם לא ברכות ליום הולדת, אנחנו בכלל לא מעוניינים לדעת מתי יום ההולדת שלכם, אם הוא מתרחש היום אז מזל טוב.
פתרון שמצאתי כשרק התחלתי ללמוד פייתון - מי נותן פתרון רקורסיבי ?
r=[i for i in range(1,9)]#n discs on the first stick need to be moved to the third one (range(1,9)=8 discs a=r[::-1] b=[] c=[] l=a[0] pop=0 count=0 last_move=('a','b') def move(a,b): global pop,last_move, my_dict pop=a.pop() b.append(pop) last_move=(a,b) def posible_moves (): global last_move ,a,b,c if b==[] and c==[]: return (a,b) if l%2==0: if a==[] and c==[]: return (b,a) if last_move==(a,b): if c==[]: return (b,c) if c[-1]>b[-1]: return (b, c) if c[-1]<b[-1]: return (c,b) if last_move==(b,a): if c==[]: return (b,c) if b==[]: return (c,b) if c[-1]>b[-1]: return (b,c) if c[-1] < b[-1]: return (c,b) if last_move==(b,c): if b==[]: return (a,b) if a==[]: return (b,a) if b[-1]>a[-1]: return (a,b) if b[-1] < a[-1]: return (b,a) if last_move == (c, b): if a == []: return (b, a) if b[-1] > a[-1]: return (a, b) if b[-1] < a[-1]: return (b, a) while len (c)<l: pm1= posible_moves()[0] pm2=posible_moves()[1] move(pm1,pm2) count+=1 print('',a,'\n',b,'\n',c,'\n',count,' moves')
הפתרון ארוך והוא מתחיל כך:
[8,7,6,5,4,3,2,1]
[ ]
[ ]
ומסתיים כך:
[ ]
[ ]
[8,7,6,5,4,3,2,1]
כל רשימה מייצגת עמוד, וכל מספר מייצג טבעת בגודל שונה, המספר הגדול ביותר הוא כמובן הטבעת הגדולה ביותר. בסוף התהליך התוכנית גם סופרת כמה מהלכים בוצעו. תעתיקו ותריצו ותגלו כמה זמן היה לוקח לכם לפתור את החידה.
פתרון רקורסיבי המכיל שלושה שלבים ושתי רקורסיות, הרעיון הוא לחלק את הבעיה לסדרה של בעיות קטנות יותר, אם למשל יש לי 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
חקירה של מספר המהלכים הדרוש מעלה שמספר המהלכים הדרוש הוא הוא 2X+1 ממספר המהלכים (X) הדרוש למספר טבעות בשלב הקודם הקטן יותר ב- 1. כלומר - עבור מגדל עם 3 טבעות דרושים 7 מהלכים, ל- 4 טבעות דרושים 15 מהלכים, ל-5 טבעות דרושים 31 מהלכים וכו'. בסיפור המקורי של המנזר בהאנוי דובר על 64 טבעות. שצריך להזיז לפי הכללים לעמוד שלישי דרך עמוד שני. מספר המהלכים הדרוש: 18,446,744,073,709,551,615 אם מזיזים טבעת אחת בכל שנייה, ידרשו לנזיר - בערך 584 מיליארד שנה.