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

פתרון שמצאתי כשרק התחלתי ללמוד פייתון - מי נותן פתרון רקורסיבי ?

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]

כל רשימה מייצגת עמוד, וכל מספר מייצג טבעת בגודל שונה, המספר הגדול ביותר הוא כמובן הטבעת הגדולה ביותר. בסוף התהליך התוכנית גם סופרת כמה מהלכים בוצעו. תעתיקו ותריצו ותגלו כמה זמן היה לוקח לכם לפתור את החידה.