שאלת מבחן באלגוריתמים - האוניברסיטה הפתוחה 2022 - תכנות דינמי

שאלה 1 – תשלום במטבעות במטבעה רוקדת בצלעות אר רכך לישלם, יתנוני ממלוקחים שלמים. ויקימים, חדוקים השנויות שנכרוכים $1,3,5$ מטבעות שווה מחיר $f(n)$ היא $\geq 1$ מחיר, יתנוני מטבעה סדירה שלפט $Matglized$. חדוקים שנויות לשלם סמים עבור, לממש קדום משלם סדור מטבעה בעד $1$, או לחלופין, לשלם קדום $3$ רכך אחרוני מטבעה בעד $1$, ושלוני דרכים שנויות לשלם סדור מטבעה מצרך ישרר כ–$4$. (ג'–8 נק') הוכיחו כי לכל שלם יתנוני $n\geq 1$ אפשר למחשב את $f(n)$.

רמז: הגדירו את $f(n)$ כמספר הדרכים המסודרות לשלם סכום $n$. נסו למצוא נוסחת נסיגה עבור $f(n)$ על ידי בחינת המטבע האחרון שבו ניתן להשתמש.

פתרון: כדי להוכיח שניתן לחשב את $f(n)$ לכל $n \geq 1$, נציג אלגוריתם המחשב אותו. ראשית, נגדיר את הבעיה באופן מדויק ונפתח **נוסחת נסיגה**. יהי $f(n)$ מספר הסדרות השונות של מטבעות מהקבוצה $\{1, 3, 5\}$ שסכומן הוא בדיוק $n$. מכיוון שהשאלה מתייחסת ל"סדר" התשלום, אנו סופרים את כל הסדרות האפשריות. כל סדרת מטבעות שסכומה $n$ (עבור $n \geq 1$) חייבת להסתיים באחד המטבעות מהקבוצה $\{1, 3, 5\}$. נבחן את כל האפשרויות למטבע האחרון בסדרה: 1. **המטבע האחרון הוא 1:** אם המטבע האחרון הוא 1, יתר המטבעות בסדרה חייבים להצטבר לסכום של $n-1$. מספר הדרכים לעשות זאת הוא, על פי ההגדרה, $f(n-1)$. 2. **המטבע האחרון הוא 3:** אם המטבע האחרון הוא 3, יתר המטבעות בסדרה חייבים להצטבר לסכום של $n-3$. מספר הדרכים לעשות זאת הוא $f(n-3)$. 3. **המטבע האחרון הוא 5:** אם המטבע האחרון הוא 5, יתר המטבעות בסדרה חייבים להצטבר לסכום של $n-5$. מספר הדרכים לעשות זאת הוא $f(n-5)$. מכיוון ששלוש האפשרויות הללו זרות (סדרה אינה יכולה להסתיים בו-זמנית בערכים שונים), לפי עקרון הסכום, נוסחת הנסיגה עבור $f(n)$ היא: $f(n) = f(n-1) + f(n-3) + f(n-5)$ כדי שהנוסחה תהיה מוגדרת היטב, עלינו להגדיר **תנאי בסיס**: - $f(0) = 1$: ישנה דרך אחת בלבד להרכיב את הסכום 0 - באמצעות הסדרה הריקה (ללא מטבעות כלל). - לכל $n < 0$, נגדיר $f(n) = 0$, כיוון שלא ניתן ליצור סכום שלילי ממטבעות חיוביים. כעת, נוכל להציג אלגוריתם לחישוב $f(n)$ בשיטת **תכנות דינמי**, אשר בונה את הפתרון "מלמטה למעלה" על בסיס נוסחת הנסיגה. **אלגוריתם לחישוב $f(n)$:** 1. ניצור מערך `DP` בגודל $n+1$ לאחסון ערכי הפונקציה $f(0), f(1), \dots, f(n)$. 2. נאתחל את תנאי הבסיס: `DP[0] = 1`. 3. נרוץ בלולאה עבור `i` מ-1 עד $n$: א. נחשב את `DP[i]` באמצעות הערכים הקודמים שכבר חושבו: `val1 = (i >= 1) ? DP[i-1] : 0` `val3 = (i >= 3) ? DP[i-3] : 0` `val5 = (i >= 5) ? DP[i-5] : 0` `DP[i] = val1 + val3 + val5` 4. התוצאה הסופית היא הערך המאוחסן ב-`DP[n]`. אלגוריתם זה מבצע לולאה באורך $n$, ובכל איטרציה מבצע מספר קבוע של פעולות חשבון וגישה למערך. לכן, **סיבוכיות הזמן** שלו היא $O(n)$ ו**סיבוכיות המקום** היא $O(n)$. מכיוון שהצגנו אלגוריתם דטרמיניסטי, אשר עוצר תמיד לאחר מספר סופי של צעדים ומחשב את $f(n)$ לכל $n \geq 1$, הוכחנו כי $f(n)$ ניתן לחישוב. $\blacksquare$