diff options
Diffstat (limited to '2.1/hamming.c')
-rw-r--r-- | 2.1/hamming.c | 75 |
1 files changed, 75 insertions, 0 deletions
diff --git a/2.1/hamming.c b/2.1/hamming.c new file mode 100644 index 0000000..abc3483 --- /dev/null +++ b/2.1/hamming.c @@ -0,0 +1,75 @@ +/* +ID: mytbk921 +LANG: C +TASK: hamming +*/ + +#include <stdio.h> + +typedef unsigned char u8; + +static unsigned +popcount(unsigned x) +{ + unsigned c = 0; + while (x) { + if (x&1) c++; + x >>= 1; + } + return c; +} + +static unsigned +hamdist(unsigned x, unsigned y) +{ + return popcount(x^y); +} + +u8 s[64]; +int N, B, D; + +int search(int i) +{ + int t, j; + if (i==N) return 1; + + for (t=s[i-1]+1; t<(1<<B); t++) { + for (j=0; j<i; j++) { + if (hamdist(s[j], t)<D) + break; + } + if (j==i) { + s[j] = t; + if (search(i+1)) + return 1; + } + } + /* all searched */ + return 0; +} + +int main() +{ + int i; + + FILE *fin = fopen("hamming.in", "r"); + FILE *fout = fopen("hamming.out", "w"); + fscanf(fin, "%d%d%d", &N, &B, &D); + fclose(fin); + + s[0] = 0; + if (search(1)) { + for (i=0; i<N; i++) { + if (i%10==0) { + if (i>0) + fprintf(fout, "\n"); + } else { + fprintf(fout, " "); + } + fprintf(fout, "%d", s[i]); + } + fprintf(fout, "\n"); + } + fclose(fout); + return 0; +} |