חידה

מספר6

New member
חידה

איש אחד רוצה למדוד לעצמו את החום, אבל הוא לא יודע כמה זמן צריך להחזיק את המדחום בבית השחי. הוא יכול רק לחכות כמה זמן שנראה לו, ואז להוציא את המדחום ולראות אם המדידה הסתיימה (נניח שאפשר לראות את זה על המדחום באיזושהי צורה). אבל כאשר מוציאים את המדחום, הוא מתקרר מיד. מה שאומר שאם המדידה לא הסתיימה, יהיה עליו להחזיר את המדחום ולהתחיל למדוד מאפס. לדוגמה, אם צריך לחכות שלוש דקות והאיש חיכה רק שתי דקות, במדידה הבאה הוא עדיין יצטרך לחכות את מלוא שלוש הדקות. ידוע שזמן ההמתנה הוא לפחות שניה אחת, אבל הוא יכול להיות באורך כלשהו. האיש רוצה לבזבז כמה שפחות זמן. כלומר, אם צריך לחכות t שניות, הוא צריך שיטה שתבטיח סיום מדידה בתוך T שניות, כך שהיחס zz T/t zz הוא הקטן ביותר האפשרי. מהי השיטה הטובה ביותר למדוד את החום?
 
אני חושב...

שיש בעייה בהגדרה.. מכיוון ש-t יכול להיות כל מספר... יכולות להיות שתי שיטות שכל אחת פותרת את הבעייה טוב יותר מהשנייה, עבור tים שונים. - לפי נתוני השאלה לא נדע איזו להעדיף..
 

מספר6

New member
הכוונה לפתרון במקרה הגרוע ביותר

כלומר, מצא פתרון שהמקרה הגרוע ביותר שלו מינימלי
 

wesnoth

New member
פתרון

שיוציא את המדחום כשהוא מצפצף
 

slallum

New member
נראה לי..

להתחיל בשניה, וכל פעם להכפיל ב-2, עד שמגלים שזה מספיק, ברגע שמגלים שזה מספיק עושים חיפוש בינארי בין המקום האחרון למקום האחד לפני אחרון. הממ אפשר לחשב פה סיבוכיות?
 

מספר6

New member
אין צורך

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