首页 > 代码库 > 枚举法
枚举法
(⊙o⊙)，今天和爸妈一起买电视机去了，很interesting，早上看的东西应该还没忘掉 (＾－＾)V
枚举集合：
一般都用的二进制思想，& | ^ 就分别对应的是 交，并，对称差。枚举每一个子集，就是一个简单的循环变量 i ，而 i 怎么提取每一个元素，就是 s & (1<<i) ，循环遍历。
1 /* 2 集合的枚举 3 */ 4 5 #include <bits/stdc++.h> 6 7 using namespace std; 8 9 int cnt = 0;10 11 void print_subset(int n,int s) // s 为 枚举的集合，n 为 总集合个数12 {13 for(int i=0;i<n;i++) {14 if(s&(1<<i)) printf("%d ",i);15 }16 puts("");17 cnt++;18 }19 20 int main()21 {22 23 int n = 5;24 for(int i=0;i<(1<<n);i++) {25 print_subset(n,i);26 }27 28 printf("***%d\n",cnt);29 30 return 0;31 }
枚举排列：
这个还是挺有代表性的，单纯的枚举排列完全可以用库函数，其思想还是有很大的作用的，就是一个解答树的概念，从当前的一个状态转到下一个状态的一个递归写法。
1 /* 2 1~n 的排列枚举 3 */ 4 5 #include <bits/stdc++.h> 6 7 using namespace std; 8 9 void print_permutation(int n,int *A,int cur) {10 if(cur==n) {11 for(int i=0;i<n;i++)12 printf("%d ",A[i]);13 puts("");14 }15 else {16 for(int i=1;i<=n;i++) {17 int ok = 1;18 for(int j=0;j<cur;j++) {19 if(A[j]==i)20 {21 ok = 0;22 break;23 }24 }25 if(ok) {26 A[cur] = i;27 print_permutation(n,A,cur+1);28 }29 }30 }31 }32 33 int main()34 {35 int A[10];36 print_permutation(5,A,0);37 return 0;38 }
当然有重复的元素，就要看之前用了多少，就类似于一个标记。
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 void print_permutation(int n,int* P,int* A,int cur) { //n 为 p 的长度 6 if(cur==n) { 7 for(int i=0;i<n;i++) { 8 printf("%d ",A[i]); 9 }10 puts("");11 }12 else {13 for(int i=0;i<n;i++) {14 int c1 = 0,c2 = 0;15 for(int j=0;j<cur;j++)16 if(A[j]==P[i]) c1++; //已经用了多少次17 for(int j=0;j<n;j++)18 if(P[i]==P[j]) c2++;19 if(c1<c2) {20 A[cur] = P[i];21 print_permutation(n,P,A,cur+1);22 }23 }24 }25 26 }27 28 int main()29 {30 int p[5] = {1,2,3,5,5};31 int A[10];32 print_permutation(5,p,A,0);33 34 return 0;35 }
然后系统库函数。
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 int main() 6 { 7 8 int A[5] = {5,4,3,2,1}; 9 10 sort(A,A+5);11 12 do {13 for(int i=0;i<5;i++)14 printf("%d ",A[i]);15 puts("");16 }while(next_permutation(A,A+5));17 18 return 0;19 }
枚举法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。