ויקיספר

מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי - דג הסלמון: הבדלים בין גרסאות בדף

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמתהעריכה הבאה ←
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
Atavory (שיחה | תרומות)
7,521 עריכות
Atavory (שיחה | תרומות)
7,521 עריכות
שורה 14:
 
{{:מבני נתונים ואלגוריתמים - מחברת קורס/נספחים/חשיבה רקורסיבית/דג הסלמון/הבעיה}}
 
דג נולד בברכה הראשונה מתוך <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>, ואנו צריכים להשתמש בו כדי לחשב את זמן שחיית המינימום ואת ברכות העצירה.
 
==הרקורסיה הפשוטה==
אוחזר מתוך "https://he.wikibooks.org/wiki/מבני_נתונים_ואלגוריתמים_-_מחברת_קורס/אלגוריתמים/תכנון_דינאמי_-_דג_הסלמון"