From 92d2da1251d9712ee86c733e648c0feceeb7d571 Mon Sep 17 00:00:00 2001
From: Iru Cai <mytbk920423@gmail.com>
Date: Thu, 19 Apr 2018 23:12:23 +0800
Subject: finish 2.1

---
 2.1/hamming.c | 75 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 75 insertions(+)
 create mode 100644 2.1/hamming.c

(limited to '2.1/hamming.c')

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;
+}
-- 
cgit v1.2.3