שאלה בC

[asi123456789]

שאלה בC

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

 

[Maha Vailo]

עזרה

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

 

[asi123456789]

תודה על התגובה אחי

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

 

[Maha Vailo]

אל תנסה להזיז אחדות

אם הכוונה שלך היא למצוא פתרון אחד ואז להזיז אחדות מפתרון אחד לשני, אז אמנם אפשר לפתור ככה, אבל זה בכלל לא נח לחשוב על זה ככה. הנה סתם דוגמא להרצה עם הושבה של שני תלמידים בחמש מקומות. 0 אומר שאין תלמיד, 1 יש תלמיד ו * שעוד לא החלטנו. אז מתחילים עם ***** ועכשיו מחליטים מה עושים עם הכסא הראשון - יש שתי אפשרויות z 10*** 0**** z נניח שברקורסיה, קודם מתייחסים למקרה בו מושיבים מישהו בכסא, אז באיטרציה הבאה נקרא ל z 1010* 100** z עכשיו כבר יש תלמידים שיושבים במקרה השמאלי, אז פשוט הופכים את שאר הכוכביות לאפסים ומקבלים פתרון 10100. סיימנו עם החלק השמאלי, אז עוברים לימני. שוב יש שתי אפשרויות z 10010 1000* z המקרה השמאלי זה שוב פתרון ולכן עוברים למקרה הימני ושוב יש שתי אפשרויות 10001 10000 המקרה עם השתי אחדות זה פתרון, ואילו המקרה השני הוא לא פתרון ושוב חוזרים אחורה הפעם עד ל z 0**** z שים לב שזה כיסה את כל האפשרויות בהן מושיבים מישהו בכסא הראשון. וככה ממשיכים הלאה מושיבים מישהו בכסא השני וכו'. נסה לשרטט את העץ של הרקורסיה הזאת כדי שיהיה לך יותר קל לראות איך היא עובדת.

 

[asi123456789]

חייב להיות סדר לפתרון

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

 

[HaifaMan]

הרעיון שלי הוא כזה:

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

 

[HaifaMan]

אופטימיזציה קלה

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

 

[asi123456789]

סבבה, הבנתי, תודה רבה.

 

[asi123456789]

סבבה, הבנתי, תודה רבה.