חידה ותיקה שבה צריך להעביר את כל הטבעות הנמצאות על עמוד אחד, לעמוד שלישי, כאשר הכלל היחידי הוא שאסור להניח טבעת גדולה על גבי טבעת קטנה, אלא רק קטנה על גדולה.
למשל בציור שלמעלה צריך להעביר את כל הטבעות מעמוד 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]
כל רשימה מייצגת עמוד, וכל מספר מייצג טבעת בגודל שונה, המספר הגדול ביותר הוא כמובן הטבעת הגדולה ביותר. בסוף התהליך התוכנית גם סופרת כמה מהלכים בוצעו. תעתיקו ותריצו ותגלו כמה זמן היה לוקח לכם לפתור את החידה.