בתשובה להקשה המקשה, 05/08/03 14:27
 |
|
 |
||
|
||||
 |
בשיטה הזאת יש קומה קריטית אחת שניתן למצוא בשתי זריקות, (1) שתי קומות קריטיות שניתן למצוא ב 3 זריקות, (2, 11) וכך הלאה עד 8 קומות קריטיות שניתן למצוא ב9 זריקות. (8, 17, 26 .. 71) ב10 זריקות ניתן למצוא 11 קומות (9, 10, 18, 27 .. 81, 91) ב11 זריקות ניתן למצוא 10 קומות (19, 20, 28 .. 82, 92) ב12 זריקות ניתן למצוא 9 קומות (29, 30, 38, 47 .. 83, 93) וכך הלאה עד שב18 זריקות מוצאים את הקומות 89, 90, ו99 וב19 זריקות את קומה 100. התוחלת (בהנחה של התפלגות אחידה) היא טובה בהרבה - בערך 8.8. |
 |
 |
 |
|
|
|
||
|
||||
|
אם הבנתי נכון, "ספירת המלאי" שרשמת מתיחסת לאסטרטגיה לפיה אחרי הקומה ה- 90 עוברים ל- 91 , 92, וכן הלאה. הלא כן? התוחלת שיצאה לי עבור אסטרטגיה זו היא 10.81 . יתכן שטעיתי, אבל הפער בין התוצאות שלנו משמעותי (מבחינת השאלה שבדיון). בכל אופן, גם תוצאה זו כבר די קרובה לתוחלת של פתרון-החסם-המינימלי. נניח שאני רוצה לכתוב תכנית מחשב שתמצא את האסטרטגיה האופטימלית. את מציאת המספר הכולל של אסטרטגיות אפשריות אני משאיר לחכמי הקומבינטוריקה והסיבוכיות (משהו יפה, עם נוסחת סטירלינג נניח, או פונקציות גמא, או סתם פונקציה היפרגאומטרית, יתקבל בברכה :) ). האם יש אפשרות ליעל את התהליך כך שלא יהיה צורך להתעסק עם אסטרטגיות שאינן "מבטיחות"? |
|
|
|
|
|
|
||
|
||||
|
אם אתה כבר יודע את התשובה לכל מספר קומות עד 99, אתה מוצא את האסטרטגיה האופטימלית ע"י חישוב פשוט שבודק רק את האפשרויות לזריקה הראשונה. בדרך זו אתה "ממשיך" את האסטרטגיה האופטימלית לבניין יותר נמוך (במקרה זה, עם 87 קומות) לאסטרטגיה אופטימלית ל-100 קומות. זה יעיל מאוד, ובוודאי לא מתעסק עם אסטרטגיות לא מבטיחות - זה בערך "חמדני". | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |