USACO2.1 Hamming Codes(hamming)

从0开始递增遍历所有自然数，直到取得n个满足要求的数为止。使用C++标准程序库bitset类型保存自然数a的二进制值，如果该二进制满足题目要求，则将a与其二进制对象保存进map<int，bitset<8> >中，然后继续递增a值遍历检验。感觉算法复杂度挺高，但是所有测试例都是0秒通过，稍稍惊喜。
 
 
01 /*
02 ID:jzzlee1
03 PROG:hamming
04 LANG:C++
05 */
06 #include<iostream>
07 #include<fstream>
08 #include<cmath>
09 #include<string>
10 #include<bitset>
11 #include<cstring>
12 #include<map>
13 using namespace std;
14 ifstream fin("hamming.in");
15 ofstream fout("hamming.out");
16 map<int,bitset<8> > map1;
17 map<int,bitset<8> >::iterator iter;
18 int n,b,d;
19 bool check(bitset<8> bt)      //检验该二进制对象是否满足与之前所有二进制对象汉明码距离至少为d
20 {
21     int k=0;
22     for(iter=map1.begin();iter!=map1.end();++iter)
23     {
24         k=0;
25         for(int index=0;index!=8;++index)
26         {
27             if((iter->second)[index]!=bt[index])
28                 ++k;
29         }
30         if(k<d)
31             return 0;
32     }
33     return 1;
34 }
35 int main()
36 {
37     //cin>>n>>b>>d;www.zzzyk.com
38     fin>>n>>b>>d;
39     int a;
40      
41     int count=0;
42     for(a=0,count=0;count!=n;++a)
43     {
44         bitset<8> bt(a);
45         if(check(bt))
46         {
47             map1.insert(make_pair(a,bt));
48             ++count;
49         }
50     }
51     int i;
52     for(i=1,iter=map1.begin();iter!=map1.end();++i,++iter)      //输出
53     {
54         //注意输出格式，容易格式错
55         //cout<<iter->first;
56         fout<<iter->first;
57         if(i%10==0)
58             fout<<endl;
59             //cout<<endl;
60         else if(i!=n)
61             fout<<" ";
62             //cout<<" ";
63         if(i==n&&i%10!=0)
64             fout<<endl;
65             //cout<<endl;
66     }
67     return 0;
68 }

补充：软件开发 , C++ ,

上一个：C++单例模式
下一个：封装远程注入类CreateRemoteThreadEx