分治算法講解

1、分治算法一：基本概念（分而治之）分治就是把一個復(fù)雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。比如：二分查找，歸并排序，快速排序，樹的遍歷等等任何一個可以用計算機求解的問題所需的計算時間都與其規(guī)模有關(guān)。問題的規(guī)模越小，越容易直接求解，解題所需的計算時間也越少。例如，對于n個元素的排序問題，當n=1時，不需任何計算。n=2時，只要作一次比較即可排好序。n=3時只要作3次比較即可，。而當n較大時，問題就不那么容易處理了。要想直接解決一個規(guī)模較大的問題，有時是相當困難的。二：基本思想 分治設(shè)計思想：將一個大的問題

2、，分解成一個個小的，相同類型的問題，然后逐個擊破各個小問題，最后將小問題逐步合并，得到最終的解。（可能會用到遞歸，大問題里包含小問題，找到規(guī)律然后解決） 分治基本策略：對于一個規(guī)模為n的問題，若該問題可以容易地解決（比如說規(guī)模n較?。﹦t直接解決，否則將其分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。 三：分治使用情況 1) 該問題的規(guī)?？s小到一定的程度就可以容易地解決2) 該問題可以分解為相同類型的小問題（前提）3) 利用該問題分解出的子問題的解可以合并為該問題的解；（關(guān)鍵） 4) 該問題所分解出的各個子問題是相互獨

3、立的，即子問題之間不包含公共的子子問題。 第三條特征是關(guān)鍵，能否利用分治法完全取決于問題是否具有第三條特征，如果具備了第一條和第二條特征，而不具備第三條特征，則可以考慮用貪心法或動態(tài)規(guī)劃法。 四：基本步驟 （1）劃分：把問題的實例劃分成子問題 （2）求解：若是子問題比較簡單，就直接解決，否則遞歸求解子問題 （3）合并：合并子問題的解得到原問題的解課前引導(dǎo)：一：分段函數(shù) 例如：高中數(shù)學中的分段函數(shù)也是類似分治思想的體現(xiàn)，如看圖求y關(guān)于x的表達式。一個分段函數(shù)，反映的是x與y的關(guān)系，簡單來說，就是在R的范圍內(nèi)將y的表達式表示出來，那么這時候利用分治的思想，將R區(qū)間劃分為小區(qū)間，然后分別求出各個小區(qū)

4、間的表達式，最后合并起來，完成y關(guān)于x的表達式的求解二：大整數(shù)乘法123 345 678 * 3 = 370 037 034在這里我們可以這樣寫：123 * 3 = 369   345 * 3 = 1035   678 * 3=2034         組合在一起是    369 1035 2034。對比發(fā)現(xiàn)，當使用千進制的時候結(jié)果變成了370037034首先他滿足：第一條件：分解到一定小規(guī)模的時候可以解決

5、  第二條件：每個小規(guī)模都具有最佳子結(jié)構(gòu)（在變量范圍內(nèi)，可以用來表示）  第三條件：每個小問題可以通過合并在一起形成大問題的解  第四條件：每個小問題相互獨立專題一：分治算法之二分查找思考題：找假幣： 有一堆個數(shù)為32的硬幣，和一個天平，已知其中有一個假幣，且假幣比真硬幣輕，找出這個假幣1. 普通方法：兩兩比較，輕的那個是假幣，最多比較16次2. 二分法：將硬幣分為兩份，假幣在輕的那份中，然后繼續(xù)分，直到找出假幣，最多用5次 哪種方法好？課題：二分查找（折半查找）知識目標：理解二分查找算法的概念以及執(zhí)行過程。 重點：掌握二分查找算法的

6、常規(guī)寫法以及遞歸寫法。1. 邊界錯誤造成的問題2.死循環(huán)3. 溢出I. 算法介紹： 二分查找又稱折半查找，優(yōu)點是比較次數(shù)少，查找速度快，平均性能好;其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經(jīng)常變動而查找頻繁的有序列表。II. 思路分析：二分查找的基本思想是：（1）先確定一組順序排列的數(shù)據(jù)存儲到數(shù)組中，輸入要查找的數(shù)據(jù)（2）將數(shù)組元素的中值與查找的數(shù)據(jù)相比較，如果兩者相等，則子函數(shù)返回相應(yīng)的結(jié)果后終止；（3）否則利用中間位置縮小數(shù)據(jù)查找的范圍。如果中間位置的數(shù)組元素大于查找數(shù)值，則進一步查找中值之前的數(shù)組元素，否則進一步查找中值之后的數(shù)組元素。（4）重復(fù)上述過程，直

