Lab 16-1: High Dimensional Polynomial:
single class design, inner struct, vector, the Big3,
simple algorithm, and assert

期中綜合練習

1. 練習如何運用 Visual Studio 2010 界面宣告類別 (2005/2008, VC6)
2. 練習如何使用 private 與 public access specifier (了解 C++ 如何控制存取權限)
3. 練習如何定義成員函式 (member function), 在成員函式中如何存取類別資料
4. 浮點數的比對
5. 內部結構
6. vector<type> 使用
7. Reference
8. The Big3
9. merge sort algorithm
10. assert 應用
11. unitTest()

這些東西不是都在前面實習一個一個辛苦地做過了嗎? 何必又來一次? 前面到底發生什麼狀況了????

底下所有的 code 原則上都不讓你直接拷貝, 目的是希望你被迫自己打, 既然都要打字了, 會不會能夠避免你在不了解的情況下還能夠完成實習, 會不會碰巧你在打的時候評估了其它種寫法的可行性, .... 試看看會不會是問題的關鍵? (雖然實習已經過了一半, 也許你會覺得就算找到為什麼前面實習沒有效果的原因, 好像沒有什麼太大用了, 但是也許你應該想想說是不是你的專業生涯已經過了一半了呢?? 如果還有長長久久的時日, 那麼找到學習障礙的關鍵就是很有幫助的了!)

在一個應用軟體中，需要使用許多高次數的一元多項式來進行運算，例如

f(x)=1.5x²⁵-2.3x¹¹+x⁷

因此設計一個 HiDPoly 類別，每一個 HiDPoly 類別的物件代表一個 n 次實數係數的一元多項式，這樣的物件需要有一些基本的資料設定、運算、與驗證功能，如下程式所示：

請下載資料檔案 poly.dat 及 範例執行程式

範例輸出資料:

poly1 = 2.1*x^8 + 3.5*x^5 + 5.4*x^2 + 0.6*x^0
poly2 = 4.1*x^12 + 6.5*x^10 + 2.4*x^4 + 1.6*x^2 + -3.5*x^1
poly1+poly2 =
4.1*x^12 + 6.5*x^10 + 2.1*x^8 + 3.5*x^5 + 2.4*x^4 + 7*x^2 + -3.5*x^1 + 0.6*x^0
poly1*poly2 =
8.61*x^20 + 13.65*x^18 + 14.35*x^17 + 22.75*x^15 + 22.14*x^14 + 42.6*x^12 + 7.26*x^10 + 1.05*x^9 + 5.6*x^7 + 0.71*x^6 + 10.08*x^4 + -18.9*x^3 + 0.96*x^2 + -2.1*x^1

請回答下列問題，依序完成 HiDPoly 類別 (HiDPoly.h 及 HiDPoly.cpp) 的設計

根據上面這一段程式的內容，這個 HiDPoly 類別至少應該有

1. 一個建構元 (constructor) 函式由輸入串流讀入多項式
2. 一個 addEqual() 成員函式負責將兩個多項式相加起來
3. 一個 mulEqual() 成員函式負責將兩個多項式相乘起來
4. 一個 print() 成員函式負責列印一個字串訊息以及多項式
5. 兩個 equals() 成員函式

請在 HiDPoly.h 檔案中宣告這個類別，以及這幾個成員函式的原型 (prototype)，請根據上述程式設計各個參數的型態、回傳值的型態、以及存取權限 (public or private)，可以使用const 的地方請盡量使用

參考程式

接上題，因為題目希望這個類別的物件可以存放高次數的一元多項式，也沒有限制最高次數是多少，看上面的例子又發現可能是很稀疏的高次多項式，例如

f(x)=1.5x⁴⁵-2.3x¹¹

所以我們希望在 HiDPoly 類別內定義一個有兩個欄位 degree 和 coef 的結構 DegreeCoef 來描述多項式的每一項：例如 (45,1.5) 和 (11,-2.3)，請定義此內部結構 (inner struct/class)

HiDPoly類別的物件需要有兩個資料成員：

