Question

dynamic_programming
summer_18_b

נתונים nn מספרים ממשיים, a1,,ana_1, \ldots, a_n, רוצים ליצור מהם ביטוי חשבוני על ידי הוספת פעולות כפל וחיבור בין כל שני מספרים עוקבים,כך שערך הביטוי שיתקבל יהיה מקסימלי.

הערות:

  • המספרים נתונים בסדר מסוים ואין לשנות אותו.
  • כאשר מחשבים את ערך הביטוי פעולת כפל קודמת לפעולת חיבור.

א. השלימו את הקלט הבא עם פעולות חיבור וכפל כך שערך הביטוי שמתקבל מקסימלי.

0.1232= \begin{array}{|c|c|c|c|c|c|c|c|c|} \hline 0.1 & \quad & -2 & \quad & 3 & \quad & 2 & = &\quad \\\hline \end{array}

ב. הוצע לחשב את ערך הביטוי על ידי נוסחת הנסיגה הבאה:

f(i)=max{ai+f(i+1)aif(i+1) f(i) = \max \begin{cases} a_i + f(i + 1) \\ a_i \cdot f(i + 1) \end{cases}

כאשרf(i)f(i) הוא ערך הביטוי עבור הקלטai,,ana_i, \ldots, a_n ו-f(n)=anf(n) = a_n.

הראו שנוסחה זו אינה מחשבת בהכרח את ערך הביטוי המקסימלי.

ג. תארו אלגוריתם פולינומי שבהינתן nn מספרים ממשיים כלשהם, a1,,ana_1, \ldots, a_n, מוסיף פעולות כפל וחיבור בין כל שני מספרים עוקבים,כך שערך הביטוי שמתקבל יהיה מקסימלי.יש לנתח סיבוכיות זמן ריצה אבל אין צורך להוכיח נכונות.

1

Answers

א.

0.1×2+3×2=5.8 \begin{array}{|c|c|c|c|c|c|c|c|c|} \hline 0.1 & \times & -2 & + & 3 & \times & 2 & = & 5.8 \\\hline \end{array}

ב. למשל עבור הקלט 5,1,55,-1,5 ערך נוסחת הנסיגה הוא 20 בעוד שערך הפתרון האופטימלי הוא 9.

ג. נשים לב שאם קיימת פעולת חיבור במקום ה-ii אז אנחנו מעוניינים למקסם את הביטויים משמאל ומימין לפעולה. מצד שני יכול להיות שערך הביטוי המקסימלי מתקבל מפעולות כפל בלבד, כלומר אם נסמן ב-f(i,j)f(i,j) את ערך הביטוי המקסימלי עבור המספרים ai,,aja_i, \dots, a_j אז מתקיים ש:

f(i,j)=max{maxik<jf(i,k)+f(k+1,j)ikjak f(i, j) = \max \begin{cases} \displaystyle{\max_{i \leq k < j} f(i,k) + f(k + 1, j)} \\\\ \displaystyle{\prod_{i \leq k \leq j} a_k} \end{cases}

כאשר f(i,i)=aif(i,i) = a_i.

את הנוסחה הנ"ל אפשר לחשב במטריצה בגודל n×nn \times n לפי סדר האלכסונים.

סיבוכיות: אנחנו מחשבים O(n2)O(n^2) ערכים כאשר חישוב של כל ערך לוקח O(n)O(n) זמן ולכן בסך הכל O(n3)O(n^3) זמן.

1
Feedback