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

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

תבנית:מבנה תבנית

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

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

תבנית:מבנה תבנית

נניח שיש מערך גלובלי תבנית:קוד בשורה בגודל $n$, ואנו צריכים להשתמש בו כדי לחשב את זמן שחיית המינימום ואת ברכות העצירה.