לא מבין את הרקורסיה הזאת -

מנהלים: TA_nimrod, TA_Igor, TA_Adi

שלח תגובה
hodgav
הודעות: 44
הצטרף: 15:06 22/10/2009

לא מבין את הרקורסיה הזאת -

שליחה על ידי hodgav » 13:15 23/01/2010

קוד: בחירת הכל

public static void subsets(int n, int k) {
subsets(n, k, "");
}
public static void subsets(int n, int k, String s) {
if (k == 0)
System.out.println(s);
else if (n > 0) {
subsets(n - 1, k, s);
subsets(n - 1, k - 1, n + s);
}
}

זה אמור להדפיס את כל תת הקבוצות בגודל k של המספרים 1,2,.......n
אבל איך זה עושה זאת?
למה 2 קריאות רקרוסיביות
אוף :(

בר כהן
הודעות: 146
הצטרף: 18:24 22/10/2009

Re: לא מבין את הרקורסיה הזאת -

שליחה על ידי בר כהן » 13:29 23/01/2010

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

hodgav
הודעות: 44
הצטרף: 15:06 22/10/2009

Re: לא מבין את הרקורסיה הזאת -

שליחה על ידי hodgav » 13:34 23/01/2010

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

TA_Yoni
הודעות: 236
הצטרף: 13:44 18/10/2009

Re: לא מבין את הרקורסיה הזאת -

שליחה על ידי TA_Yoni » 13:44 23/01/2010

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

קוד: בחירת הכל

subsets(n - 1, k - 1, n + s)
והמקרה השני הוא בו לא בוחרים את האיר n לתת הקבוצה ולכן עדין יש לבחור k איברים מתוך העולם

קוד: בחירת הכל

subsets(n - 1, k, s);
נסה להבין לבד כעת את תנאי העצירה.
המתרגל יוני

hodgav
הודעות: 44
הצטרף: 15:06 22/10/2009

Re: לא מבין את הרקורסיה הזאת -

שליחה על ידי hodgav » 13:55 23/01/2010

עכשיו הכל הרבה יותר ברור.. תודה!
את תנאי העצירה אני דווקא ישר יודע לכתוב, הצעד הרקורסיבי תמיד מהווה לי אבן נגף :(

hodgav
הודעות: 44
הצטרף: 15:06 22/10/2009

Re: לא מבין את הרקורסיה הזאת -

שליחה על ידי hodgav » 17:45 24/01/2010

יאללה איזה צירוף מקרים זה היה במבחן היום חחח

shearer
הודעות: 28
הצטרף: 19:33 23/10/2009

Re: לא מבין את הרקורסיה הזאת -

שליחה על ידי shearer » 17:50 24/01/2010

איזה עולם קטן !

שלח תגובה

חזור אל “- מבוא למדעי המחשב 2010”