Posted on 2010-08-22 10:58
lzh525 阅读(1161)
评论(0) 编辑 收藏 引用 所属分类:
数据结构及算法问题
1 #include<iostream>
2 using namespace std;
3
4 const int MAX=100;
5 int a[MAX];
6 bool finished=false;//是否找到了所要全部求的解
7
8 void process(int *a,int n)
9 {
10 int i,first=0;
11 for(i=1;i<=n;i++)
12 {
13 if(first)
14 cout<<" ";
15 first=1;
16 cout<<a[i];
17 }
18 cout<<endl;
19 }
20
21 bool is_ok(int k,int n)
22 {
23 return (k==n);
24 }
25
26 void creat_c(int *a,int k,int n,int *c,int *m)//最核心的构造候选元素的函数
27 {
28 int i;
29 bool flag[MAX];
30 for(i=1;i<MAX;i++)
31 flag[i]=false;
32 for(i=1;i<k;i++)
33 flag[a[i]]=true;//标记已之前被加入排列的元素
34 *m=0;
35 for(i=1;i<=n;i++)
36 if(flag[i]==false)
37 {
38 c[*m]=i;
39 *m=*m+1;
40 }
41 }
42
43 void backtrack(int *a,int k,int n)
44 {
45 int c[MAX];//存储下一位的可能元素
46 int m;//下一位可能元素的个数
47 int i;
48 if(is_ok(k,n))
49 process(a,n);
50 else
51 {
52 k++;
53 creat_c(a,k,n,c,&m);
54 for(i=0;i<m;i++)
55 {
56 a[k]=c[i];
57 backtrack(a,k,n);
58 if(finished)
59 return ;//提前结束
60 }
61 }
62 }
63
64 int main()
65 {
66 int n;
67 while(cin>>n)
68 {
69 backtrack(a,0,n);
70 }
71 return 0;
72 }
子集生成
1 #include<iostream>
2 using namespace std;
3
4 const int MAX=100;
5 int a[MAX];
6 bool finished=false;//是否找到了所要全部求的解
7 int num;//子集数目
8
9 void process(int *a,int k)
10 {
11 num++;
12 int t;//标记，处理输出的自己元素之间加上","隔开
13 int i,first=0;
14 cout<<"{";
15 t=0;
16 for(i=1;i<=k;i++)
17 if(a[i]==true)
18 {
19 if(t==1)
20 cout<<",";
21 cout<<i;
22 t=1;
23 }
24 cout<<"}\\n";
25 }
26
27 bool is_ok(int k,int n)
28 {
29 return (k==n);
30 }
31
32 void creat_c(int *a,int k,int n,int *c,int *m)//最核心的构造候选元素的函数
33 {
34 c[0]=true;//c[i]为true则将i加入到当前生成的子集中
35 c[1]=false;//c[i]为false则不将i加入到当前生成的子集中
36 *m=2;
37 }
38
39 void backtrack(int *a,int k,int n)
40 {
41 int c[MAX];//存储下一位的可能元素
42 int m;//下一位可能元素的个数
43 int i;
44 if(is_ok(k,n))
45 process(a,k);
46 else
47 {
48 k++;
49 creat_c(a,k,n,c,&m);
50 for(i=0;i<m;i++)
51 {
52 a[k]=c[i];
53 backtrack(a,k,n);
54 if(finished)
55 return ;//提前结束
56 }
57 }
58 }
59
60 int main()
61 {
62 int n;
63 while(cin>>n)
64 {
65 num=0;
66 backtrack(a,0,n);
67 cout<<"子集的数目为: "<<num<<endl;
68 }
69 return 0;
70 }