普及讲座1-递归与分治C++版

江苏省大丰高级中学陈鹏PengChenJiangSuDaFengSeniorHighSchool,递归与分治Recursionif(x=1)return1;p=1;elsereturnfac2(x-1)*x;for(i=1;i=3时，先将前n-1个盘子以C为中介移到B柱子；再将第n个盘子移到C柱子；最后将n-1个盘子以A为中介从B柱移到C柱。,一递归,2020年5月1日星期五,18,参考程序片断move(total，A，B，C);voidmove(intn,charz1,charz2,charz3)if(n=1)printf(%c-%cn,z1,z3);elsemove(n-1,z1,z3,z2);printf(%c-%cn,z1,z3);move(n-1,z2,z1,z3);,一递归,2020年5月1日星期五,19,例5：数字排列问题描述由m个A，n个B组成若干个排列。从某个排列的位置1开始数，数到任意位置时都能保证A的个数不少于B的个数，则称该排列为合理排列。例如：当m=2，n=2时排列有：AABB(合理)ABAB(合理)ABBA(不合理)BBAA(不合理)合理排列数有2种。,一递归,2020年5月1日星期五,20,输入格式仅一行为两个整数m，n（1=n=1search(w-an,n-1);search(w,n-1);,一递归,2020年5月1日星期五,27,问题三：输出每种装载方案。voidsearch(intw,n)ifw=0printf(t);exit;ifn=1t+=1;ct:=an;search(w-an,n-1);t-=1;search(w,n-1);,一递归,2020年5月1日星期五,28,再思考：问题四：给定背包容量W和物体种类N，以及每种物体的重量Wi，每种物体只有一个，尽可能将背包装满的方案。,一递归,2020年5月1日星期五,29,递归小结1、数据的定义形式是递归的，如求Fibonacci数列问题。2、某些问题虽然没有明显的递归关系或结构，但问题的解法是不断重复执行一种操作，只是问题规模由大化小，直至某个原操作（基本操作）就结束，如汉诺塔问题，这种问题使用递归思想来求解比其它方法更简单。3、数据之间的逻辑关系（即数据结构）是递归的，如树、图等的定义和操作。,一递归,2020年5月1日星期五,30,优缺点优点：它能使一个蕴含递归关系且结构复杂的程序简介精炼，增加可读性。特别是在难于找到从边界到解的全过程的情况下，如果把问题推进一步,其结果仍维持原问题的关系，则采用递归算法编程比较合适。缺点：1、冗余计算造成程序的效率很低。2、边界条件设置不当的情况下，经常造成死循环或者内存(系统栈)溢出的窘境，导致递归深度有限。所以，一般递归子程序中不要定义局部数组。,一递归,2020年5月1日星期五,31,直接将递归转化成递推1、当递归关系有明确的定义时，一般来说，相邻的两个数之间有着规律性的变化，我们常常可以利用这种规律性的变化，一步一步递推出结果，而将递归结束条件作为递推的初始条件。实现这种递推通常使用循环迭代的方法，如循环累乘、计算斐波那切数据项等。2、当递归关系没有明确的递归式时，也可以转化成递推来完成，这就需要不断的缩小问题的规模，找出规律性的变化。,二分治,2020年5月1日星期五,32,引例分硬币问题问题描述有n个硬币，其中有一个是伪币，重量和其他硬币不一样，你有一个天平，如何找到这个伪币呢？算法分析先将这些硬币分成两个一组，每一次只称一组硬币，如果运气好的话只要称1次就可以找到，最多称8次就可以找出那枚硬币。这种直接寻找的方法存在着相当大的投机性。,二分治,2020年5月1日星期五,33,如果我们将一组硬币分成两小组，将原来设计的一次比较两枚硬币变为一次比较两组硬币，我们会发现通过一次比较后，完全可以舍弃全部是真币的一组硬币，选取与原有问题一致的另一半进行下一步的比较，这样问题的规模就明显缩小，而且每一次比较的规模都是成倍减少。,二分治,2020年5月1日星期五,34,根据以上分析，我们可以得到以下的结论：1、参与比较的硬币数量越多，使用该方法来实现就越快，而且投机性大大减少；2、解决方法关键在于能将大问题分割成若干小问题；3、小问题与原有问题是完全类似的。通常我们将这种大化小的设计策略称之为分治法，即“分而治之”的意思。,二分治,2020年5月1日星期五,35,定义分治法是将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。侧重点在于能各个击破。分治法在设计检索、分类算法或某些速算法中很有效的。最常用的分治法是二分法、归并法、快速分类法等。,二分治,2020年5月1日星期五,36,例1矩形分割平面上有一个大矩形，其左下角坐标（0，0），右上角坐标（R，R）。大矩形内部包含一些小矩形，小矩形都平行于坐标轴且互不重叠。所有矩形的顶点都是整点。要求画一根平行于y轴的直线x=k（k是整数），使得这些小矩形落在直线左边的面积必须大于等于落在右边的面积，且两边面积之差最小。并且，要使得大矩形在直线左边的的面积尽可能大。注意：若直线穿过一个小矩形，将会把它切成两个部分，分属左右两侧。,二分治,2020年5月1日星期五,37,输入格式第一行为一个整数r，表示大矩形的右上角坐标是（r，r）（1=r=1000000）。接下来的一行为一个整数n，表示一共有n个小矩形（0n=10000）。再接下来有n行，每行有4个整数l，t，w，h，表示有一个小矩形的左上角坐标是（l，t），宽度是w，高度是h（0=l，t=r）。输出格式仅一行为一个整数n，表示答案应该是直线x=n。如果必要的话，x=r也可以是答案。,二分治,2020年5月1日星期五,38,输入输出样例输入：输出：10005211215121,二分治,2020年5月1日星期五,39,算法分析二分查找。“二分查找”又称“折半查找”，是一种基于递归思想的查找方法，需要注意的是只有给定的数是递增（或递减）的，才可用二分查找，否则要先排序。对于排好序的线性表A有如下性质：比较x和A中任意一个元素i，若x=Ai，则x在A中的位置就是i；如果xAi，同理我们只要在Ai的后面查找x即可。无论是在Ai的前面还是后面查找x，其方法都和在A中查找x一样，只不过是线性表的规模缩小了。,二分治,2020年5月1日星期五,40,参考程序片断/二分查找：i=1;j=n;if(flag)printf(Yn);flag=false;elseprintf(Nn);while(ix)j=mid-1;elsei=mid+1;,二分治,2020年5月1日星期五,41,参考程序片断/矩形分割：f=0;t=2000000;t=0;while(f=f)elset=mid;t=f;break;if(ai.rightt)t=ai.right;printf(%dn,t);,二分治,2020年5月1日星期五,42,参考程序片断/矩形分割：longlongcheck(intx)s1+=(x-ai.left)*ai.high);longlongs1,s2;s2+=(ai.right-x)*ai.high);inti;s1=0;s2=0;for(i=1;i=x)s2+=(ai.right-ai.left)*ai.high);if(ai.leftx),二分治,2020年5月1日星期五,43,例2输出前K大的数问题描述给定一个数组，统计前k大的数并且把这k个数从大到小输出。输入格式第一行为一个整数n（n100000），表示数组的大小。第二行为n个整数，表示数组的元素，整数之间以一个空格分开。每个整数的绝对值不超过100000000。第三行为一个整数k（kn）。输出格式从大到小输出前k大的数，每个数一行。,二分治,2020年5月1日星期五,44,输入输出样例输入：输出：109456987123085765,二分治,2020年5月1日星期五,45,算法分析与设计排序。快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。,二分治,2020年5月1日星期五,46,算法分析与设计,二分治,2020年5月1日星期五,47,算法分析与设计快排思想：1、分解(Divide)：将输入的序列Ap.r划分成两个非空子序列Ap.q和Aq+1.r，使Ap.q中任一元素的值不大于Aq+1.r中任一元素的值。2、递归求解(Conquer)：通过递归调用快速排序算法分别对Ap.q和Aq+1.r进行排序。3、合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在Ap.q和Aq+1.r都排好序后不需要执行任何计算Ap.r就已排好序。,二分治,2020年5月1日星期五,48,参考程序片断/快排：voidqsort(intL,intR)while(iL)qsort(L,j);i=L;j=R;x=a(i+j)/2;dowhile(aix)doj-;if(i=j)tmp=ai;ai=aj;aj=tmp;i+;j-;,二分治,2020年5月1日星期五,49,参考程序片断/输出前K大的数：scanf(%d,二分治,2020年5月1日星期五,50,分治策略1、分解（Divide）：将原问题分成一系列子问题。2、解决（Conquer）：递归的解决各子问题。若子问题足够小，则可直接求解。3、合并（Combine）：将子问题的结果合并成原问题的解。,二分治,2020年5月1日星期五,51,二分治,2020年5月1日星期五,52,例3求排列的逆序对问题描述在Internet上的搜索引擎经常需要对信息进行比较，比如可以通过某个人对一些事物的排名来估计他（或她）对各种不同信息的兴趣，从而实现个性化的服务。对于不同的排名结果可以用逆序来评价它们之间的差异。考虑1，2，n的排列i1，i2，in，如果其中存在j，k，满足jik，那么就称（ij，ik）是这个排列的一个逆序。一个排列含有逆序的个数称为这个排列的逆序数。例如排列263451含有8个逆序(2，1)，(6，3)，(6，4)，(6，5)，(6，1)，(3，1)，(4，1)，(5，1)，因此该排列的逆序数就是8。显然，由1，2，n构成的所有n!个排列中，最小的逆序数是0，对应的排列就是1，2，n；最大的逆序数是n(n-1)/2，对应的排列就是n，(n-1)，2，1。逆序数越大的排列与原始排列的差异度就越大。现给定1，2，n的一个排列，求它的逆序数。,二分治,2020年5月1日星期五,53,输入格式第一行是一个整数n（n=100000），表示该排列有n个数。第二行是n个不同的正整数，之间以空格隔开，表示该排列。输出格式输出该排列的逆序数。输入输出样例输入：输出：68263451,二分治,2020年5月1日星期五,54,算法分析归并排序。归并就是将多个有序的数列合成一个有序的数列。将两个有序序列合并为一个有序序列叫二路归并。归并排序就是n长度为1的子序列，两两归并最后变为有序的序列。,二分治,2020年5月1日星期五,55,参考程序片断/归并排序：voidmerge(intL,intM,intR)intp1,p2,p3,i;p1=L;p2=M+1;p3=L;while(p1=M),二分治,2020年5月1日星期五,56,p3+;while(p1=M)bp3=ap1;p3+;p1+;while(p2=R)bp3=ap2;p3+;p2+;for(i=L;i=R;+i)ai=bi;,二分治,2020年5月1日星期五,57,参考程序片断/求排列的逆序对：voidmerge(intL,intM,intR);intp1,p2,p3,j;p1=L;p2=M+1;p3=L;while(p3R)|(ap1=tr+size)/残缺格在上部if(dc=tc+size)/残缺格在左部，将右下角设为阴影，填上三格板编号；boardtr+size-1,tc+size-1=title;/分别对四个小区域进行覆盖boardtr+size-1,tc+size=title;boardtr+size,tc+size-1=title;fugai(tr,tc,tr+size-1,tc+size-1,size);fugai(tr+size,tc,tr+size,tc+size-1,size);fugai(tr,tc+size,tr+size-1,tc+size,size);,二分治,2020年5月1日星期五,64,fugai(tr+size,tc+size,dr,dc,size);else/将左下角设为阴影，填上三格板编号；boardtr+size-1,tc+size-1=title;/分别对四个小区域进行覆盖boardtr+size-1,tc+size=title;boardtr+size,tc+size:=title;fugai(tr,tc,tr+size-1,tc+size-1,size);fugai(tr+size,tc,dr,dc,size);fugai(tr,tc+size,tr+size-1,tc+size,size);fugai(tr+size,tc+size,tr+size,tc+size,size);elseif(dc=tc+size)/残缺格在左部，将右上角设为阴影，填上三格板编号；boardtr+size-1,tc+size-1=title;/分别对四个小区域进行覆盖boardtr+size,tc+size-1=title;,二分治,2020年5月1日星期五,65,boardtr+size,tc+size=title;fugai(tr,tc,tr+size-1,tc+size-1,size);fugai(tr+size,tc,tr+size,tc+size-1,size);fugai(tr,tc+size,dr,dc,size);fugai(tr+size,tc+size,tr+size,tc+size,size);else/将左上角设为阴影，填上三格板编号；boardtr+size-1,tc+size=title;/分别对四个小区域进行覆盖boardtr+size,tc+size-1=title;boardtr+size,tc+size=title;fugai(tr,tc,dr,dc,size);fugai(tr+size,tc