Question

dynamic_programming

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

ברצוננו לגלות מהי הקומה הקריטית (אם בכלל).

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

לדוגמה: אם נתונה ביצה אחת, יש צורך ב-nn הטלות שכן יש להטיל את הביצה מקומה 1 ועד הקומה ה-nn ויתכן כי הביצה לא תשבר באף אחת מההטלות.

1

Answers

נניח שאנחנו זורקים ביצה מהקומה ה-ii. אם הביצה נשברה אנחנו יודעים שהקומה הקריטית היא ii לכל היותר ואם הביצה לא נשברה אז הקומה הקריטית היא לפחות ii אם בכלל.

לכן, אם נסמן ב-f(μ,ν)f(\mu, \nu) את מספר הזריקות המינימלי הדרוש עם μ\mu ביצים ובניין בן ν\nu קומות, אז מתקיימת נוסחת הנסיגה הבאה:

f(μ,ν)=mini[ν]max{f(μ,i)f(μ1,νi) f(\mu, \nu) = \min_{i \in [\nu]} \max \begin{cases} f(\mu, i) \\ f(\mu - 1, \nu - i) \end{cases}

כמו כן, מתקיים ש-f(1,ν)=νf(1, \nu) = \nu ו-f(μ,0)=0f(\mu, 0) = 0.

אנחנו מעוניינים לחשב את הערך f(m,n)f(m, n) וניתן לעשות זאת בטבלה בגודל m×nm \times n.

סיבוכיות: חישוב ערך בודד לוקח O(n)O(n) זמן ובסך הכל O(mn2)O(mn^2).

1
Feedback