USACO/Hamming Codesヘミングコード(DFS)

N,B,Dが与えられ、2つの符号化の間に少なくともD単位の「Hamming距離」(1<=D<=7)があるように、N個の0または1からなる符号化(1<=N<=64)が求められる.「Hamming距離」とは、2つの符号化について、それらのバイナリ表現における異なるバイナリビットの数を意味する.以下の2つの符号化0 x 554と0 x 234(0 x 554と0 x 234はそれぞれ2つの16進数を表す):0 x 554=0101 01000 x 234=0010 0011 0100同位xxxは5ビットが異なるため、「Hamming距離」は5である.
 
フォーマットPROGRAM NAME:hammingINPUT FORMAT:(file hamming.in)N,B,Dを含む行.OUTPUT FORMAT:(file hamming.out)N個の符号化(10進数で表す)は、ソートするには、10個1行です.解が多ければ、あなたのプログラムはこのような解を出力します:もしそれを2進数にするならば、その値は最小です.SAMPLE INPUT 16 7 3 SAMPLE OUTPUT 0 7 25 30 42 45 51 75 7682 85 97,102,127ヒント他のすべての数に比べて、Hamming距离はすべて要求に合っていなければならない.答え:サンプル出力のように、0と7、0と25、0と......の比較はいずれもヘミングコードに合致し、同様に7と25、7と30、7と......の比較も要求に合致し、このように推定する.これで終わりです.
 
ぶんせき
 
要求されたn個の数をインクリメント順に探索し,前の数と距離がdより大きいか否かを判断し,解のセットを見つけた後,必ず最小であり,出力する.データは大きくなく、暴力的に検索すればいい.注意:

0は必須です。

いくつかの最適化:

bは検索の最大値を与えた:2^b-1(これは最適化ではないようだ)

は、a xor bの数のバイナリ形式の1の数を計算する限り、2つの数a,bの距離を計算する.

/*   



ID: 138_3531   



PROG: hamming  



LANG: C++   



*/  



  



  



#include <fstream>  



  



using namespace std;  



  



int N,B,D;  



int ans[64];  



  



bool Is(int a,int b)  



{  



  int cnt=0;  



  for(int i=0; i<B; ++i)  



      {if((a&1)!=(b&1)) ++cnt; a=a>>1;b=b>>1;}  



  if(cnt>=D)  



      return true;  



  else   



      return false;       



}  



bool Is2(int top,int b)  



{  



 for(int i=0; i<top; ++i)  



  if(!Is(ans[i],b))  



      return false;     



 return true;  



}  



  



void solve()  



{int cnt=1;  



 int count=1;  



 while(cnt<N)  



{  



  if(Is2(cnt,count))  



  {ans[cnt]=count; ++cnt;}  



  count++;   



}  



}  



  



int main()  



{  



  ifstream fin("hamming.in");  



  ofstream fout("hamming.out");  



  fin>>N>>B>>D;  



  solve();  



  for(int i=0,j=1; i<N-1; ++i,++j)  



    { if(j<10)  



       fout<<ans[i]<<' ';  



      else  



       {fout<<ans[i]<<endl; j=0;}  



    }  



       fout<<ans[N-1]<<endl;  



return 0;  



}