USACO - 2.1.5 - Hamming Codes

 

 

原创文章转载请注明出处

摘要：枚举、暴力破解

一. 题目翻译

1. 描述：

给出 N，B 和 D：找出 N 个编码（1 <= N <= 64），每个编码有 B 位[二进制]（1 <= B <= 8），使得两两编码之间至少有 D 个单位的“海明距离”（1 <= D <= 7）。“海明距离”是指对于两个编码，他们二进制表示法中的不同二进制位的数目。看下面的两个编码 0x554 和 0x234 之间的区别（0x554 表示一个十六进制数，每个位上分别是 5，5，4）:

       0x554 = 0101 0101 0100

       0x234 = 0010 0011 0100

       不同位     xxx   xx 

       因为有五个位不同，所以“海明距离”是 5。因为有五个位不同，所以“海明距离”是 5。

2. 格式：

          INPUT FORMAT:

          (file hamming.in)

          一行，包括 N, B, D。

          OUTPUT FORMAT:

          (file hamming.out)

          N 个编码（用十进制表示），要排序，十个一行。如果有多解，你的程序要输出这样的解：假如把它化为2进制数，它的值要最小。

3. SAMPLE：

          SAMPLE INPUT:

16 7 3

          SAMPLE OUTPUT:

0 7 25 30 42 45 51 52 75 76

82 85 97 102 120 127

          

二.  题解

1. 题意理解（将问题分析清楚，大致用什么思路）：

          由于数据量并不是很大，我们可以直接暴力搜索就可以了。从0开始，按照递增顺序搜索，然后按照题目要求，判断是否与之前产生的数的海明距离大于等于D。

 

2. 具体实现（具体实现过程中出现的问题）：

          我们用一个ArrayList记录已经产生的所有结果。

          计算海明距离时，我们使用异或操作（a^b），然后计算异或结果中1的个数（按位计算一个个数）。

3. 需要注意的细节：

          之前使用了byte进行枚举，当byte大于127时，会变为负数，这里要特别注意。

          还要特别注意必须与其他所有的数相比、海明码都符合要求,这个数才正确

三.  代码

/*
ID:fightin1
LANG:JAVA
TASK:hamming
*/

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Scanner;

public class hamming {
	
	static int n ;
	static int b ;
	static int d ;
	
	public static void main(String[] args) {
		try {
//			Scanner in = new Scanner(System.in);
//			PrintWriter pw = new PrintWriter(System.out);
			
			Scanner in = new Scanner(new BufferedReader(new FileReader(
			"hamming.in")));
			PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
			"hamming.out")));
			
			n = in.nextInt();
			b = in.nextInt();
			d = in.nextInt();
			ArrayList<Integer> al = new ArrayList<Integer>();
			al.add(0);
			

			for (int a = 1;al.size()<n&&al.size()>0;a++){
				if (judge(a,al)){
					al.add(a);
				}
			}
			StringBuilder sb = new StringBuilder();
			for(int i=0;i<al.size();i++){
				if ((i+1)%10==0){
					sb.append(al.get(i));
					sb.append("\n");
				}else{
					sb.append(al.get(i)+" ");
				}
			}
			sb.deleteCharAt(sb.length()-1);
			pw.println(sb);
			pw.close();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	public static boolean judge (int a ,ArrayList<Integer> al) {
		boolean result = true;
		for(int i=0;i<al.size();i++){
			if (count(a,al.get(i))<d){
				result = false;
				break;
			}
		}
		return result;
	}
	
	public static int count(int a1 ,int a2){
		int count = 0;
		int c = a1^a2;
		
		for (int i=0;i<b;i++){
			if (c%2 ==1){
				count ++;
			}
			c = c/2;
		}
		return count ;
	}
}