資料結構›Ch3 堆疊與佇列第 3 題/共 28 題
3. Stack、演算法設計
#DS-03-003中Stack演算法設計
Let be a stack containing coefficients , where , is at the top of the stack, and is at the bottom. The following algorithm computes . Identify the missing expression in the pseudocode.
POLY(S, x) 1 while S.size >= 2 2 u = S.pop() 3 v = S.pop() 4 S.push(□) 5 return S.pop()
參考答案與解析
答案 (B):這是 Horner's Rule 由高次到低次逐步累加的標準寫法。u 是先彈出的值(目前累加結果,初始是最高次係數 a_n),v 是後彈出、次高的係數。要往前推一步,新的累加值應該是「目前累加值 × x + 新係數」,也就是 u·x+v,才會一路算出 (...(a_n·x+a_{n-1})·x+...)+a_0。
📄 台大115
▤完整推導請見《WH 資工筆記 · 資料結構》Ch3 堆疊與佇列