递归与分治策略ppt课件.ppt

《递归与分治策略ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、递归与分治策略12递归一个直接或间接地调用自身的算法称为递归算法。一个使用函数自身给出定义的函数称为递归函数。递归使到函数的定义和算法的描述简捷且易于理解。3例阶乘函数边界条件递归方程4边界条件与递归方程是递归函数的二个要素递归函数只有具备了这两个要素，才能在有限次计算后得出结果。5intFactorial(intn){if(n==0)return1;returnn*Factorial(n–1);}6例Hanoi塔问题设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到

2、小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。7在移动圆盘时应遵守以下移动规则：规则1：每次只能移动1个圆盘；规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。8在问题规模较大时，较难找到一般的方法，因此我们尝试用递归技术来解决这个问题。当n=1时，问题比较简单。此时，只要将编号为1的圆盘从塔座a直接移至塔座b上即可。当n＞1时，需要利用塔座c作为辅助塔座。

3、此时若能设法将n-1个较小的圆盘依照移动规则从塔座a移至塔座c，然后，将剩下的最大圆盘从塔座a移至塔座b，最后，再设法将n-1个较小的圆盘依照移动规则从塔座c移至塔座b。由此可见，n个圆盘的移动问题可分为2次n-1个圆盘的移动问题，这又可以递归地用上述方法来做。由此可以设计出解Hanoi塔问题的递归算法如下。递归解法voidhanoi(intn,inta,intb,intc){if(n>0){hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);}}9例整数划分问题将

4、正整数n表示成一系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。10例如正整数6有如下11种不同的划分：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。11递推关系式q(n,m):正整数n的所有不同划分中,最大加数n1不大于m的划分个数12intq(intn,intm){if((n<1)

5、

6、(m<1))return0

7、;if((n==1)

8、

9、(m==1))return1;if(n

10、，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1是同一种分法。Input第一行是测试数据的数目t（0<=t<=20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。Output对输入的每组数据M和N，用一行输出相应的K。SampleInput173SampleOutput832233142151143052061070017例：排列问题设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。设R={r1,r2,…,rn}是要进行排列的n个元素，

11、Ri=R-{ri}。集合X中元素的全排列记为perm(X)。(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀ri得到的排列。18R的全排列可归纳定义如下：当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素；当n>1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)构成。19voidpermute(intt,intn,intx[]){if(t>n)output(n,x);else{for(inti=t;i<=n;i++)

12、{swap(x[t],x[i]);permute(t+1,n,x);swap(x[t],x[i]);}}}Divide-and-Conquer分治策略将问题的实例划分为同一个问题的几个较小的实例，最好拥有同样的规模对这些较小的实例求解（一般使用递归方法）如果必要的话，合并这些较小问题的解，以得到原始问题的解2122由分治法产生的子问题往往是原问题的较小模式在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很