Inheritance - IS-A

在《Fundamentals of Data Structures in C++》中看到一段話

Inheritance is used to express subtype relationships between ADTs. This is also referred to as the IS-A relationship. We say that a data object of Type B IS-A data object of Type A if B is more specialized than A or A is more general than B; that is, all Bs are As, but not all As are Bs; or the set of all objects of Type B is a subset of the set of all objects of Type A. For example, Chair IS-A Furniture, Lion IS-A Mammal, Rectangle IS-A Polygon.

IS-A 及 HAS-A 是 OO 兩個很特殊的關係。HAS-A 就好比組裝，如：汽車有四個輪子，這代表每一個汽車物件其內部皆有四個輪子物件。簡單說就是物件中包有物件的關係。

而 IS-A 就有點像在探討本質，像：圓形窗子雖然改造過了，但它還是個窗子；桌子雖然是眾多家具之一，然而，他仍是種家具。

而 IS-A 的關係正解釋了為什麼 pointer to base class 可以指向 object of derived class 。

交響樂之雨 - 芙鈴

在第一個夢，就猜測到芙鈴是雅俐的化身，果不其然！

在故事最後，芙鈴的聲音漸漸出現在他人耳中，被他人接受、讚揚。也同時代表著雅俐將被外界接納。

昏迷不醒的雅俐，在故事最後與芙鈴合而為一。

不擅長歌唱的雅俐，與熱愛歌唱的芙鈴，似乎極難讓人聯想到為同一人。但，芙鈴正是雅俐內心的那股希望，雅俐希望能陪在庫里斯身邊、希望能與庫里斯合奏、也希望為庫里斯導引未來的方向，希望他不在迷網，希望他能憶起一切！

最後的結局，不再充斥著悲傷、迷惑，而是最歡樂，最圓滿的。
在經歷了一切震撼後，為這款遊戲留下最完美的結束！

交響樂之雨

活潑、開朗的朵魯坦，背負著什麼樣的壓力，以及那笑容下的悲傷？
溫柔、有禮的法珞，背後藏著何種不為人知的黑暗？
封閉、內向的黎瑟，隱藏了何種痛苦，何種心酸？

很推薦這款遊戲，當一切破曉，正是瀰漫整個遊戲的雨天放晴時。
它並不歡樂，Good Ending 也許稱做 True Ending 會為恰當。
然而，它活生生讓我們見到真真實實的黑暗，以及表象所遮蔽的酸甜苦辣。

心之雨，一首詳和配樂，但...何時才會放晴呢？

與朵魯坦在電車內的漫談？
在病床上與黎瑟的心靈交織？
還是那放晴般與法珞相處的假象？

一波又一波的震撼，正如同空之軌跡曲折離奇的劇情帶來的衝擊！

The Knuth-Morris-Pratt Algorithm

最簡易的子字串搜尋法，是對於每一個字元開頭 Si，判斷字串 S(i)S(i + 1)...S(i + n - 1)，是否與欲搜尋之字串 P(0)P(1)...P(n - 1)相同，然而，這樣的搜尋法複雜度為 O (n * m)，當資料量極大時，將秏費相當多的時間。

因此，為加快子字串搜尋的速度，不斷改良後，出現了名為 Knuth-Morris-Pratt 的演算法。

此演算法的精隨在於，比對失敗時，能跳過不需再比對的部分，迅速找出下一次的比對點。這與 DP 的要旨相符，「做過的就不要再做」。

Knuth 演算法如下：

對於每次的比對，若比對成功，則原字串及子字串的 index 各加 1，繼續比對。

若比對失敗，則視情況決定位移：
(1)若子字串的 index 為 0，代表開頭便不符，因此只需把原字串的 index 加 1 繼續比對。
(2)若在其他位置比對失敗，則根據位移表決定子字串的 index 移至何處繼續比對。


位移概念如下：

當原字串在位置 i 和子字串在位置 j 比對失敗，代表 P(0) ~ P(j - 1) 與 S(i - j) ~ S(i - 1) 的比對皆成功。

若字串 P(j - n)...P(j - 1) 與 P(0)...P(n - 1) 相同 （n為可行值之最大值），再根據上述條件，可知字串 P(j - n)...P(j - 1) 與 S(i - n)...S(i - 1)相同，因此可知 P(0) ~ P(n - 1) 與 S(i - n) ~ S(i - 1) 的比對皆會成功。

既然如此，只需從 P(n) 與 S(i) 比對起便可（因為確保 P(0) ~ P(n - 1) 的比對一定成功）


至於如何建表，在此就不多做說明。

快速建表法之 Code 如下：

int LengthP = Length ();   // LengthP 為子字串之長度
f[0] = -1;     // f 為表
for (int j = 1 ; j < LengthP ; ++j) {
    int i = f[j - 1];
    // str 為子字串名稱
    while ((*(str + j) != *(str + i + 1)) && (i >= 0))  
        i = f[i];
    if (*(str + j) == *(str + i + 1))
        f[j] = i + 1;
    else 
        f[j] = -1;
}

