分治法學習記錄

2019-11-11 03:31:07

字體：大中小

來源：轉載

供稿：網友

分治法學習記錄

#include <iostream>#include <vector>using namespace std;int maxsum (vector<int> ivec, vector<int>::iterator start, vector<int>::iterator end){ if (start == end) return *start; /*檢查序列是否為空或僅有一個元素*/ vector<int>::iterator mid = start + (end - start)/2; int **maxs** = max(maxsum(ivec, start, mid), maxsum(ivec, mid, end)); /*若最大連續和不過中間*/ int Lsum = 0, Rsum = 0, temp = 0;; vector<int>::iterator iter = mid-1; while (iter-- >= start) Lsum = max(Lsum, temp += *iter); iter = mid; temp = 0; while (iter++ <= end) Rsum = max(Rsum, temp += *iter); /*由中間開始分別向兩邊延伸求求最大連續和序列*/ return max(maxs, Lsum+Rsum);}int main(int argc, const char * **argv**[]) { vector<int> ivec; int num = 0; while(cin >> num) ivec.push_back(num); cout << maxsum(ivec, ivec.begin(), ivec.end()) << endl; return 0;}

先說一點：看遞歸應該廣度優先遍歷！！！ 這是我被坑懵逼了無數次得出的結論。。。。。追求這個函數最后遞歸成啥樣的人都死的很難看。。。。話說回來，這程序是因為我實在看不過眼書上用數組實現的代碼，于是改成了用vector實現（其實就是改了幾個類型和變量名），然而我不能理解的是， 為什么特么的會有死循環？？？ 為什么遞歸的時候迭代器出界了？？？ 我不能理解啊喂！！！！(╯‵□′)╯︵┻━┻，明明和原代碼一毛一樣！！！！

咳咳回到正題，分治法：劃分，遞歸解決，合并序列。問題最大的是合并序列，很多情況下這個問題一旦被分開了就合不起來了，書上的大部分例子在剛看到的時候都有這感覺。這其實是人對于遞歸有一定誤解的情況下發生的情況，就像上面說的，別看到遞歸就想著“下一層是啥情況？”“再下面一層是啥情況？”，一般來說，看遞歸，預先了解這函數是干嘛的，得到功能后直接把功能帶入遞歸代碼中，不要硬想著下一層發生了啥，比方說這幾行：

while (iter-- >= start) Lsum = max(Lsum, temp += *iter); iter = mid; temp = 0; while (iter++ <= end) Rsum = max(Rsum, temp += *iter);

真往下層看根本不是個頭，直接從代碼介紹中獲得“這函數獲取這一段中的最大連續和”，代入后即可獲得注釋中寫的內容。另外，這個程序中用“左閉右開”的集合范圍，好處是在處理“數組分割”時比較自然，區間[x,y)被分為[x,m)，[m,y)兩部分，不需要在任何地方加減一。還有一個細節：x+(y-x)/2來獲取序列的中間值，盡管在數學上這和(x+y)/2結果一樣，但計算機計算時會向下取整，會更自然的分成上面說的形式。

上一篇：yang模型理解

下一篇：yang模型理解