第2章-递归与分治策略

第2章递归与分治策略2020/3/4算法设计与分析2第2章递归与分治策略学习要点•理解递归的概念•掌握设计有效算法的分治策略：分治法的基本思想•通过范例学习分治策略的算法分析及设计技巧–二分搜索技术–大整数的乘法–Strassen矩阵乘法–棋盘覆盖–合并排序和快速排序–线性时间选择2020/3/4算法设计与分析32.1递归的概念问题1：什么是递归?•直接或间接地调用自身的算法称为递归算法，用函数自身给出定义的函数称为递归函数。•举例：输出n个自然数。Print_1(intn){inti;for(i=1;i=n;i++)printf(“%d”,i);printf(“\n”);return;}非递归算法Print_2(intn){if(n==0)return;else{Print_2(n-1);printf(“%d”,n);}return;}递归算法结论：在计算机算法设计中，使用递归技术往往使函数的定义和算法的描述简洁且易于理解。2020/3/4算法设计与分析4补充：归纳法的思想方法•基础步：a1是问题P(1)的解；•归纳步：对所有的k,1kn，如果bk是问题P(k)的解，则P(bk)是问题k+1的解。其中，P(bk)是对bk的某种运算或处理。举例：a1是问题P(1)的解，如果a2=P(a1)，则a2是问题P(2)的解…，依此类推，若an-1是问题P(n-1)的解，且an=P(an-1)，则an是问题P(n)的解。2020/3/4算法设计与分析5分析•为求问题P(n)的解an，先求问题P(n-1)的解an-1，再对an-1进行P运算或处理；为求问题P(n-1)的解an-1，先求问题P(n-2)的解an-2，再对an-2进行P运算或处理……•如此等等，不断地进行递归求解，直到P(1)为止。•当得到P(1)的解之后，再回过头来，不断地把所得到的解进行P运算或处理，直到得到P(n)的解为止。))1(()(nPPnP)))2(((nPPP))))1((((PPPPn次P处理2020/3/4算法设计与分析6举例2-1：阶乘函数•可递归定义为：•其中：•n=0时，n!=1为边界条件（基础步）•n0时，n!=n(n-1)!为递归方程（归纳步）0)!1(01!nnnnn说明：边界条件与递归方程是递归函数的两个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。2020/3/4算法设计与分析7举例2-2：Fibonacci数列•无穷数列1,1,2,3,5,8,13,21,34,55,…，被称为Fibonacci数列。•它可以递归定义为：1211101nnFnFnnnF边界条件递归方程intFibonacci(intn){if(n=1)return1;returnFibonacci(n-1)+Fibonacci(n-2);}2020/3/4算法设计与分析8分析•以上两例中的函数也可以用如下非递归方式定义：•但是并非所有递归函数都能用非递归方式定义，例如Ackerman函数就不能用非递归方式定义。n×1)-(n×…×3×2×1=n!1125125151)(nnnF2020/3/4算法设计与分析9举例2-3：Ackerman函数•当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。•Ackerman函数A(n,m)定义如下，n,m是两个独立的整变量，其中n,m均≥0：1,1,,1,220,01,020,1mnmmnAAmnAnnnAmmAAAckerman函数无法找到非递归的定义。2020/3/4算法设计与分析10分析•A(n,m)的自变量m的每一个值都定义了一个单变量函数：•m=0时，A(n,0)=n+2。•m=1时，A(n,1)=2n。•m=2时，A(n,2)=2n。•m=3时，类似的可以推出•m=4时，A(n,4)的增长速度非常快，以至于没有合适的数学式子来表示这一函数。n2...222020/3/4算法设计与分析11longintack(intn,intm){if(n0||m0){printf(\nthecondictionofcalculatingisnotexit!\n);exit(0);}else{if(n==1&&m==0)return2;elseif(n==0&&m=0)return1;elseif(n=2&&m==0)return(n+2);elseif(n=1&&m=1)return(ack(ack(n-1,m),m-1));}}2020/3/4算法设计与分析12分析•定义单变量的Ackerman函数A(n)为：A(n)=A(n,n)。•定义其拟逆函数α(n)为：α(n)=min{k|A(k)≥n}，即α(n)是使n≤A(k)成立的最小的k值。•α(n)在复杂度分析中常遇到。对于通常所见到的正整数n，有α(n)≤4，因为A(4)太大了。可以看出α(n)增长速度很慢。在理论上α(n)没有上界，随着n的增加，它以难以想象的慢速度趋向正无穷大。2020/3/4算法设计与分析13举例2-4：排列问题•排列问题：设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。•问题分析：一个n个数的排列可以由n-1个数的排列生成，只要先生成第n-1个数再插入第n个数就可以了。•举例：X={a,b,c}2020/3/4算法设计与分析14•设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}。•集合X中元素的全排列记为perm(X)。•(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。R的全排列可归纳定义如下：–当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素；–当n1时，perm(R)由(r1)perm(R1),(r2)perm(R2),…,(rn)perm(Rn)构成。2020/3/4算法设计与分析15求长度为n的数组元素全排列•存放于数组A的n个元素，生成其全排列：1.第一个元素不动，生成后面n-1个元素的排列；2.第一、第二个元素互换，生成后面n-1个元素的排列；3.最后，第一个、第n个元素互换，生成后面n-1个元素的排列。2020/3/4算法设计与分析16•为生成后面n-1个元素的排列，继续采取下面的步骤：1.第二个元素不动，生成后面n-2个元素的排列；2.第二、第三个元素互换，生成后面n-2个元素的排列；3.最后，第二个、第n个元素互换，生成后面n-2个元素的排列；•当排列的前n-2个元素已确定后，为生成后面2个元素的排列，可以：1.第n-1个元素不动，生成后面1个元素的排列，此时，n个元素已构成排列；2.第n-1、第n个元素互换，生成后面1个元素的排列，此时，n个元素已构成排列。2020/3/4算法设计与分析17voidperm(intlist[],intk,intm)//产生list[k:m]的所有排列{//m为list数组下标的最大值，而k则表示position，初始值为0inti;if(k==m)//单元素排列，则排列工作结束，输出元素序列{for(i=0;i=m;i++)printf(“%4d”,list[i]);printf(“\n”);}else//多元素序列，递归产生排列{for(i=k;i=m;i++){swap(list[k],list[i]);//使list[k]始终为提取出来的ri，通过交换，使得每个元素都能够成为前缀perm(list,k+1,m);//递归调用，得到作为前缀的元素的所有排列swap(list[k],list[i]);}}}基础步归纳步2020/3/4算法设计与分析18说明•算法perm(list,k,m)递归产生所有的前缀list[0:k-1]，且后缀是list[k:m]的全排列的所有排列，函数调用perm(list,0,n-1)则产生list[0:n-1]的全排列。•一般情况下，km，算法将list[k:m]中的每个元素与list[k]中的元素交换，然后递归计算list[k+1:m]的全排列，并将计算结果作为list[0:k]的后缀。2020/3/4算法设计与分析19举例2-5：整数划分问题•问题定义：将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1,k≥1，正整数n的这种表示称为正整数n的划分，求正整数n的不同划分个数。•举例：6；5+1；4+2，4+1+1；3+3，3+2+1，3+1+1+1；2+2+2，2+2+1+1，2+1+1+1+1；1+1+1+1+1+1。正整数6的11种划分分析：前面的几个例子中，问题本身都具有比较明显的递归关系，因而可以用递归函数直接求解。在本例中，如果设p(n)为正整数n的划分个数，则难以找到递归关系。2020/3/4算法设计与分析20分析•遇到的难题：如果设p(n)为正整数n的划分个数，则难以找到递归关系。•解决办法：考虑增加一个自变量：将最大加数n1（即第一个加数）不大于m（即n1≤m）的划分个数记作q(n,m)。•可以建立q(n,m)的如下递归关系：2020/3/4算法设计与分析21整数划分问题中q(n,m)的递归关系•q(n,1)=1,n≥1；m=1•q(n,m)=q(n,n),m≥n•q(n,n)=1+q(n,n-1),m=n•q(n,m)=q(n,m-1)+q(n-m,m),nm11,1,1,1,1,11,mnmmnqmnqmnnnqmnnnqmnmnq2020/3/4算法设计与分析22说明•正整数n的划分数p(n)=q(n,n)。•注意：正整数划分的数目随着n的增加增长的非常快（指数级增长），所以不要用较大的整数来测试用该算法编写的程序。1,1,1,1,1,11,mnmmnqmnqmnnnqmnnnqmnmnq2020/3/4算法设计与分析23intSplitq(intn,intm){if((n1)||(m1))return0;/*此时没有划分数*/if((n==1)||(m==1))return1;/*n=1时只能有一种表示，即1=1*//*m=1时也只有一种表示，n=1+1+……+1*/if(nm)returnSplitq(n,n);/*当mn时，由于m不能大于n，否则就会有负数出现了，因此只能表示成最大加数不大于n的划分*/if(n==m)returnSplitq(n,m-1)+1;/*当m==n时，首先可以有一种表示:n=m，其余的就表示成最大加数不大于m-1的划分*/returnSplitq(n,m-1)+Splitq(n-m,m);/*一个数的最大加数为m的划分可以表示为两部分*/}2020/3/4算法设计与分析24举例2-6：Hanoi塔问题•问题定义：设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。•在移动圆盘时应遵守以下移动规则：（1）每次只能移动1个圆盘；（2）任何时刻都不允许将较大的圆盘压在较小的圆盘之上；（3）在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。2020/3/4算法设计与分析25塔座a塔座b塔座c321特例：三阶Hanoi塔问题•分析：起始塔座a上有三个圆盘，所以该问题被称为三阶Hanoi塔问题。需要完成：Hanoi(3,a,c,b)；其中，参数1表示一共需要移动几个圆盘；参数2表示起始塔座；参数3表示中间塔座；参数4表示目的塔座。2020/3/4算法设计与分析26分析•简单解法：将A、B、C、A构成一个顺时针循环。在移动盘子的过程中，若是奇数次移动，则将