交響樂之雨 - 黎瑟西雅

黎瑟西雅，一位熱愛歌唱的女孩。而他的父親 - 古拉衛，是位極傲慢的貴族，為傳承家系的符德魯琴，他要求黎瑟專心在瑟藝上，而不準沉溺於歌唱。

在認識庫里斯之後，不斷與他合奏，而逐漸開放的心靈，讓他再度對唱歌抱持希望。然而，當他父親之知曉後，便藉由各種方法阻撓她與庫里斯的往來，弄傷她的腳，甚至，讓他喉嚨受傷！

庫里斯發現這件事後，堅持不讓黎瑟回家，他希望她能留在他家裡，不要再受到古拉衛的傷害。而從那天裡，他們便天天合奏，沉浸在音樂的樂趣之中。

在畢業公演的前一天，黎瑟打算回家偷拿出她最愛歌曲的樂譜。然而，諷刺的是，那曲子竟是他父親為母親所寫！

黎瑟是個孤兒，是被父親丟棄到孤兒院後再帶回的，而帶回的理由，只單單是她有彈符德魯琴的才華。這份樂譜當黎瑟在孤兒院時就擁有的，而因為這首曲子，她變得很喜歡唱歌。再被父親帶回後，為了不讓她迷戀於歌唱，於是將這份樂譜沒收。

黎瑟的母親 - 艾思珂，丟下古拉衛和女兒不管，跟著另一位歌手跑了。當時古拉衛忙著身為音樂家的事業，丟下家庭不管，才會釀成今日的局面。而這首曲子，正是為艾思珂所寫。

畢業公演結束後，古拉衛用言語把黎瑟騙回家，完全地破壞她的喉嚨！！他告訢庫里斯：「你奪走了她成為符德魯琴音樂家的可能性，所以我也要奪走他歌唱的才華。

Good Ending，卻是個悲劇，也許，名為 True Ending 會更為恰當。

兩人最後在一起了，但，失去歌聲和意識的黎瑟，真的有美好的未來嗎？也許當黎瑟清醒的那天，就是追尋夢想的開始，雖然不知何時才能時現，但庫里斯絕不放棄希望。他真誠地等待那天！

究竟是為了什麼，可以讓一個人冷酷到如此地步？甚至對自己女兒也狠得下心。
古拉衛，我想他瘋了，為了音樂家至高榮譽而瘋狂。他一生，究竟得到了什麼？為了名利，失去了家庭，失去了女兒，這樣值得嗎？只要能維持傳承下身為符德魯瑟家的驕傲，似乎世上的一切都不再重要。

Lyceenee，黎瑟最愛的曲子，雖然與原曲有些許差異，但這是她與庫里斯以記憶所寫下的曲子，代表著她與庫里斯相處的心情，對他們來說，這是最為珍貴的寶物。

演奏結束了，得到極高評價的他們，卻必須面對即將來臨的悲慘。
這...公平嗎？

庫里斯的介入，害了黎瑟嗎？然而，他的介入，卻真正讓黎瑟放開！
沒有庫里斯，今天的黎瑟，也許仍是個受到大家排斥，心靈封閉的女孩吧！

很喜歡這首曲子，沒有哀傷，只有滿滿的活力與希望。

計實

第一題：
基本的 GUI，平常作業有參與應不至於做不出來。

第二題 - Binary Search
二分搜尋法，要點在於區間的取捨，不論是前閉後開區間（[)），或前閉後閉區間（[]），各有不同的作法。
以在程式中最常見的前閉後開區間來說，當下界大於或等於上界時，就是搜尋結束之時。而上下界值的改變也是很重要的一環，程式碼如下：

while (l < u) {
    int mid = (l + u) / 2;
    if (array[mid] == number)
        return true;
    else if (array[mid] < number)
        l = mid + 1;
    else 
        u = mid;
}
return false;

上下界值改變的重點就在於 lower 要加1，但upper不用，因為下界是閉，代表包含此值，但 index 為 mid 之值已檢查過，因此應不在區間內，所以必須加1；而上界是開，代表不包含此值，因此直接設為 mid 便可。

第三題：遞迴作圖
以前中區學科有出過類似的題目（不過當時不是作圖，是求作標），概念上不難，難是難在要懂得如何在 GUI 介面上畫圖。其實這題算是我這次考試學到的東西吧！以前都還不知怎麼畫圖呢！ XD

英雄寂寞

一首極為優美的樂曲
那麼詳和、那麼沉穩，卻帶著淡淡的孤獨

「血洗神洲、天下止武」
一種不同於正道的理念
卻少有支持此理念之人

身為一名軍師，運籌帷幄，少有失誤
然而，卻缺少了與他共同謀策的智者

不凡一生，卻也寂寞一生

正為文武冠冕寂寞侯