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.rax

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

您可能以下文章有趣

[WP7主模] Rainmeter

[便做] 客任 : The Matrix 幕

[] 修改命令提示字元的字色

[] 在命令提示字元移游