7、到在數(shù)組中找到相同的數(shù)字。（5）若在數(shù)組中找不到這個數(shù)據(jù)，則顯示查找不成功III. 算法框架： 按照分治算法三步驟，將二分算法作如下介紹：（1） 二分算法代碼設(shè)計模式: /arr表示要進行二分查找的順序排列對象數(shù)組，low表示數(shù)組下標的最小值，high表示數(shù)組下表的最大值，key表示要查找的元素 int erfen(int arr,int low,int high,int key) 如果數(shù)組下標的最小值大于最大值 則返回結(jié)果為-1至主函數(shù)；/表明在數(shù)組中不存在要查找的元素 確定數(shù)組的中間位置mid 若查找的元素等于數(shù)組的中間元素，則進行相應(yīng)的步驟 若查找的元素大于數(shù)組（指定范圍內(nèi)）的中間元素

8、則將查找范圍縮小至數(shù)組（指定范圍內(nèi)）中間元素右邊； 若查找的元素小于數(shù)組指定范圍內(nèi)的中間元素 則將查找范圍縮小至數(shù)組（指定范圍內(nèi)）中間元素左邊； 例題1：輸入一個整數(shù)n，然后按升序輸入n個整數(shù)，將它們存入數(shù)組a中，再輸入一個數(shù)x,然后在數(shù)組中查找x,如果找到，輸出相應(yīng)的最小下標，否則，輸出“Not Found”.普通寫法：#include<iostream>using namespace std;int main()int i,s100,n;cin>>n;for(i=0;i<n;i+)cin>>si;int x;cin>>x;for(i=0

9、;i<n;i+)if(si=x)cout<<i<<endl;break;if(i=n)cout<<"Not found"<<endl;return 0;二分寫法：#include<iostream>using namespace std;void erfen(int a,int n,int key)int low=0,high=n-1,mid;while(low<=high)mid=(low+high)/2;if(amid=key)cout<<"這個數(shù)的下標是："<

10、<mid<<endl;break; else if(amid>key)high=mid-1;elselow=mid+1;if(low>high)cout<<"Not Found！"<<endl; int main()int a100;int n,key,i;cin>>n;for(i=0;i<n;i+)cin>>ai;cin>>key;erfen(a,n,key);return 0;二分遞歸：#include <iostream>using namespace std;

11、int search(int a,int left,int right,int key) if(left>right) cout<<"Not found!"<<endl; exit(0); else int middle=(left+right)/2; if (amiddle=key) return middle; else if(key<amiddle) / 這里key是和amiddle比較，而非middle; right=middle-1; return search(a,left,right,key); else left=midd

12、le+1; return search(a,left,right,key); int main()int a100,n,x,left,right,i;cin>>n;for(i=0;i<n;i+)cin>>ai;left=0;right=n-1;cin>>x;cout<<"這個數(shù)的下標是："<<search(a,left,right,x)<<endl;專題二：分治算法之歸并排序歸并排序是分治算法的一個非常典型的應(yīng)用。歸并排序原理：歸并排序具體工作原理如下（假設(shè)序列共有n個元素）：將序列每相鄰兩個數(shù)字

13、進行歸并操作（merge)，形成floor(n/2)個序列，排序后每個序列包含兩個元素將上述序列再次歸并，形成floor(n/4)個序列，每個序列包含四個元素重復(fù)步驟2，直到所有元素排序完畢歸并操作：歸并操作(merge)，也叫歸并算法，指的是將兩個順序序列合并成一個順序序列的方法。如設(shè)有數(shù)列6，202，100，301，38，8，1初始狀態(tài)：6,202,100,301,38,8,1第一次歸并后：6,202,100,301,8,38,1，比較次數(shù)：3；第二次歸并后：6,100,202,301，1,8,38，比較次數(shù)：4；第三次歸并后：1,6,8,38,100,202,301,比較次數(shù)：4；總的比

