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

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

{{דוגמה|תוכן = 
נשתמש כדוגמה בברכות הבאות לאורך הדף:
        
[[תמונה:dsa_salmon_fish_setting.png|מרכז|100%|הבריכות והתעלות במסלולו של דג הסלמון המסכן.]]}} 

דג הסלמון צריך לבחור באיזו ברכה לעצור ולנוח, כדי לצמצם את משך הזמן הכולל מהברכה הראשונה לאחרונה. מדוע שהדג        יעצור לנוח בכלל בברכה כלשהי? נניח שאם הדג אינו עוצר בברכה, אז השחייה בתעלה הבאה אורכת <math dir = "ltr">\displaystyle 1.5</math> יחידות זמן, השחייה בתעלה שלאחריה אורכת <math dir = "ltr">\displaystyle 1.5^2</math> יחידות זמן, השחייה        בתעלה שלאחריה אורכת <math dir = "ltr">\displaystyle 1.5^3</math> יחידות זמן, וכן הלאה (עד שהדג עוצר לנוח בברכה).      
לשם הפשטות, נניח שהדג נח בברכה הראשונה והאחרונה. 

מהו זמן המינימום למסלול הדג, ובאלו ברכות ינוח?
      
{{דוגמה|תוכן = 
אם הדג נח רק בברכה הראשונה והאחרונה, אז הזמן הכולל הוא <math dir = "ltr">\displaystyle 1.5 + 2 \cdot (1.5 ^6 - 1) +
          1</math>, אבל אם דג הסלמון נח גם בברכה השלישית, אז הזמן הכולל יורד ל<math dir = "ltr">\displaystyle 1.5 + 2 \cdot (1.5^3          - 1) + 0.2 + 2 \cdot (1.5^3 - 1) + 1</math>.
        
[[תמונה:dsa_salmon_fish_examples.png|מרכז|100%|שני פתרונות אפשריים.]]}} 

נניח שיש מערך גלובלי {{קוד בשורה|Resting-Times}} בגודל <math dir = "ltr">\displaystyle n</math>, ואנו צריכים להשתמש בו כדי לחשב את        זמן שחיית המינימום ואת ברכות העצירה.