考研中某些算法的分治法解释

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可