עבור לתוכן

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

Featured Replies

פורסם

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

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

יש הצעות?

פורסם

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

פורסם

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

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

הסיכוי -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

פורסם
  • מחבר

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

פורסם

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

:P

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

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)

פורסם
  • מחבר

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

1-argument

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

פורסם

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

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

b3b83073434fc6df220de80069a2cb12.png

פורסם

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

בכל מקרה:

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

1-argument

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

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

פורסם
  • מחבר

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

פורסם

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

  • 2 שבועות מאוחר יותר...
פורסם

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

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

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) ואז הקומפיילר ידע שאתה מתכוון למספרים ממשיים.

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

פורסם

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

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

הצלת אותי

ארכיון

דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.

דיונים חדשים