補考 10

HW4-5

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

【題目】

【題目】

A mathematical expression is given without parentheses. Design an algorithm to parenthesize the expression such that the value of the expression is maximized. For example, consider the expression: 2+7⋅5. There are two ways to parenthesize the expression 2+(7⋅5) = 37 and (2+7)⋅5 = 45, so in this case, your algorithm should output the second expression. Here, you may assume the given expressions contain only 3 kinds of binary operators ‘+’, ‘−’, and ‘⋅’.

【解題思路】

因為題目說有 + - * 三種運算符號,因此需要考慮 負值x負值 之類的狀況,所以要探討每個區間最大最小值做運算的狀況(有可能會是兩個子區間的最小值相乘而得到最大值),首先我們可以將表達式

a1 op1 a2 op2 opn1 an的數字
[ a1,a2,,an ]
和運算符號
[ op1,op2,,opn1 ]
分開來看。

而我們需要有兩個二維矩陣(數字大小)分別儲存子表達式內最大值max[i][j]及最小值min[i][j],代表 ij 所計算出來的最大值及最小值,而運算符號則放在一維陣列內 op[n-1]

【遞迴式】

assume amount of input is n

1i,jn
max[i][j], min[i][j]=ai,ifi=j.

max[i][j] = Maxik<j{max[i][k]op[k]max[k+1][j]max[i][k]op[k]min[k+1][j]min[i][k]op[k]max[k+1][j]min[i][k]op[k]min[k+1][j]max[i][j]subexpressionijMaximummax[1][n]

min[i][j] = Minik<j{max[i][k]op[k]max[k+1][j]max[i][k]op[k]min[k+1][j]min[i][k]op[k]max[k+1][j]min[i][k]op[k]min[k+1][j]min[i][j]subexpressionijMinimummin[1][n]

【蘇都扣】

//初始值設定 n = num_size; for i from 1 to n: max[i][i] = a[i], min[i][i] = a[i]; //主要部份 get_Max_expression(1,n){ for q from 1 to n-1: //不能超過n,固定現在運算的長度。 for i from 1 to n-q: //會是以陣列為斜的算下去 j = i + q; (max[i][j],min[i][j]) = sub_expression_result(i, j); return max[1][n]; } //跑遞迴式 sub_expression_result(i, j){ minimum = INT_MAX, maximum = INT_MIN; for k from i to j-1: MM = max[i][k] op[k] max[k+1][j]; //op是運算符號 Mm = max[i][k] op[k] min[k+1][j]; mM = min[i][k] op[k] max[k+1][j]; mm = min[i][k] op[k] min[k+1][j]; maximum = Max(MM, Mm, mM, mm, maximum); minimum = Min(MM, Mm, mM, mm, minimum); return maximum, minimum; }

【Example Expression = 3 - 4 * 7 + 6】

min 1 2 3 4
1 3 -1 -25 -49
2 -4 -28 -52
3 7 13
4 6
max 1 2 3 4
1 3 -1 -7 -1
2 -4 -28 -22
3 7 13
4 6

Ans:max[1][4]=1#

【括號】

//主要部份 //maxExp[][], minExp[][] 是用來記錄發生 max, min 時的 expression get_Max_expression(1,n){ for q from 1 to n-1: //不能超過n,固定現在運算的長度。 for i from 1 to n-q: //會是以陣列為斜的算下去 j = i + q; (max[i][j],min[i][j],MT,mT,MF,mF) = sub_expression_result(i, j); placing_paretheses(maxExp,MT,MF,i,j); placing_paretheses(minExp,mT,mF,i,j); return max[1][n], maxExp[1][n]; } //跑遞迴式 //MT, mT 用來記錄當 max, min 發生, k 的值 //MF, mF 用來記錄當 max, min 發生, 是種組合 sub_expression_result(i, j){ minimum = INT_MAX, maximum = INT_MIN; for k from i to j-1: MM = max[i][k] op[k] max[k+1][j]; //op是運算符號 Mm = max[i][k] op[k] min[k+1][j]; mM = min[i][k] op[k] max[k+1][j]; mm = min[i][k] op[k] min[k+1][j]; maxTemp = Max(MM, Mm, mM, mm); minTemp = Min(MM, Mm, mM, mm); if maxTemp > maximum // 表 maxTemp 為當前最大 maximum = maxTemp; MT = k; MF is the the combination about maximum; //MM, mm, Mm? if minTemp < minimum // 表 minTemp 為當前最小 minimum = minTemp; mT = k; mF is the the combination about minimum; return maximum, minimum, MT, mT, MF, mF; } //插入括號 placing_paretheses(Exp[][], T, Flag, i, j){ switch(Flag) { case 'MM': exp[i][j] = '(' + maxExp[i][T] + op[T] + maxExp[T + 1][j] + ')'; break; case 'Mm': exp[i][j] = '(' + maxExp[i][T] + op[T] + minExp[T + 1][j] + ')'; break; case 'mM': exp[i][j] = '(' + minExp[i][T] + op[T] + maxExp[T + 1][j] + ')'; break; case 'mm': exp[i][j] = '(' + minExp[i][T] + op[T] + minExp[T + 1][j] + ')'; break; } }

【Example Expression = 3 - 4 * 7 + 6】

max 1 2 3 4
1 3 (3-4) ((3-4)*7) (((3-4)*7)+6)
2 -4 (4*7) (4*(7+6))
3 7 (7+6)
4 6
min 1 2 3 4
1 3 (3-4) (3-(4*7)) (3-(4*(7+6)))
2 -4 (4*7) ((4*7)+6)
3 7 (7+6)
4 6