14、較次數(shù)為：3+4+4=11；歸并基本算法：輸入兩個整數(shù)，作為兩個數(shù)組的長度，輸入兩個按升序排列好的數(shù)組，將兩個已排序的數(shù)組合并后存放在另一個數(shù)組中，且合并后的數(shù)組也是有序排列（要求不能合并后再排序），再輸出合并后的數(shù)組?！緲永斎搿? 51 2 3 45 6 7 8 9【樣例輸出】1 2 3 4 5 6 7 8 9代碼：#include<iostream>using namespace std;int main()int m,n,i,j,k=0,a100,b100,c200;cin>>m>>n;for(i=0;i<m;i+)cin>>ai;

15、for(j=0;j<n;j+)cin>>bj;i=0;j=0;while(i<m&&j<n)/當數(shù)組a和數(shù)組b都沒有完全賦值到數(shù)組c中時 if(ai<bj)/如果a數(shù)組里的元素比b數(shù)組的小 ck=ai;/就把數(shù)組a的元素賦給數(shù)組c i+;k+;/且將數(shù)組a和數(shù)組c的下標都往后移一位 else/要是數(shù)組b的元素比數(shù)組a的元素大時 ck=bj;/就把數(shù)組b的元素賦值到數(shù)組c中 j+;k+;/且將數(shù)組b和數(shù)組c的下標往后移一位 if(i=m)/當數(shù)組a已經(jīng)被完全賦值到數(shù)組c中 while(j<n)/當數(shù)組b還沒有完全賦值 ck=bj;/此時，

16、只需要把b數(shù)組中剩余的數(shù)全部賦值到數(shù)組c接下去的位置上 j+;k+;else/當數(shù)組b已經(jīng)被完全賦值到數(shù)組c中while(i<m)/當數(shù)組a還沒有完全賦值 ck=ai;/此時，只需要把a數(shù)組中剩余的數(shù)全部賦值到數(shù)組c接下去的位置上 i+;k+;for(i=0;i<m+n;i+) cout<<ci<<" " 歸并函數(shù)：所涉及知識過多，目前只需要了解思想【例題三】設(shè)有n=2k個運動員要進行網(wǎng)球循環(huán)賽?，F(xiàn)要設(shè)計一個滿足以下要求的比賽日程表：     (1)每個選手必須與其他n-1個選手各賽一次； 

17、60;  (2)每個選手一天只能參賽一次；     (3)循環(huán)賽在n-1天內(nèi)結(jié)束請按此要求將比賽日程表設(shè)計成有n行和n-1列的一個表。在表中的第i行，第j列處填入第i個選手在第j天所遇到的選手。其中1in，1jn-1。假設(shè)有8位參賽選手，8個選手的比賽日程表如下圖：【思路】按分治的實現(xiàn)過程，可以先找到上面所示日程表的規(guī)律，即對角線相等，那么所要完成的操作就是對角線填充。實現(xiàn)過程： (1)用一個for循環(huán)輸出日程表的第一行 for(int i=1;i<=N;i+) a1i = i (2)然后定義一個m值，m初始化為1，m用來控制每

18、一次填充表格時i（i表示行）和j（j表示列）的起始填充位置。    (3)用一個for循環(huán)將問題分成幾部分，對于k=3，n=8，將問題分成3大部分，第一部分為，根據(jù)已經(jīng)填充的第一行，填寫第二行，第二部分為，根據(jù)已經(jīng)填充好的第一部分，填寫第三四行，第三部分為，根據(jù)已經(jīng)填充好的前四行，填寫最后四行。for (ints=1;s<=k;s+)  N/=2;      (4)用一個for循環(huán)對中提到的每一部分進行劃分for(int t=1;t<=N;t+)對于第一部分，將其劃分為四個小的單元，即對第二行進行如下劃分   同理，對第二部分（即三四行），劃分為兩部分，第三部分同理。     (5)最后，根據(jù)以上for循環(huán)對整體的劃分和分治法的思想，進行每一個單元格的填充。填充原則是：對角線填充    &#