הבלוג של גרי רשף

15/07/2010

מגדלי האנוי

Filed under: Uncategorized — תגיות: , , , , — גרי רשף @ 10:09

אתגר מגדלי האנוי שמוכר לכל מי שעסק ברקורסיה במסגרת מבוא למדעי המחשב: משחק שהומצא במערב וניתן לו שם בעל נופך מזרח אסיאתי מסתורי ולצידו אגדה על נזירים המחשבים את קיצו של העולם לאחור בעוד 64^2 שניות..
באופן מעורר חשד זה מזכיר אגדה אחרת – מופרכת לא פחות – על האיש שהמציא את משחק השחמט וביקש תמורת המצאתו גרגר חיטה כנגד המשבצת הראשונה, 2 גרגרים כנגד השניה, 4 כנגד השלישית וכך הלאה – טור הנדסי של מכפלות של 2, ובמקרה זה מספר גרגרי החיטה הוא 64^2 שזה הרבה מעבר למה שיש + מה שהיה + מה שיהיה..

ולענייננו- נתחיל עם הקוד (למי שאין כח להסברים ורוצה לראות איך זה נראה) של העברת 3=I@ דיסקיות ממוט A למוט B בעזרת מוט C:

Declare    @I Int

Set    @I=3;

With Nmbr As

(select 1 As Mispar

Union All

Select Mispar+1

From Nmbr

Where Mispar<@I),

Hanoi    As

(Select    N1.Mispar Diskit,

        @I Shalav,

        Case When N2.Mispar=1 Then 'A'

            When N2.Mispar=2 Then 'C'

            End Makor,

        Case When N1.Mispar=@I Then 'B'

            When N2.Mispar=1 Then 'C'

            When N2.Mispar=2 Then 'B'

            End Yaad,

        Case When N1.Mispar=@I Then 1 Else 0 End Amiti,

        Power(2,@I-1)+Case When N1.Mispar=@I Then 0

            When N2.Mispar=1 Then (-Power(2,@I-2))

            When N2.Mispar=2 Then Power(2,@I-2)

            End Seder

From    Nmbr N1

Inner Join Nmbr N2

        On N2.Mispar In (1,2)

        And N1.Mispar<=@I

        And (N2.Mispar=1 Or N1.Mispar<>@I)

Union All

Select    N1.Diskit,

        (Shalav-1) Shalav,

        Case When N2.Mispar=1 Then Makor

            When N2.Mispar=2 Then Cast(Replace(Replace('ABC',Makor,''),Yaad,'') As VarChar(1))

            End Makor,

        Case When N1.Diskit=Shalav-1 Then Yaad

            When N2.Mispar=1 Then Cast(Replace(Replace('ABC',Makor,''),Yaad,'') As VarChar(1))

            When N2.Mispar=2 Then Yaad

            End Yaad,

        Case When N1.Diskit=Shalav-1 Then 1 Else 0 End Amiti,

        Seder+Case When N1.Diskit=Shalav-1 Then 0

            When N2.Mispar=1 Then (-Power(2,(Shalav-3)))

            When N2.Mispar=2 Then Power(2,Shalav-3)

            End Seder

From    Hanoi N1

Inner Join Nmbr N2

        On N2.Mispar In (1,2)

        And N1.Diskit<=Shalav-1

        And (N2.Mispar=1 Or N1.Diskit<>Shalav-1)

Where    N1.Diskit<=Shalav-1)

Select    Diskit,

        Makor,

        Yaad

From    Hanoi

Where    Amiti=1

Order By Seder,

        Diskit

option (MaxRecursion 0);

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

אפשר לשנות בשורה השנייה את ערכו של I@ מ-3 לכל מספר אחר.

שיטת הפתרון – למי שלא זוכר – היא כך: מעבירים את כל הדסקיות חוץ מהתחתונה (N-1 דיסקיות) מ-A ל-C, מעבירים את התחתונה מ-A ל-B, ומעבירים את N-1 הנ"ל מ-C ל-B. כמובן, שכדי להעביר N-1 דיסקיות מ-A ל-C ומ-C ל-B יש באופן רקורסיבי להעביר את אלו שלמעלה, לאחר מכן את זו שלמטה וכך הלאה.

הפתרון שלי עובד בדרך זו, ולכן צריך להבחין בין העברות "אמיתיות" (העברת הדיסקית התחתונה) להעברות לא "אמיתיות" שעליהן יש להפעיל רקורסיה, ולשם כך העמודה Amiti; כאשר Amiti=1 עבור הדיסקית ה-N מתוך N דיסקיות ועבור כל השאר Amiti=0.

בתחילת השליפה מופיעה Nmbr- זו שמחוללת את רצף המספרים מ-1 ועד I@.

מספור הצעדים לצורך הצגתם הממויינת: העברת N דיסקיות נעשית בעזרת 2N-1 צעדים, למשל- עבור 3=N זה 7=8-1. קל להוכיח את זה באינדוקציה: עבור N=1 זה נכון (צעד אחד להעברת הדיסקית מ-A ל-B), ואם זה נכון עבור N זה נכון גם עבור 1+N מכיוון שאז נזדקק ל- 2N-1 עבור N הדיסקיות העליונות, 1 עבור התחתונה, ו- 2N-1 שוב עבור העליונות; וביחד זה 2N+1-1 צעדים.

לא חייבים להבין לעומק את כל המתימטיקה הזו, וזה רק נועד להסביר מה עומד מאחורי החישוב של Seder: כשמעבירים N דיסקיות, העברת הדיסקית ה-N שהיא האמיתית תתרחש בצעד ה- 2N-1-1, והצעדים הלא "אמיתיים" יהיו באופן סימטרי לפני ואחרי.

כל מה שנותר לסקרנים זה לשנות את ערכו של I@ ל-64, להפעיל, וכשזה מסיים לרוץ – סימן שסוף העולם הגיע, או אולי משאבי המחשב נוצלו עד תום ויש לבצע ריסטארט כי הוא נתקע..

מודעות פרסומת

להגיב »

עדיין אין תגובות.

RSS feed for comments on this post. TrackBack URI

כתיבת תגובה

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

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s

בלוג בוורדפרס.קום.

%d בלוגרים אהבו את זה: