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! 递规定义式： f(n)=n*f(n-1) n1; f(1)=1 n=1 #include using namespace std; long fact(int n) { if(n==1) return 1;//边界 else return n*fact(n- 1); // 递规调用式 } int main() { int n,i; long s=0; cinn; for(i=1;i2 f(1)=f(2)=1 #include using namespace std; long f(int n) { if(n==1||n==2) return 1;//边界 else return f(n-1)+f(n- 2); // 递规调用式 } int main() { long n; cinn; coutf(n);//调用函数 return 0; } 简单的递归 3、求两个正整数m,n(mmn; coutgcd(m,n);//调用函数 return 0; } 递归的应用 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 (n0) //若还有直线存在，则递归计算所有交叉情况 for(int r=m ;r=1;r--) try(m-r,j+r*(m-r)); else g[j]=1;//确定m条直线存在j个交点 } 其中：数组g[1max]，g[i]=0表示交点数i不存在，而max=n(n-1)/2 int main() { int max,n,i,total=0; cinn; max=n*(n-1)/2; try(n,0);//递归求g[i]是否存在 for(i=0;i0 f(a,b)=f(a-1,b) a0,b=0 f(a,b)=f(a,b-1) a=0 边界值f(0,0)=1 。