USACO 2.1 Hamming Codes (疊代)

#include <stdio.h>
#define DEBUG 1
#define TESTCASES 9

//numberHasBit1[i]表示二進制數中包含i個1的數的十進制表示
int numberHasBit1[8]={0,1,3,7,15,31,63,127};
int numberArray[257];
int nunmbers;
int codewords, numOfBits, hammingDist;
int result[257];

int countBit1(int num){
	int numOfBit1 = 0;
	while (num){
		num &= (num - 1);
		numOfBit1++;
	}
	return numOfBit1;
}

int main(){
#if DEBUG
	int testCase;
	for (testCase = 1; testCase <= TESTCASES; testCase++){
		char inputFileName[20] = "inputX.txt";
		inputFileName[5] = '1' +  (testCase - 1);
		freopen(inputFileName, "r", stdin);
		printf("\n#%d\n", testCase);
#endif

	scanf("%d%d%d", &codewords, &numOfBits, &hammingDist);

	int first = numberHasBit1[hammingDist];
	int last= (1 << numOfBits) - 1;
	int numbers = 0;
	//先把海明碼距離不小于hammingDist的數存在數組numberArray中
	int num;
	for (num = first + 1; num <= last; num++)
		if (countBit1(num) >= hammingDist)
			numberArray[++numbers] = num;

	result[0] = 0;
	result[1] = first;
	int resultSize = 2;;
	int numberIndex, resultIndex;
	//将數組numberArray中符合要求的數（即與結果數組中的所有數的海明碼距離都不小于hammingDist）儲存在結果數組result中
	for (numberIndex = 1; numberIndex <= numbers; numberIndex++){
		int ok = 1;
		for (resultIndex = 1; resultIndex < resultSize; resultIndex++){
			if (countBit1(numberArray[numberIndex] ^ result[resultIndex]) < hammingDist){
				ok = 0;
				break;
			}
		}
		if (ok)
			result[resultSize++] = numberArray[numberIndex];
		if (resultSize == codewords)
			break;
	}

	//注意輸出格式可以這樣寫
	printf("0");
	for (resultIndex = 1; resultIndex < resultSize; resultIndex++)
		printf("%c%d", resultIndex % 10 == 0 ? '\n' : ' ', result[resultIndex]);	

#if DEBUG
	}
#endif
	return 0;
}