//usaco training-Hamming Codes /* * 题目类型：搜索 * N<64 ，B<=8由于8位二进制数共有511个，数据量比较小可以直接暴力搜索 * res数组记录结果值，逐个搜索当前值，加入到res中 * 每次搜索从res最后的数字的下一个数开始，检查是否满足条件 * ！！！注意输出，N=10时，注意不要多输出空行 */ /* Compiling... Compile: OK Executing... Test 1: TEST OK [0.000 secs, 3028 KB] Test 2: TEST OK [0.000 secs, 3028 KB] Test 3: TEST OK [0.000 secs, 3028 KB] Test 4: TEST OK [0.000 secs, 3028 KB] Test 5: TEST OK [0.000 secs, 3028 KB] Test 6: TEST OK [0.000 secs, 3028 KB] Test 7: TEST OK [0.000 secs, 3028 KB] Test 8: TEST OK [0.000 secs, 3028 KB] Test 9: TEST OK [0.000 secs, 3028 KB] Test 10: TEST OK [0.000 secs, 3028 KB] Test 11: TEST OK [0.000 secs, 3028 KB] All tests OK. */ #include <iostream> #include <cmath> #include <fstream> using namespace std; int res[70]; int N,B,D; bool dist(int a,int b) { int i,num=0; for(i=1; i<=B; ++i){ if((a&1)!=(b&1)) num++; a=a>>1; b=b>>1; } return (num>=D) ? true : false; } int main(void) { int i,j,tmp; ifstream fin("hamming.in"); ofstream fout("hamming.out"); fin>>N>>B>>D; for(i=1; i<N; ++i) for(tmp=res[i-1]+1; tmp<(int)pow((double)2,B); ++tmp){ for(j=0; j<i; ++j) if(!dist(tmp,res[j])) break; if(j==i){ res[i]=tmp; break; } } for(i=0; i!=N; ++i){ if(!((i+1))) fout<<res[i]<<endl; else if(i!=N-1) fout<<res[i]<<' '; else fout<<res[i]; } if(N) fout<<endl; return 0; }
