pythonIsrael.com

Untitled
  • הרצת פייתון אונליין

  • צור קשר

  • פורום פרויקטים וחידות

  • הצב - בלוקים של פייתון

  • סרטוני הדרכה

  • קורס פייתון בחינם

  • חיפוש

  • בית

  • More

    Use tab to navigate through the menu items.
    To see this working, head to your live site.
    • All Posts
    • My Posts
    eddiearb
    Apr 28, 2019
      ·  Edited: Apr 28, 2019

    מגדל האנוי - חידת פייתון

    in General Discussions

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


    למשל בציור שלמעלה צריך להעביר את כל הטבעות מעמוד A לעמוד C. מספר הטבעות יכול להיות N ככל שהוא גדול יותר זה לוקח יותר זמן לפתור את החידה (תנסו לפתור אותה עם 8 טבעות) או לכל N טבעות. אנו רוצים לראות מודל של החידה המיוצג בפייתון, ואת השלבים והדרך המובילים לפתרון החידה. אפשר להיעזר בפתרונות לחידות אחרות שהתפרסמו בפורום הזה. בהצלחה. בין הפותרים נכונה לא יוגרל שום דבר. כולם יזכו להערכה ולהערות בונות אם יש. לא לפחד להירשם לפורום, אנחנו לא שולחים ספאם, גם לא ברכות ליום הולדת, אנחנו בכלל לא מעוניינים לדעת מתי יום ההולדת שלכם, אם הוא מתרחש היום אז מזל טוב.

    3 comments
    eddiearb
    Apr 28, 2019

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

    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]


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

    0
    eddiearb
    May 06, 2019  ·  Edited: May 07, 2019

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

    eddiearb
    May 07, 2019

    חקירה של מספר המהלכים הדרוש מעלה שמספר המהלכים הדרוש הוא הוא 2X+1 ממספר המהלכים (X) הדרוש למספר טבעות בשלב הקודם הקטן יותר ב- 1. כלומר - עבור מגדל עם 3 טבעות דרושים 7 מהלכים, ל- 4 טבעות דרושים 15 מהלכים, ל-5 טבעות דרושים 31 מהלכים וכו'. בסיפור המקורי של המנזר בהאנוי דובר על 64 טבעות. שצריך להזיז לפי הכללים לעמוד שלישי דרך עמוד שני. מספר המהלכים הדרוש: 18,446,744,073,709,551,615 אם מזיזים טבעת אחת בכל שנייה, ידרשו לנזיר - בערך 584 מיליארד שנה.

    0
    3 comments