分治法學習記錄

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

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

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