מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי - דג הסלמון: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
|||
שורה 148:
==הדפסת העצירות==
נניח שצריך להדפיס גם את העצירות. כלומר, לא מספיק רק להדפיס את הפתרון המהיר ביותר, אלא גם את פרטיו (היכן עוצר הדג במסלול המהיר ביותר). זה קל למדי - פשוט נוסיף עוד מערך {{קוד בשורה|S}}, ששומר בכל נקודה את העצירה הקודמת לאותה נקודה. נדאג לעדכן מערך זה במהלך האלגוריתם:
<source lang = "python">
# Calculates the minimum time for the fish to swim up to (including) some pool (k).
# Takes the up-to pool number (k).
Min-Time(k)
1
2
3
4
5
6
7
8
9
10
והנה הפונקציה {{קוד בשורה|Print-Stops}} שתדפיס את העצירות:
<source lang = "python">
# Prints the stops on the fastest route up to
# (and including) some pool number (i).
Print-Stops(i)
1
2
3
לסיכום, כך נדפיס הכל:
<source lang = "python">
# Run the algorithm, get the shortest time.
1
2 Print(m)▼
# Print the shortest time.
# Print the stops.
3 |