C++递归和回溯.ppt

递归 递归定义 f(n)=g(n,f(n-1)) n0 f(0)=a n=0 未知函数f，用其自身构成的已知函数g 来定义，则称f为递归函数。 其中f(0)=a,称为递归边界，也就是递归 终结的条件。这是递归定义中必不可少的部 分。 递归算法适用的三种场合： 1、数据的定义形式是递归，如fibonacci数列的问题 2、数据之间的逻辑关系是递归，如树，图等的定义和操作 3、某些问题的解法是不断重复执行一种操作并且期问题规模由大 变小，直至某个原操作结束。如汉诺塔问题。 简单的递归 1、计算阶乘之和n!+(n-1)!+...+1! #includeiostream using namespace std; long fact(int n) { if(n==1) return 1;//边界 else return n*fact(n-1); // 递规调用式 } 递归调用过程 若n=5,调用fact(5) (1) fact(5)=5*fact(4) (2) fact(4)=4*fact(3) (3) fact(3)=3*fact(2) (4) fact(2)=2*fact(1) (5) fact(1)=1 然后返回fact(1)的值到 fact(2)中则： (6)fact(2)=2*1=2 (7)fact(3)=3*2=6 (8)fact(4)=4*6=24 (9)fact(5)=5*24=120 简单的递归 2、斐波那契函数: 问题是指某人有一对兔子饲养在围墙中，如果它们每个月生一对兔子，且新生的兔子在第二个月后也是每个月生一对兔子，问一年后围墙中共有多少对兔子。 #includeiostream using namespace std; long f(int n) { if(n==1||n==2) return 1;//边界 else return f(n-1)+f(n-2); // 递规调用式 } 简单的递归 3、求两个正整数m,n(mn)的最大公约数 #includeiostream using namespace std; long gcd(int m,int n) { if(n%m==0) return m;//边界 else return gcd(n%m,m); // 递规调用式 } 递归的应用 1、集合的划分 【问题描述】 设s是一个具有n个元素的集合，s={a1,a2,…an},现将s划分成k个满足下列条件的子集合s1,s2,…sk且满足： （1）si不为空集 （2）si与sj相交为空 （3）s1,s2,s3…sk并起来刚好为集合s 递归的应用 【问题分析】对于任意的含有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必与其他元素构成一个子集，则问题就变成把a1,a2,… an-1划分成k个子集；然后再把元素an放入到其中任一个子集中则有k×s(n-1,k)种情况 递归关系式就为：s(n,k)=s(n-1,k-1)+k*s(n-1,k) 那么边界条件是什么？ (1) 如果没有空盒子，则n个元素不能放入任意一个集合中，即k=0时，s(n,k)=0 (2)如果空盒子过多，将n个元素放入多于n的k个集合中也不行，即kn时，s(n,k)=0 (3)如果k=1或者k=n,也就是将n个元素放入一个集合或者将n个元素放入n个集合，那么方案数只能为1，即k=1或者k=n时，s(n,k)=1 递归的应用 递归关系式： S(n,k)=s(n-1,k-1)+k*s(n-1,k) (nk,k0) S(n,k)=0 (nk||k=0) S(n,k)=1 (k=1||n=k) #includeiostream using namespace std; long s(int n,int k) { if(nk||k=0) return 0;//边界 else if (k==1||k==