1、考研中某些算法的分治法解釋所謂分治法，簡單概括就是：將暫且不能解決的大問題分成很子問題，如果子問題還是不能解決則繼續劃分，直到子問題小到可以直接解決的規模，原問題的解即子問題的解的合并。說明：雖然分治法在考研中不會單獨拿出來考查，但是它對考研要求的一些算法的理解有很大幫助，這里通過幾個例題,由簡到難，來體會一下。例題1.用分治法打印數組，aLR。分析:一個循環就可以，但是我們現在要用分治法來分析，怎么做呢？如果待打印序列長度為1，則可以直接打印；如果待打印序列長度N，則可以將其劃分為兩部分:第1個元素是一個劃分，后N-1個元素是一個劃分。第一個劃分可以直接打印，然后將后N-1個繼續劃分，直到數

2、組長度為1，可以直接打印，或者長度為0，什么也不做。由此可以寫出以以下碼：void print(int a,int L,int R)/要處理的序列范圍在LR內 if(L>R) return; /說明是空序列，什么也不做，直接return返回。else if(L=R) cout<<aL<<" "/L等于R，待處理序列長為1，直接打印。else /否則待處理序列長度大于1，需要分治。cout<<aL<<" "/先打印第一個。print(a,L+1,R);/對從L+1R的序列進行分治處理。例題2.假設存在一

3、個函數divid()，可以將一個數組aLR分成兩部分，元素aL為分界線，小于aL的元素在左邊，大于aL的元素在右邊。函數divid()的聲明如下：void divid(int a,int L,int R);試用分治法，對數組aLR中元素進行快速排序。分析：如果序列長度1，則默認為是有序的，如果序列長度大于1，則用divid()函數將其劃分成3部分：左邊是小于aL的部分，中間是aL，右邊是大于aL的部分。aL已經有序，則只需對其左右兩部分繼續進行分治處理。由此可寫出以下代碼：void Qsort(int a,int L,int R)int mid;if(L>=R)return;/當序列為空

4、或者長度為1時，默認有序，什么也不做。elsemid=divid(a,L,R);/找分界點。Qsort(a,L,mid-1);/對左邊序列繼續分治處理。Qsort(a,mid+1,R);/對右邊序列繼續分治處理。例題3.一棵二叉樹存儲在二叉鏈表中，用分治法打印所有結點值，根結點由p所指。分析：當樹為空時，什么都不用做，問題直接解決。當樹中結點數大于等于1時，可用根結點將整棵樹劃分：分為根，左子樹和右子樹3個劃分；根結點直接打印，對左子樹繼續分治處理，對右子樹繼續分治處理，最終可以打印整棵樹。由此可以寫出以下代碼：void printTree(BTNode *p)if(p=NULL)return

5、;/樹為空，則問題直接解決。elsecout<<p->data<<" "/打印根結點。printTree(p->lchild);/分治處理左子樹。printTree(p->rchild);/分治處理右子樹。說明：以上就是二叉樹先序遍歷的分治法解釋。例題4.假設一個連通圖G用鄰接表存儲，用分治法打印圖中的所有頂點值，假設圖中結點數大于1。分析：例如下圖，假如從頂點v開始打印，則可以將整個圖分成分n部分，由v引出的一條邊算一部分，這與例題3的情況類似，二叉樹用根結點講整棵樹劃分成根，左子樹和右子樹，而這里劃分分為v，第1條邊所到達的子圖

6、，第2條邊所到達的子圖第n條邊所到達的子圖；v可以直接打印，然后對各個子圖進繼續進行分治處理。因圖中可能有回路，則設置訪問標記數組visit來檢測當前的劃分是否需要去處理。例題4 圖由此可以寫出以下代碼：visitv=1;void printfG(AGraph *G,int v) ArcNode *p; visitv=1; /置已訪問標記，表示當前劃分已經處理過。 cout<<v<<” ”; /打印出v。 p=G->adjlistv.firstarc; /p指向頂點v的第一條邊的終結點。 /*這個循環完成對由v的n條產生的n個劃分逐個繼續進行分治處理*/ whil

7、e(p!=NULL) if(visitp->adjvex=0)/檢測當前劃分是否已經處理過。 printfG (G,p->adjvex); /繼續分治處理當前劃分。 p=p->nextarc; /準備分治處理下一個劃分。說明：這就是圖的深度優先搜索遍歷的分治法解釋。例題5.已知二叉樹的先序遍歷序列和中序遍歷序列，分別存儲在aL1R1與bL2R2兩個數組中，用分治法由這兩個序列建立一棵二叉樹，存儲在二叉鏈表存儲結構中。分析：如果為空序列，則什么都不做，問題可以直接解決；如果序列長度大于1，則：aL1為二叉樹的根結點，在b中找到aL1，假設下標為k，則bL2k-1是其左子樹上的所

8、有結點，bk+1R2是其右子樹上的所有結點。反應在a中，即aL1+1L1+k-L2是其左子樹上的結點，aL1+k-L2+1R1是其右子樹上的所有結點；這樣對aL1+1L1+k-L2與bL2k-1繼續進行分治處理，對aL1+k-L2+1R1與bk+1R2繼續進行分治處理，最終可以將樹建立完畢。由此可寫出如下代碼：BTNode* CBtree(int a,int b,int L1,int R1,int L2,int R2)int k;if(L1>R1)return NULL;/序列為空，問題直接解決，生成空樹。elses=(BTNode*)malloc(sizeof(BTNode)s->

9、;data=aL1;for(k=L2;k<=R2;k+)/查找分界點if(aL1=bi)break; /*以下對子序列分別進行分治處理*/s->lchild=CBtree(a,b,L1+1,L1+k-L2,L2,k-1);s->rchild=CBtree(a,b,L1+k-L2+1,R1,k+1,R2);例題6.漢諾塔問題，有3根柱子，x,y,z，第一根上有n個盤，從上到下依次增大，要求將第一個柱子上的所有盤移動到底三根柱子上，整個過程都必須滿足一根柱子上的盤子從上到下依次。分析：這個是利用分治法解題的經典題目，過程如下：如果第一根柱子上只有1個盤子，則直接移動即可；如果第一根柱子上的盤子大于1個，則將柱子上的盤子劃分成兩部分，最下邊的盤子為1部分，上n-1個盤為一部分，對上n-1個盤繼續分治處理，將其先移動到第二個柱子上，此時第一個柱子上只有1個盤，可直接移動到第三根柱子上，然后將第二根柱子上的n-1個盤繼續分支處理，移動到第三個柱子上，此時整個問題解決。由此可寫出以下代碼：void Han(int x,int y,int z,int n)/*代表將n個盤子分治的從x移到z上，y做輔助柱。*/ if(n=1) move(x,z);/n為1可