רקורסיה.

[carlos22]

רקורסיה.

איך ניתן להסתכל על הבעיה של 8 המלכות (על לוח שחמט שלא מאיימות אחת על השניה) באופן רקורסיבי ? לא הבנתי את הכיוון אפילו.

 

[ש ב ו ז]

ככה

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

 

[carlos22]

אבל

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

 

[vinney]

השאלה היא איך אתה מגדיר משימה

להגדיר משימה "שבץ בתוך ריבוע" זה לא נכון, לכן זה לא מסתדר לך.

 

[דודהלי]

הלוח הקטן יותר הוא...

הלוח הקטן יותר (הצעד הרקורסיבי) הוא זה שמתקבל מהלוח ה"גדול" ע"י הורדה של השורה והעמודה שעליהם נמצאת המלכה ו"הדבקה" של ארבעת הרבעים. שים לב שאם המלכה הוצבה בשורה I ועמודה J אז כשנצמיד את שורה I+1 לשורה I-1, התאים שיהיו הצמודים יהיו מאותה עמודה מקורית. כך שזה לא משנה שבלוח המקורי הם לא היו סמוכים....

 

[טיורינג]

הייתי מסתכל על זה ככה:

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

 

[ש ב ו ז]

בדרך שלי מובטח לו שבכל פעם

שהרקורסיה עוצרת יתקבל אחד מהפתרונות

 

[גיל14]

גם בזו של טיורינג. היות ויש פתרון.

 

[carlos22]

תודה לכולם.