בתשובה לעומר, 05/06/24 13:40
על מה יש להצטער 769265
אח של אייל • בתשובה לעומר יום ד', 5/6/2024, 15:03
אם ההסתברויות הן: 0.1, 0.29 ,0.3, 0.31
אז איך האלגוריתם הראשון עובד?
על מה יש להצטער 769269
עומר • בתשובה לאח של אייל יום ד', 5/6/2024, 16:12
ההגרלה תעבוד כך: בחר אינדקס אקראי בין 0 ל-‏1.
* אם קיבלת 0: בהסתברות 0.4 החזר 0, ואחרת החזר 3.
* אם קיבלת 1: תמיד החזר 1.
* אם קיבלת 2: בהסתברות 0.84 החזר 2, אחרת החזר 1.
* אם קיבלת 3: בהתסברות 0.64 החזר 3, אחרת החזר 2.

נבדוק:
* ההסתברות לקבל 0: 0.4*0.25 = 0.1.
* ההסתברות לקבל 1: (1-0.84)*0.25+0.25 = 0.29
* ההסתברות לקבל 2: 0.84*0.25 + (1-0.64)*0.25 = 0.3
* ההסתברות לקבל 3: 0.64*0.25 + (1-0.4)*0.25 = 0.31

אם אתה רוצה לדעת איך קיבלתי את ההסתברויות והבחירות האלטרנטיביות האלה בסיבוכיות של o(n), ראה כאן.
על מה יש להצטער 769270
עומר • בתשובה לעומר יום ד', 5/6/2024, 16:14
(את האינדקס בחר, כמובן, בין 0 ל-‏3 - כולל).
על מה יש להצטער 769271
יובל נוב • בתשובה לעומר יום ד', 5/6/2024, 17:32
(אני מבין שהראש שלך עובד בפייתון / C, ולא ב-R / מטלאב.)

ותודה על האלגוריתם, לא הכרתי.
על מה יש להצטער 769272
אח של אייל • בתשובה לעומר יום ד', 5/6/2024, 17:45
תודה על ההסבר.

בתגובה המקורית דובר על כך שאיברים שקיבלו "יותר מדי" (למשל האיבר הראשון שקיבל 25 במקום 10) צריכים לתרום חלק למישהו אחר.

עכשיו אני רואה שלפעמים איברים שקיבלו "מעט מדי" (כמו האיבר השלישי שקיבל 25 במקום 30) צריך לתרום, אבל איכשהו זה מתקזז (האיבר השלישי תרם 4 וקיבל 9 וזה הביא את המאזן שלו ל 30).

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