חידה ובעיה
אהלן, מצורפת שאלה של ניתוח זמן ריצה. אני אשמח אם מישהו יוכל להגיד לי מה לדעתו זמן הריצה בכל קטע קוד קטן כזה (אני כבר פתרתי, אבל לא בטוח בתשובות שלי) ושאלה נוספת- שהיא יותר חידה יש משחק. שחקן א בוחר מס' A בין 1 לN. (תחום) שחקן שני צריך למצוא את המס' בכמה שפחות שלבים- כאשר בכל שלב מותר לו לשאול עד A שאלות (לכן בפעם הראשונה הוא רשאי לשאול שאלה 1 כי הוא לא יודע אם המס' A גדול מ1) לדוגמא לאחר שישאל אם המס' A גדול מ10 ויקבל תשובה חיובית יוכל לשאול 11 שאלות בתור הבא. המשחק מתנהל כך שהשואל מגיש רשימת שאלות ונענה על כולן בבת אחת. מה אלגוריתם הפתרון היעיל ביותר?
אהלן, מצורפת שאלה של ניתוח זמן ריצה. אני אשמח אם מישהו יוכל להגיד לי מה לדעתו זמן הריצה בכל קטע קוד קטן כזה (אני כבר פתרתי, אבל לא בטוח בתשובות שלי) ושאלה נוספת- שהיא יותר חידה יש משחק. שחקן א בוחר מס' A בין 1 לN. (תחום) שחקן שני צריך למצוא את המס' בכמה שפחות שלבים- כאשר בכל שלב מותר לו לשאול עד A שאלות (לכן בפעם הראשונה הוא רשאי לשאול שאלה 1 כי הוא לא יודע אם המס' A גדול מ1) לדוגמא לאחר שישאל אם המס' A גדול מ10 ויקבל תשובה חיובית יוכל לשאול 11 שאלות בתור הבא. המשחק מתנהל כך שהשואל מגיש רשימת שאלות ונענה על כולן בבת אחת. מה אלגוריתם הפתרון היעיל ביותר?