西安专业网站建设价格,高防手表网站,app 软件开发公司,wordpress菜单 自定义菜单目录#xff1a; 7.1 简单枚举7.2 枚举排列7.3 子集生成 7.1 简单枚举
例题7-1 除法#xff08;Division, UVa 725#xff09; 输入正整数n#xff0c;按从小到大的顺序输出所有形如abcde/fghij n的表达式#xff0c;其中a#xff5e;j恰好 为数字0#xff5e…目录 7.1 简单枚举7.2 枚举排列7.3 子集生成 7.1 简单枚举
例题7-1 除法Division, UVa 725 输入正整数n按从小到大的顺序输出所有形如abcde/fghij n的表达式其中aj恰好 为数字09的一个排列可以有前导02≤n≤79。 样例输入 62 样例输出 79546 / 01283 62 94736 / 01528 62
#includeiostream
using namespace std;int pjj(int m , int n){int k0;int a[10]{0};while(m){a[k]m%10;mm/10;}while(n){a[k]n%10;nn/10;} for(int i0;i10;i)for(int ji1;j10;j)if(a[i]a[j]) return -1;return 1;
}int main(){int n,k,i;cinn;for(i1234;i*n98765;i){ki*n;if(pjj(i,k)1) {cout k / ; if(i 10000) cout 0; cout i n endl;}}
}
分析只需要枚举fghij就可以算出abcde然后判断是否 所有数字都不相同即可
例题7-2 最大乘积Maximum Product, UVa 11059 输入n个元素组成的序列S你需要找出一个乘积最大的连续子序列。如果这个最大的乘 积不是正数应输出0表示无解。1≤n≤18-10≤Si≤10。 样例输入 3 2 4-3 5 2 5 -1 2 -1 样例输出 8 20
#includeiostream
using namespace std;
int main(){int n;int a[100];while(cinn){long long maxm-100,tmp;int i,j;for(i0;in;i){cina[i];} for(i0;in;i){tmp1;for(ji;jn;j){tmp*a[j];if(maxmtmp){maxmtmp;}}}if(maxm0) cout0endl;else coutmaxmendl;}}
分析连续子序列有两个要素起点和终点因此只需枚举起点和终点即可其中起点为i终点为j。
例题7-3 分数拆分Fractions Again?!, UVa 10976 输入正整数k找到所有的正整数x≥y使得 1/k1/x1/y 样例输入 2 12 样例输出 2 1/2 1/6 1/3 1/2 1/4 1/4 8 1/12 1/156 1/13 1/12 1/84 1/14 1/12 1/60 1/15 1/12 1/48 1/16 1/12 1/36 1/18 1/12 1/30 1/20 1/12 1/28 1/21 1/12 1/24 1/24
#includeiostream
using namespace std;
int main(){double k,x;int i,sum;while(cink){sum0;for(ik1;i2*k;i){xi*k/(i-k);if(x(int)x)sum;}coutsumendl;for(ik1;i2*k;i){xi*k/(i-k);if(x(int)x)cout1/k1/x1/iendl;}}}
分析 既然要求找出所有的x、y枚举对象自然就是x、y了。可问题在于枚举的范围如何 从1/121/1561/13可以看出x可以比y大很多。难道要无休止地枚举下去当然不是。由 于x≥y有 1/k1/y1/y因此 即y≤2k。这样只需要在2k范围之内枚举y然后根据y尝试 计算出x即可
7.2 枚举排列
例7-2-1输入整数n按字典序从小到大的顺序输出前n个数的 所有排列。 分析两个序列的字典序大小关系等价于从头开始第一个不相同位置处的大 小关系。例如(1,3,2) (2,1,3)字典序最小的排列是(1, 2, 3, 4,…, n)最大的排列是(n, n-1, n-2,…, 1)。n3时所有排列的排序结果是(1, 2, 3)、(1, 3, 2)、(2, 1, 3)、(2, 3, 1)、(3, 1, 2)、 (3, 2, 1)。 以1开头的排列的特点是第一位是1后面是29的排列。根据字典序的定义这些2 9的排列也必须按照字典序排列。换句话说需要“按照字典序输出29的排列”不过需 注意的是在输出时每个排列的最前面要加上“1”。这样一来所设计的递归函数需要以 下参数 1.已经确定的“前缀”序列以便输出。 2.需要进行全排列的元素集合以便依次选做第一个元素
void print_permutation(序列A, 集合S)
{ if(S为空) 输出序列A; else 按照从小到大的顺序依次考虑S的每个元素v { print_permutation(在A的末尾填加v后得到的新序列, S-{v}); }
}
下面考虑程序实现。不难想到用数组表示序列A而集合S根本不用保存因为它可以 由序列A完全确定——A中没有出现的元素都可以选。C语言中的函数在接受数组参数时无法 得知数组的元素个数所以需要传一个已经填好的位置个数或者当前需要确定的元素位置 cur代码如下
#includeiostream
#includecstdio
using namespace std;
int a[1000];
void print_permutation(int n,int *a,int cur);
int main(){int n;cinn;print_permutation( n, a, 0);
}void print_permutation(int n,int *a,int cur){if(curn) {for(int i0;in;i) printf(%d ,a[i]);printf(\n) ;}else{for(int i1;in;i){//改变前缀int ok 1;for(int j0;jcur;j){//如果i已经在A[0]~A[cur-1]出现过则不能再选if(a[j]i) ok 0;}if(ok){a[cur]i;print_permutation( n, a, cur 1);//每一个前缀的可能排序}}}
} 递归边界是S为空 的情形这很好理解现在序列A就是一个完整的排列直接输出即可。接下来按照从小到大的顺序考虑S中的每个元素每次递归调用以A开头. 循环变量i是当前考察的A[cur]。为了检查元素i是否已经用过上面的程序用到了一个 标志变量ok初始值为1真如果发现有某个A[j]i时则改为0假。如果最终ok仍 为1则说明i没有在序列中出现过把它添加到序列末尾A[cur]i后递归调用。
例7-2-2生成可重集的排列
如果把问题改成输入数组P并按字典序输出数组A各元素的所有全排列则需要对 上述程序进行修改——把P加到print_permutation的参数列表中然后把代码中的if(A[j] i) 和A[cur] i分别改成if(A[j] P[i])和A[cur] P[i]。这样只要把P的所有元素按从小到大的顺序排序然后调用print_permutation(n, P, A, 0)即可如下面代码所示。
#includeiostream
#includecstdio
#includealgorithm
using namespace std;
int a[1000];int p[1000];
void print_permutation(int *p,int n,int *a,int cur);
int main(){int n,i;cinn;for(i0;in;i){cinp[i];}sort(p,pn);print_permutation(p, n, a, 0);
}void print_permutation(int *p,int n,int *a,int cur){int i;if(curn) {for(int i0;in;i) printf(%d ,a[i]);printf(\n) ;}else{for(int i0;in;i){//改变前缀int ok 1;for(int j0;jcur;j){//如果i已经在A[0]~A[cur-1]出现过则不能再选if(a[j]p[i]) ok 0;}if(ok){a[cur]p[i];print_permutation( p, n, a, cur 1);//每一个前缀的可能排序}}}
}
这个方法看上去不错可惜有一个小问题输入1 1 1后程序什么也不输出正确答案 应该是唯一的全排列1 1 1原因在于这样禁止A数组中出现重复而在P中本来就有重 复元素时这个“禁令”是错误的。 一个解决方法是统计A[0]A[cur-1]中P[i]的出现次数c1以及P数组中P[i]的出现次数 c2。只要c1 c2就能递归调用
结果又如何呢输入1 1 1输出了27个1 1 1。遗漏没有了但是出现了重复先试着把 第1个1作为开头递归调用结束后再尝试用第2个1作为开头递归调用结束后再尝试用第3 个1作为开头再一次递归调用。可实际上这3个1是相同的应只递归1次而不是3次。
换句话说我们枚举的下标i应不重复、不遗漏地取遍所有P[i]值。由于P数组已经排过 序所以只需检查P的第一个元素和所有“与前一个元素不相同”的元素即只需在“for(i 0; i n; i)”和其后的花括号之前加上“if(!i || P[i] ! P[i-1])”即可。
#includeiostream
#includecstdio
#includealgorithm
using namespace std;
int a[1000];int p[1000];
void print_permutation(int *p,int n,int *a,int cur);
int main(){int n,i;cinn;for(i0;in;i){cinp[i];}sort(p,pn);print_permutation(p, n, a, 0);
}void print_permutation(int *p,int n,int *a,int cur){int i;if(curn) {for(int i0;in;i) printf(%d ,a[i]);printf(\n) ;}else for(int i 0; i n; i) { if(!i || p[i] ! p[i-1]){int c1 0,c2 0; for(int j 0; j cur; j) if(a[j] p[i]) c1; for(int j 0; j n; j) if(p[i] p[j]) c2; if(c1 c2) { a[cur] p[i]; print_permutation(p,n, a, cur1); } }}}
总结 如果某问题的解可以由多个步骤得到而每个步骤都有若干种选择这些候 选方案集可能会依赖于先前作出的选择且可以用递归枚举法实现则它的工作方式可以 用解答树来描述。
例7-2-3利用next_permutation解答 枚举所有排列的另一个方法是从字典序最小排列开始不停调用“求下一个排列”的过 程。如何求下一个排列呢C的STL中提供了一个库函数next_permutation
#includecstdio
#includealgorithm //包含next_permutation
using namespace std;
int main( ) { int n, p[10]; scanf(%d, n); for(int i 0; i n; i) scanf(%d, p[i]); sort(p, pn); //排序得到p的最小排列 do { for(int i 0; i n; i){printf(%d , p[i]); //输出排列p}printf(\n); } while(next_permutation(p, pn)); //求下一个排列 return 0;
}
上述代码同样适用于可重集。 总结枚举排列的常见方法有两种一是递归枚举二是用STL中的 next_permutation
7.3 子集生成
