דף 1 מתוך 1

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

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

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

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 קריאות רקרוסיביות
אוף :(

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

נשלח: 13:29 23/01/2010
על ידי בר כהן
האמת, הדרך הכי פשוטה לראות ולהבין למה, זה לקחת דף ולהתחיל להריץ את זה לבד
תראה כל פעם מה כל שורה עושה...

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

נשלח: 13:34 23/01/2010
על ידי hodgav
לעשות מעקב זה לא באמת להבין, זה לראות שזה עובד. מה גם שמעקב אחרי רקורסיה עם 2 קריאות הוא על סף הבלתי אפשרי.

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

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

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

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

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

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

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

נשלח: 13:55 23/01/2010
על ידי hodgav
עכשיו הכל הרבה יותר ברור.. תודה!
את תנאי העצירה אני דווקא ישר יודע לכתוב, הצעד הרקורסיבי תמיד מהווה לי אבן נגף :(

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

נשלח: 17:45 24/01/2010
על ידי hodgav
יאללה איזה צירוף מקרים זה היה במבחן היום חחח

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

נשלח: 17:50 24/01/2010
על ידי shearer
איזה עולם קטן !