1. 其一是一個整數用來存放多項式有幾項
2. 另一個成員是運用標準函式庫中的vector來存放動態配置的DegreeCoef結構的指標

請在類別中定義此兩個資料成員並說明 HiDPoly.h 檔案中需要的引入檔

參考程式

請撰寫預設建構元 (default constructor) 成員函式, 運用初始化串列 (initialization list) 將多項式項數設為 0

參考程式

請撰寫由資料檔案串流中讀取多項式的建構元函式，資料的格式如上圖 poly.dat 所示，首先是一個整數代表多項式的項數，接下來每一列資料代表多項式的一項 (次數, 係數) (例如 8 2.1 代表 2.1 x⁸ 這一項)，在檔案中每一個多項式都是先列出高次項然後才列出低次項，在物件中的 vector 成員內也需要依照這種順序排放各項的次數及係數

參考程式

請撰寫多項式相加的成員函式 addEqual(const HiDPoly &rhs)，相加的結果修改原來物件中的多項式，例如：

(2.1 x⁸ + 3.5 x⁵ + 5.4 x² + 0.6) + (4.1 x¹² + 6.5 x¹⁰ + 2.4 x⁴ + 1.6 x² - 3.5 x) =
4.1 x¹² + 6.5 x¹⁰ + 2.1 x⁸ + 3.5 x⁵ + 2.4 x⁴ + 7 x² - 3.5 x + 0.6

請注意相加以後的多項式的內部資料還是需要由高次項排到低次項，相同次數的係數需要加起來，演算法的效率不需要特別考慮，以正確完成功能為優先目標

基本演算法, 參考程式 part1, part2

請注意相乘以後的多項式的內部資料還是需要由高次項排到低次項，相同次數的係數需要加起來

基本演算法, 參考程式

請實作一個 print 成員函式列印出多項式列印出多項式到傳入的資料串流，以符合上圖的測試輸出

參考程式

由於 HiDPoly 類別的資料成員包含動態配置的資料，所以請撰寫一個拷貝建構元成員函式，另外請問不撰寫拷貝建構元常常會遇見的錯誤是什麼?

參考程式

與上題相同的原因，請製作一個設定運算子 operator=() 成員函式以支援上圖中第13列複製一個 HiDPoly 物件(你可以使用 vector<type>::erase(vector<type>::iterator start, vector<type>::iterator end) 成員函式來刪除 vector<type> 物件中所有的資料)

參考程式

與上題相同的原因，請撰寫解構元(destructor)成員函式以避免 memory leakage

參考程式

請撰寫驗證加法正確性的 equals() 成員函式，這個函式的參數需要包括一個 HiDPoly 物件的參考以及一個誤差的範圍，這個函式裡請你比較兩個多項式裡每一個係數是否都在指定的誤差範圍內 (請注意兩個多項式因為經過計算，有可能項數並不相同，有可能有一個多項式有 10^-13 x⁵ 這種係數很小的資料項，而另一個多項式根本沒有 x⁵ 項，就算出現這種狀況，只要誤差在指定的範圍內，就算是相同的)，可以運用 math.h 裡面計算浮點數絕對值的 double fabs(double) 函式

基本演算法, 參考程式 part1, part2

請撰寫一個計算函式值的 evaluate() 成員函式，參數是一個 double 型態的 x 數值，此成員函式可以運用標準 C/C++ 的 math.h 函式庫中的 double pow(double base, double exponent) 函式來計算 f(x) 的數值

參考程式

請撰寫驗證乘法正確性的 equals() 成員函式驗證 f(x)=g(x)h(x)，這個函式的參數需要包括兩個 HiDPoly 物件 g(x) 與 h(x) 的參考，這個成員函式裡請你運用標準 C/C++ 的 stdlib.h 函式庫中的 rand() 函式隨機挑選 1000 個浮點數 x，分別計算 f(x)、g(x)、與 h(x), 並且驗證浮點數 g(x)*h(x) 和 f(x) 的差值是否在 f(x)*10^-10 的相對誤差範圍內，如果 1000 個中發現任何一個錯誤就算是驗證失敗，回傳 false

參考程式