递归和递推课件.ppt

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

1、递归和递推陈旭龙函数定义递归的概念一个函数、过程、概念或数据结构，如果在其定义或说明内部直接或间接地出现有其本身的引用，或者是为了描述问题的某一状态，必须用到它的上一状态，而描述上一状态，又必须用到它的上一状态……这种用自己来定义的方法，称之为递归或者递归定义。在程序设计中，过程或函数直接或者间接调用自己，就称为递归调用递归过程实际上借助于一个递归工作栈来实现的。首先问题向一个方向一步一步分解，既问题规模逐渐降低，这样，问题向一极推进的过程称之为递归过程；然后这些问题又按后提出先解决的顺序依次得到解决，最后得到原问题的解。这样，在子问题得到逐一解决的基础上，最后回到原问

2、题的解的变化过程，称之为回归过程。递归定义的要素1、递归边界或终止条件。2、递归定义，使问题向边界条件转化的规则。varn:integer;functionfibonacci(x:integer):integer;beginif(x=0)or(x=1)thenexit(1);exit(fibonacci(x-1)+fibonacci(x-2));end;beginreadln(n);writeln(fibonacci(n));end.递归函数的应用P1294走楼梯P1024数字的根递归的应用分析P1293移梵塔P1750分形P1752红与黑集合的划分设ｓ是一个具有n个元

3、素的集合，ｓ＝｛a1，a2，……，an｝，现将ｓ划分成K个满足下列条件的子集合s1，s2，……，sk，且满足：1．si≠φ2．si∩sj＝φ(1≤i，j≤ki≠j)3．s1∪s2∪s3∪…∪sk＝ｓ则称s1，s2，……，sk是集合ｓ的一个划分。它相当于把ｓ集合中的n个元素a1，a2，……，an放入k个（0

4、∪｛4｝｛1，3｝∪｛2｝∪｛4｝｛1，4｝∪｛2｝∪｛3｝｛2，3｝∪｛1｝∪｛4｝｛2，4｝∪｛1｝∪｛3｝｛3，4｝∪｛1｝∪｛2｝考虑一般情况，对于任意的含有n个元素a1，a2，……，an的集合s，放入k个无标号的盒子中去，划分数为s(n，k)，我们很难凭直觉和经验计算划分数和枚举划分的所有方案，必须归纳出问题的本质。下面考虑对任一个元素an，则必然出现以下两种情况：1、｛an｝是k个子集中的一个，于是我们只要把a1，a2，……，an-1划分为k－1子集，便解决了本题，这种情况下的划分数共有s(n－1，k－1)个；2、｛an｝不是k个子集中的一个，则an必与其它

5、的元素构成一个子集。则问题相当于先把a1，a2，……，an-1划分成k个子集，这种情况下划分数共有ｓ(n－1，k)个；然后再把元素an加入到k个子集中的任一个中去，共有k种加入方式，这样对于an的每一种加入方式，都可以使集合划分为k个子集，因此根据乘法原理，划分数共有k*ｓ(n－1，k)个。综合上述两种情况，应用加法原理，得出n个元素的集合｛a1，a2，……，an｝划分为k个子集的划分数为以下递归公式：ｓ(n，k)＝ｓ(n－1，k－1)+k*s(n－1，k)(n>k，k>0)。确定s(n，k)的边界条件首先不能把n个元素不放进任何一个集合中去，即k=0时，ｓ(n，k)＝

6、0；也不可能在不允许空盒的情况下把n个元素放进多于n的k个集合中去，即k＞n时,ｓ(n，k)＝0；再者，把n个元素放进一个集合或把n个元素放进n个集合，方案数显然都是1，即k=1或k=n时，s(n,k)=1。可以得出划分数ｓ(n，k)的递归关系式为：s(n，k)＝s(n－1，k－1)+k*s(n－1，k)(n>k，k>0)s(n，k)＝0(n

7、干件，使得放入背包的重量之和正好为S。样例输入：10516275样例输出：Truevars,n,i:integer;a:array[1..100]ofinteger;functionpackge(s,n:integer):boolean;beginif(n=1)and(s<>a[n])thenexit(false);｛边界｝ifs=a[n]thenexit(true);ifa[n]>sthenexit(packge(s,n-1));ifs>a[n]thenbeginifpackge(s-a[n],n-1)thenexit(true)els