שלום לכולם,

אני לא מצליח לחשוב על דרך לפתור אחת מהשאלות בעבודה האחרונה בקורס C (רקורסיות). בשאלה מקבלים לפונקציה מערך, מספר תלמידים K, ומספר כיסאות N, ואם רוצים אפשר לקלוט עוד נתונים לפי איך שרוצים. כך ש-N גדול או שווה ל-2K-1.

צריך להושיב את התלמידים כך שיהיה בינהם לפחות רווח אחד, ולהדפיס את כל האפשרויות, כך ש-0 מסמן כיסא ריק, 1 מסמן כיסא תפוס. לדוגמא, עבור K=2 N=5, נקבל:

00101

01001

01010

10001

10010

10100

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

אודה לכם במידה ותעזרו,

Anatoli.

תחשוב על זה ככה - כל פעם אתה מושיב תלמיד אחד, ובודק כמה אפשרויות נשארו לך להושיב את התלמידים הנותרים.

עבור N מקומות ו-K תלמידים, מספר האפשרויות להושיב אותם = מספר האפשרויות אם אתה מושיב את התלמיד בכסא הראשון (= הפעלת הפונקציה על K-1, N-2) ועוד מספר האפשרויות אם אתה מושיב את התלמיד בכסא השני (הפעלת הפונקציה על K-1, N-3) ועוד מספר האפשרויות אם אתה מושיב אותו בכסא השלישי, וכן הלאה. במילים אחרות:

f(N,K) = f(N-2,K-1) + f(N-3,K-1) + f(N-4,K-1) + ...

שים לב שיש כאן הרבה כפילות, ולכן הפתרון הרקורסיבי הוא פתרון מאוד לא יעיל (הרבה יותר יעיל לעבוד עם תכנון דינמי).

יואב, זה קורס מבוא ל-C. עוד לא שמענו על תכנון דינאמי

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

עריכה:

קבל ביטול. הרעיון לא צלח. עכשיו שוברים את הראש על רעיון אחר.

Anatoli.

מה הבעיה בפתרון (הרקורסיבי) שהצעתי לך?

לפרט על תכנון דינמי?

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

הכוונה היא שבמקום להתחיל מהתוצאה הסופית, תתחיל מה"התחלה" - תחשב קודם את (f(1,1 (ותשמור את התוצאה במערך), אח"כ את (f(2,1, אח"כ את (f(3,1 ואת (f(3,2 (מתוך הנתונים שכבר חישבת קודם), וכן הלאה. תעצור את החישוב כמובן כשאתה מגיע ל-(f(N,K.

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

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

Anatoli.

עבור התלמיד הראשון אתה יכול להושיב אותו במושב הראשון

f(k-1, n-2)

מכיוון שאתה חייב רווח אחד

או להושיב אותו במושב השני

f(k-1, n-3)

החיבור ביניהם זה מספר האפשרויות שלך

תנאי העצירה זה ש-k=0

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

אבל זאת האופציה שעולה לי לראש כרגע

בכל מקרה n>=2k-1 כי שמת רווח בין התלמידים

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

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

עבור 5 כסאות ו-2 תלמידים (אם הבנתי נכון אין חשיבות לזהות התלמידים, אלא רק לאם מקום תפוס או לא) הפתרון הרקורסיבי:

f(K,N)=f(2,5)=f(2,4)+f(1,3)

או במילים: כדי להושיב 2 תלמידים ב-5 מקומות, נספור את מספר האפשרויות להושיב 2 תלמידים בארבעה המקומות, השמאליים ביותר למשל, ונוסיף את כל האפשרויות להושיב 2 תלמידים כך שהתלמיד הראשון ישב במקום החמישי (הימני ביותר), המקום הרביעי "תפוס" (לא ניתן להושיב עליו, חייב להיות רווח) ולכן להושיב את שאר התלמידים (במקרה הזה 1) ב-3 המקומות הראשונים.

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

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

באופן כללי: בהינתן K תלמידים ו-N כסאות כך ש N>=2K-1 מספר האפשרויות (פתרון הרקורסיה) להושיב את K התלמידים כך שבין כל שניים יהיה לפחות רווח אחד, בN מקומות הוא:

f(K,N)=f(K,N-1)+f(K-1,N-2)

כאשר בסיס הרקורסיה (תנאי עצירה):

f(1,K)=K

f(K,K)=0

ובמקרה החופף:

f(1,1)=1

אדגים את הפתרון הכללי על הדוגמה עם 5 מקומות ו-2 תלמידים:

f(2,5)=f(2,4)+f(1,3)={[f(2,3)]+f(1,2)}+f(1,3)=[f(2,2)+f(1,1)]+f(1,2)+f(1,3)=0+1+2+3=6

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

ובמקרה שעדיין לא ברור, תשאל.

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

תודה לכולם על העזרה.

Anatoli.

עשית עם ה-swap?

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

פתרון פשוט ויפה..

אם אתה רוצה אני אעלה לך את זה.

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

Anatoli.