בעייה ברקורסיה

[Gil28]

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

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

יש הצעות?

[tzolerguy]

אם תכתוב נוסחה אולי יהיה יותר קל לעזור לך לעשות את זה

[Gil28]

(364/365)^((n*(n-1))/2)

או יותר פשוט, http://en.wikipedia.org/wiki/Birthday_problem

[עוד אחד]

בצורה רקורסיבית-

הסתברותית קל יותר לחשב את הסיכוי שאין יום הולדת משותף.

הסיכוי -1 = הסיכוי שלפחות 2 אנשים חולקים יום הולדת.

את הסיכוי הנ"ל קל לחשב.

p(n)=((365+1-n)/365)*p(n-1)

שים לב ש-

p(0)=1

p(>365)=0

פתרון ברקורסיה = לחפש נוסחת נסיגה.

לא פתרון מקורב.

(364/365)^((n*(n-1))/2)

או יותר פשוט, http://en.wikipedia.org/wiki/Birthday_problem

[Gil28]

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

[שניצל]

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

בעיקרון, ניתן להפוך כל לולאה לרקורסיה בלי הרבה מחשבה, כך שהלולאה:

for (int i = 0 ; i < n ; i++) {
 // do something here
}

הופכת לפונקציה כזו:

int f(int i, /* more parameters here */) {
 if (i < n) {
  // do something with i
  return f(i+1, /* other params */);
 }
 else
  return 0;
}

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

[עוד אחד]

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

אם אתה לא יודע לזהות נוסחת נסיגה כשאתה רואה אחת, איך לעזאזל אתה מחפש אותה ?

p(0)=1

p(>365)=0

p(n)=((365+1-n)/365)*p(n-1)

[Gil28]

הבעייה שלי היא להכניס את ה-

1-argument

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

[ירח אפל]

לא הבנתי מה קשה להפוך?

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

[שניצל]

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

בכל מקרה:

הבעייה שלי היא להכניס את ה-

1-argument

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

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

[Gil28]

אז אתה אומר שאני צריך ליצור פונקציה, נוספת, שתחשב את הסיכוי שלאף שניים לא יהיה יום הולדת, להשים את הערך במשתנה זמני ואז להחזיר "מה שיצא"-1

[שניצל]

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

[AskingAlexandria]

מה לעזאזל לא בסדר בקוד הזה שעשיתי?????

נראה לי שאני משתמש לא טוב בטיפוס דאבל...

public static double chanceForSameBirthday(int numOfPeople){

double opposite=chanceNotForSameBirthday(numOfPeople);

return (1-opposite);

}

public static double chanceNotForSameBirthday(int num){

if (num==0){

return (double)(1);

}

System.out.println("the num is: "+num);;

double temp = ((365+1-num)/365);

System.out.println(temp);

double chance = chanceNotForSameBirthday(num-1) * (temp);

System.out.println("the chance for: "+num +" is " +chance);

return chance;

}

public st

[שניצל]

אכן, זו הטעות שלך. כשאתה עושה את החישוב הזה:

(365+1-num)/365

אז כל המספרים שלך הם שלמים, ולכן גם התוצאה היא מספר שלם (כלומר 0).

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

נ.ב. אל תצמיד לשמאל את הקוד, אלא תשתמש בטג קוד (הכפתור שליד טג ציטוט).

[AskingAlexandria]

מאה אחוז, עובד.

תודה רבה, לא הכרתי את העניין הזה עם הנקודה.

הצלת אותי