מבני נתונים ואלגוריתמים - מחברת קורס/נספחים/חשיבה רקורסיבית/דג הסלמון/הבעיה

דג נולד בברכה הראשונה מתוך $\displaystyle n$ ברכות, המחוברות ע"י $\displaystyle n-1$ תעלות. הדג שוחה מהברכה הראשונה לאחרונה. לכל ברכה יש מספר המציין את משך הזמן שיש לשהות בה כדי להתאושש (חלק מהברכות נוחות יותר מהאחרות). התעלות, לעומת זאת, זהות, ושחייה בכל אחת מהן אורכת $\displaystyle 1$ יחידות זמן.

דוגמה: נשתמש כדוגמה בברכות הבאות לאורך הדף: הבריכות והתעלות במסלולו של דג הסלמון המסכן.

דג הסלמון צריך לבחור באיזו ברכה לעצור ולנוח, כדי לצמצם את משך הזמן הכולל מהברכה הראשונה לאחרונה. מדוע שהדג יעצור לנוח בכלל בברכה כלשהי? נניח שאם הדג אינו עוצר בברכה, אז השחייה בתעלה הבאה אורכת $\displaystyle 1.5$ יחידות זמן, השחייה בתעלה שלאחריה אורכת $\displaystyle 1.5^{2}$ יחידות זמן, השחייה בתעלה שלאחריה אורכת $\displaystyle 1.5^{3}$ יחידות זמן, וכן הלאה (עד שהדג עוצר לנוח בברכה). לשם הפשטות, נניח שהדג נח בברכה הראשונה והאחרונה.

מהו זמן המינימום למסלול הדג, ובאלו ברכות ינוח?

דוגמה: אם הדג נח רק בברכה הראשונה והאחרונה, אז הזמן הכולל הוא $\displaystyle 1.5+2\cdot (1.5^{6}-1)+1$, אבל אם דג הסלמון נח גם בברכה השלישית, אז הזמן הכולל יורד ל$\displaystyle 1.5+2\cdot (1.5^{3}-1)+0.2+2\cdot (1.5^{3}-1)+1$. שני פתרונות אפשריים.

נניח שיש מערך גלובלי Resting-Times בגודל $\displaystyle n$, ואנו צריכים להשתמש בו כדי לחשב את זמן שחיית המינימום ואת ברכות העצירה.