למי שלא למד/ה תכנות מעולם, או לפחות ייצוג של מספרים בבסיס בינארי, החידה החדשה הזו יכולה להיות מאתגרת מאוד. נניח שרוצים לקבל תוצאה בהסתברות של 1 ל-6. האם לזרוק את המטבע שש פעמים? מה נעשה עם התוצאות? הרי בשש הטלות יש שתיים-בחזקת-שש (64) צירופים אפשריים של עץ ופלי, ו-64 בכלל לא מתחלק ל-6 בלי שארית…
למתכנתים, לעומת זאת, הפתרון יבוא די בקלות, ובמיוחד לאור הפתרון של החידה הקודמת. נשתמש במטבע כמחולל ביטים אקראיים, ונטיל אותה מספר פעמים כמספר הביטים המינימלי הדרוש כדי לייצג בבסיס 2 את המכנה של ההסתברות הרצויה לנו. כלומר, אם אנחנו רוצים שמשהו יקרה בסיכוי של X-חלקי-שש למשל, אז נטיל את המטבע שלוש פעמים – שלושה ביטים, שיכולים לייצג את הערכים העשרוניים 0 עד 7. אם המספר שקיבלנו גדול מדי (6 או 7) פשוט נחזור על הטלת המטבע עד שייצא מספר בטווח הנכון, ואז נבדוק אם הוא קטן מ-X או לא ולפי זה נחליט.
לדוגמה, כדי לקבל תוצאה בסיכוי של 1 ל-6, נבדוק אם המספר שהתקבל בשלוש הטלות הוא 000 (אפשרות יחידה ל"הצלחה"), או אחד מהקבוצה [001, 010, 011, 100, 101] (חמש אפשרויות ל"כישלון"), או אחד מהקבוצה [110, 111] (תוצאה לא רלוונטית, יש לנסות שוב). פתרון כזה יעבוד, אך הוא קצת בזבזני מבחינת מספר הטלות ככל שההסתברות הרצויה מאתגרת יותר, כגון "אחד למיליון" או "אחד חלקי פיי". האם תוכלו לחשוב על פתרון נוסף ויעיל יותר (רמז: בממוצע)?
הפתרון האחרון מאוד מגניב 😀
חידת המשך היא איך להפוך את ה"מטבע הלא מאוזן" שיש לנו ל"קוביה לא מאוזנת עם N פיאות", כלומר במקום להגריל תוצאה מבין 2 מאורעות, להגריל תוצאה מבין N מאורעות בהסתברויות שרירותיות כלשהן.
כבר יש לכם את כל הכלים שאתם צריכים 🙂
הפתרון הזה שקול לקירוב המאורע עם ההסתברות שאנחנו רוצים (נניח 1 ל-6 בדוגמה שלך) ע"י סכום של מאורעות בלתי תלויים עם הסתברות מהצורה 2 בחזקת (n-). למשל, אם רוצים לקבל מאורע כלשהו בהסתברות 0.6 אז ננסה לקרב אותו ע"י איחוד של מאורעות בלתי תלויים שסכום ההסתברויות שלהם הוא 0.6. נתחיל מהמאורע "סדרת ההטלות מתחילה ב-1" (אני מחליף פה את העץ והפלי ב-0 ו-1 בשביל הנוחות). ההסתברות למאורע הזה הוא 0.5, לכן אנחנו צרכים עכשיו למצוא עוד מאורעות שיתנו לנו הסתברות של 0.1. המאורע הבא שנותן לנו הסתברות קטנה או שווה ל0.1 הוא מאורע מהסגנון "סדרת ההטלות מתחילה ב-0001" שהיא גם… לקרוא עוד »
היה נראה לי משום מה שהתגובות הן פר עמוד.
הפתרון פה מתייחס לפתרון של החידה מעמוד 3.