מגדלי הנוי

[אופסשםמשתמש]

מגדלי הנוי

אני מניח שיש פה הרבה שמכירים את השאלה של מגדלי הנויי יש 3 עמודים על עמוד אחד יש טבעות שמסודרות מהגדול לקטן (מלמטה למעלה) צריך להעביר אותם מעמוד אחד לעמוד אחר בעזרת עמוד עזר יש 2 חוקים : מותר להעביר טבעת אחת בכל פעם ! לעולם לא יכול להיות מצב שבו טבעת גדולה שוכבת על טבעת קטנה ! איך פותרים את זה, הפתרון הוא ברקורסיה, לא אכפת לי מהקוד. אני רק רוצה להבין את האלגוריתם

 

[andav]

אולי

פה?

 

[andav]

ויש גם

כאן

 

[liran lev]

פתרון רקורסיבי...

כעיקרון הגדרת פונקציה כאשר: A עמוד מוצא B עמוד עזר C עמוד יעד בקריאה שניה לפונקציה מתחלפים התפקידים כאשר: B - עמוד מוצא A - עמוד עזר C - עמוד יעד הרעיון מאחורי הפונקציה היא הנחה שהפונקציה יודעת להעביר את n-1 הטבעות העליונות ואז נותרת העברה של הטבעת האחרונה לעמוד ריק. אין לי את כל הפונקציה אבל להלן הרעיון של הקריאות:

פונקציה: void hanoy(int n,char source,char aux,char destination) שתי קריאות לפונקציה: hanoy(n-1,A,C,B) hanoy(n-1,B,A,C)​

בהצלחה!

 

[אופסשםמשתמש]

OK

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

 

[gmorphus]

אני אנסה

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

hanoi(1,'A','B','C');​

היא אמורה להדפיס משהו כמו: move ring from A to C ולהסתיים. מה קורה כשיש שתי טבעות? אנחנו רוצים לצמצם את הבעיה. נעביר את הטבעת העליונה לB ואז את שאר הטבעות לC ושוב את העליונה מB לC. איך אנחנו מתרגמים את זה לרקורסיה? אמרנו שאנחנו יודעים לפתור את הבעיה עבור טבעת אחת. זאת אומרת שכשיש לנו שתי טבעות אנחנו מטפלים בכל אחת מהבעיות הקטנות יותר בנפרד. רקורסיה זה לא פתרון קסם. היא עושה משהו בכל שלב של הרקרוסיה ובכל מצמצמת את הבעיה עד שמגיעים למקרה שאותו אנחנו יודעים לפתור. במקרה שלנו, הרקורסיה מנסה להעביר את כל הטבעות, חוץ מהתחתונה, לעמוד העזר כדי שהתחתונה תתפנה ונוכל להעביר אותה לעמוד היעד. זוהי לוגיקה! בכל העברה כזאת של טבעות הרקורסיה חייבת לידע את המשתמש על ההעברות שהיא עושה. למה ההעברות חוקיות אתה שואל? כי אם אני לוקח את n-1 הטבעות הקטנות ו"משחק" איתן, אפילו אם הטבעת הגדולה מסתובבת לה איפשהו על אחד העמודים היא לא תפריע לחוקי המשחק, כי הכי גדולה. כך בכל שלב של הרקורסיה אני "מרשה" לעצמי לשחק עם טבעות שקטנות יותר מהטבעת ה n.