递归在蛮力法中的应用教学课件

1、第4章 蛮力法4.3 递归在蛮力法中的应用吴粉侠蛮力法所依赖的基本技术是遍历技术，采用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解。而在遍历过程中，很多求解问题都可以采用递归方法来实现，如二叉树的遍历和图的遍历等。 前面介绍了两种采用蛮力法求解由1n整数构成的集合的幂集的方法，这里以解法2为基础。 同样采用vectorvector 容器ps存放幂集， 全局变量,初始时ps=。f(i,n,p) 输出幂集p当inf(i,n,p) 将整数i添加到p中原有每个子集中产生新子集;否则 并将所有新子集加入到p中; f(i+1,n,p);大问题：f(i，n)用于添加in整数（共需添加n-i

2、+1个整数）产生的幂集ps。小问题：f(1，n)就是生成1n的整数集合对应的幂集ps。vectorvector ps;/存放幂集存放幂集void Inserti(int i) /向幂集向幂集ps中每个集合元素添加中每个集合元素添加i并插入到并插入到ps中中 vectorvector ps1;/子幂集子幂集 vectorvector :iterator it;/幂集迭代器幂集迭代器 ps1=ps;/ps1存放原来的幂集存放原来的幂集 for (it=ps1.begin();it!=ps1.end();+it) (*it).push_back(i);/在在ps1的每个集合元素末尾添加的每个集合元素

3、末尾添加i for (it=ps1.begin();it!=ps1.end();+it) ps.push_back(*it);/将将ps1的每个集合元素添加到的每个集合元素添加到ps中中void PSet(int i,int n) /求求1n的幂集的幂集ps if (i=n) Inserti(i); /将将i插入到现有子集中产生新子集插入到现有子集中产生新子集PSet(i+1,n); /递归调用递归调用 同样采用vectorvector 容器ps存放全排列，并作为全局变量。首先初始化ps=1。 大问题：f(i，n)用于添加in整数（共需添加n-i+1个整数）产生的全排列ps。显然f(2，n)就

4、是生成1n的整数集合对应的全排列ps。 小问题：f(i+1，n)用于添加i+1n整数（共需添加n-i个整数）产生的全排列。f(i，n) 产生全排序ps当in时f(i，n) 置ps为1，取出ps的每个集合元素s， 在s的每个位置插入i;否则 将插入i后的新集合元素添加的ps1中; 置ps=ps1; f(i+1，n);vectorvector ps;/存放全排列存放全排列/在每个集合元素中间插入在每个集合元素中间插入i得到得到ps1void Insert(vector s,int i,vectorvector &ps1) vector s1; vector:iterator it; for

5、 (int j=0;ji;j+)/在在s(含含i-1个整数个整数)的每个位置插入的每个位置插入i s1=s;it=s1.begin()+j;/求出插入位置求出插入位置s1.insert(it,i);/插入整数插入整数ips1.push_back(s1);/添加到添加到ps1中中 void Perm(int i,int n) /求求1n的全排列的全排列ps vectorvector :iterator it; /全排列迭代器全排列迭代器 if (i=n) vectorvector ps1; /临时存放子排列临时存放子排列 for (it=ps.begin();it!=ps.end();+it)

6、Insert(*it,i,ps1); /在每个集合元素中间插入在每个集合元素中间插入i得到得到ps1 ps=ps1; Perm(i+1,n); /继续添加整数继续添加整数i+1 第4章 蛮力法4.3 递归在蛮力法中的应用吴粉侠 【问题描述】求1n的正整数中取k（kn）个不重复整数的所有组合。n=3 1,2,3k=21,2 1,3 2,3n=51,2,3,4,5k=3？n=51, 2, 3, 4, 5k=3a0.2a2a2=3a2=4a2=5a1=2a0=11,2,3a1=3a1=2a0=2a0=12,3,41,3,4a0=11,2,4a1=4a1=2a1=3a0=3a0=1a0=2a0=1a0

7、=23,4,52,4,51,4,5a0=12,3,51,3,51,2,5【】用数组元素a0.k-1来保存一个组合，由于一个组合中所有元素不会重复出现，规定a中所有元素按递增排列。 大问题：f(n,k)从1n中任取k个数的所有组合。 小问题：f(m,k-1)从1m中任取k-1个数的所有组合。 因为a中元素递增排列，所以ak-1的取值范围只能为kn，当ak-1确定为i后，合并f(i-1,k-1)的一个结果便构成f(n,k)的一个组合结果。f(n,k)a0ak-2ak-1=if(i-1,k-1)ak-1即i只能取kn值对应的递归模型如下：f(n，k) 输出a中的一种组合当k=0f(n，k) i取值从

8、k到n:当k0 ak-1=i; f(i-1，k-1)f(n,k)a0ak-2ak-1=if(i-1,k-1)ak-1即i只能取kn值求15中取3个整数组合的过程如下所示（a0.2放一个组合）a2取35值k=3,考虑a2k=2,考虑a1k=1,考虑a0a1=2a0=1得到123a1=2a0=1a1=3a1=4得到125a0=1得到135a0=2得到235a0=1得到145a0=2得到245a0=3得到345a2=3a2=4a2=5a1=2a1=3a0=1得到124a0=1得到134a0=2得到234void dispacomb()/输出一个组合或存放一个组合 for (int i=k;i=n;i

9、+) coutait;/ak-1位置取kn的整数 coutendl;void comb(int n,int k)/求1.n中k个整数的组合 if (k=0) /k为0时输出一个组合 dispacomb(); else for (int i=k;i=n;i+) ak-1=i; /ak-1位置取kn的整数 comb(i-1,k-1); 【算法分析】设T(n,k)表示求1n中k个数的全部组合，对应的递推式如下：可以推导出T(n)=O(n)，这是最好的情况，即每次划分的基准恰好是中位数，将一个序列划分为长度大致相等的两个子序列。在最坏情况下，每次划分的基准恰好是序列中的最大值或最小值，则处理区间只比上一次减少1个元素，此时比较次数为O(n2)。在平均情况下