Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

這學期沒修演算法，順道複習一下同學的作業。

[演算法B] Homework3: (你必須至少完成二個題目，若完成二個以上的題目則可以取得額外加分)

(A) 請展示細節(資料結構及程序)來說明如何利用 presorting改善分而治之 2D rank finding演算法

討論：
根據以前寫這題的思路來看，當時剛好學了 BIT 和 ST，於是使用了排序->掃描線->區間查找，當然這個資料結構不可能是課堂上會教的。回到這一題，其實沒上課根本看不懂題目需求 orz。

step1. 先對所有點按照 x 軸由小排到大，也就是 presorting，這是為了後面中線取捨有關。
step2. D&C(left, right) {// array index
            if(left >= right)    return;
            mid = (left+right)/2;
            D&C(left, mid);//切 x = point[mid].x 垂直線
            D&C(mid+1, right);
            merge(left, mid, right);
       }
       merge(left, mid, right) {//sort by y-axis
            idx1 = left, idx2 = mid+1;
            idx3 = 0;
            count = 0;
            while(idx1 <= mid && idx2 <= right) {
                if(point[idx1].y < point[idx2].y)
                    TEMP_BUF[idx3++] = point[idx1++]
                    count++;
                else
                    TEMP_BUF[idx3].rank = point[idx2].rank + count
                    TEMP_BUF[idx3++] = point[idx2++];
            }
            while(idx1 <= mid)    
                TEMP_BUF[idx3++] = point[idx1++]
                count++;
            while(idx2 <= right)    
                TEMP_BUF[idx3].rank = point[idx1].rank + count
                TEMP_BUF[idx3++] = point[idx2++];
            move TEMP_BUF to point[].
       }
這個做法跟求逆序數對有點像，思考一下由於已經保證合併的時候，其中一邊 x 座標肯定比較大，
因此再依序出隊的時候，只需考慮 y 座標的大小，因此合併的時候對 y 座標由小到大排序。
多一個 count 得到左側的出隊個數，等到右側元素出隊時，count 恰好是該元素增加的 rank。

(B) 寫一個分而治之演算法來解決一 個給定的數值集合的求秩(rank finding)問題

討論：
這題看了一陣子才看懂題目，原來是從 2D 降至 1D，豈不是只要計算比它 x 小的個數！
也就是相當於 sort 後，索引值即該數的 rank。
--> 既然是 D&C，請參照 merge sort 的寫法，對 int arr[] 排序。

(C) 寫一個演算法來找出一群在X軸上的點中的最近點對(closest pair of points on X-axis)

討論：
只在 x 軸上的話，很明顯地可以察覺到根本 greedy，排序後對相鄰位置計算即可。

ret ← oo
sort(A, A+n) // 小到大
for i = 1 to n-1
    ret ← min(ret, abs(A[i]-A[i-1]))

(D) 寫出一個分而治之演算法來解決最長相同連續 元素 子序列(the longest identical consecutive element subsequence) 問題，並分析演算法的時間複雜度

討論：
這題根本就是最長平台！突然加一個 D&C 有點恍神，用 D&C 也是可解的。
一樣根據 D&C 的精神下去分治，將 [left, right] 分成 [left, mid] 和 [mid+1, right]
把每一個 [left, right] 當作是一個節點 parent，因此它會有兩個孩子 lson, rson。

每個節點記錄兩項資訊，
1. 左起最長，即 [left, left+lmax-1] 都是相同元素。
2. 右起最長，即 [right-rmax-1, right] 都是相同元素。
3. 中間最長，midmax 這個相當難解釋

合併的時候，
parent [left, right]
1. parent.midmax = lson.rmax + rson.lmax
2. parent.lmax = lson.lmax == lson.length && A[mid] == A[mid+1] ? lson.lmax+rson.lmax : lson.lmax
2. parent.rmax = rson.rmax == lson.length && A[mid] == A[mid+1] ? lson.rmax+rson.rmax : lson.rmax

(E) 寫出一個分而治之演算法來解決最長單調遞增 連續元素 子序列(the longest monotonically increasing consecutive element subsequence) 問題，並分析演算法的時間複雜度

這一題我已經崩潰了，為什麼需要分治 ...


一樣根據 D&C 的精神下去分治，將 [left, right] 分成 [left, mid] 和 [mid+1, right]
把每一個 [left, right] 當作是一個節點 parent，因此它會有兩個孩子 lson, rson。

每個節點記錄兩項資訊，
1. 左起最長，即 [left, left+lmax-1] 都是相同元素。
2. 右起最長，即 [right-rmax-1, right] 都是相同元素。
3. 中間最長，midmax 這個相當難解釋

合併的時候，
parent [left, right]
1. parent.midmax = lson.rmax + rson.lmax
2. parent.lmax = lson.lmax == lson.length && A[mid] <= A[mid+1] ? lson.lmax+rson.lmax : lson.lmax
2. parent.rmax = rson.rmax == lson.length && A[mid] <= A[mid+1] ? lson.rmax+rson.rmax : lson.rmax

(Bonus Programming Homework)
(P1) 寫一程式來實作改良式分而治之二維求秩演算法
(P2) 寫一程式來實作分而治之二維求最大點(2D maxima finding)演算法
(P3) 寫一程式來實作分而治之最近二維點對(closest pair of 2D points)演算法