- 浏览: 37654 次
- 性别:
- 来自: 北京
最新评论
-
andyshar:
请问如何在现有的hadoop环境中安装?
Hadoop集群监控系统Ambari安装 -
qingtangpaomian:
失败123 写道您好楼主: 我装好之后为啥老是最后一 ...
Hadoop集群监控系统Ambari安装 -
失败123:
您好楼主: 我装好之后为啥老是最后一步Cluster ...
Hadoop集群监控系统Ambari安装
原创文章转载请注明出处
摘要:枚举、暴力破解
一. 题目翻译
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进制数,它的值要最小。
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 ;
}
}
发表评论
-
USACO - 3.2.2 - Stringsobits
2012-08-23 16:02 805原创文章转载请注明 ... -
USACO - 3.2.1 - Factorials
2012-08-23 16:01 697原创文章转载请注明出处 摘要:动态规划 ... -
USACO - 3.1.6 - Stamps
2012-08-23 16:01 1035原创文章转载请注明 ... -
USACO - 3.1.5 - Contact
2012-08-23 16:01 907原创文章转载请注明出处 摘要:二叉树的应用 , ... -
USACO - 3.1.3 - Humble Numbers
2012-08-23 16:00 711原创文章转载请注明 ... -
USACO - 3.1.2 - Score Inflation
2012-08-22 10:05 903原创文章转载请注明出处 摘要:动态规划 ... -
USACO - 3.1.1 - Agri-Net
2012-08-22 10:04 853原创文章转载请注明出处 摘要:Prim算法 , ... -
USACO - 2.4.5 - Fractions to Decimals
2012-08-22 10:04 959原创文章转载请注明出处 摘要:模拟 , 数论 ... -
USACO - 2.4.4 - Bessie Come Home
2012-08-22 10:04 903原创文章转载请注明出处 摘要:Dijkstra ... -
USACO - 2.4.2 - Overfencing
2012-08-22 10:03 998原创文章转载请注明 ... -
USACO - 2.4.1 - The Tamworth Two
2012-08-21 10:37 715原创文章转载请注明出处 摘要:模拟 ... -
USACO - 2.3.5 - Controlling Companies
2012-08-21 10:37 1300原创文章转载请注明出处 摘要:BFS , 模拟 ... -
USACO - 2.3.4 - Money Systems
2012-08-21 10:37 866原创文章转载请注明 ... -
USACO - 2.3.3 - Zero Sum
2012-08-21 10:36 742原创文章转载请注明出处 摘要:dfs , 枚举 ... -
USACO - 2.3.2 - Cow Pedigrees
2012-08-21 10:36 1007原创文章转载请注明 ... -
USACO - 2.3.1 - Longest Prefix
2012-08-20 20:31 1040原创文章转载请注明 ... -
USACO - 2.2.4 - Party Lamps
2012-08-20 20:30 1206原创文章转载请注明出处 摘要:枚举,三星 ... -
USACO - 2.2.3 - Runaround Numbers
2012-08-20 20:30 657原创文章转载请注明 ... -
USACO - 2.2.2 - Subset Sums
2012-08-20 20:30 694原创文章转载请注明出处 摘要:动态规划 ,0- ... -
USACO - 2.2.1 - Preface Numbering
2012-08-20 20:29 890原创文章转载请注明出处 摘要:模拟 , 数学分析 ...
相关推荐
USACO题目,Greedy Gift Givers
此c++代码实现了USACO上Bessie Come Home的问题,并运用了弗洛伊德算法
此C++程序是实现了USACO网站上的Magic Squares的问题。
该题来自USACO,为最长串的查找,此处方法很笨,有更好方法
USACO chapter one.May hope it useful to someone
USACO chapter two.Useful for beginners.
usaco 上的题目barn1,beads,calfflac,可到那里查看具体题目
Notes-USACO-2021-弹簧
USACO-Cpp
C-Usaco-Work:Usaco在C中的工作
USACO-实践USACO 培训网站的工作实践代码! 100% 工作 - 大部分优化 - 混合语言
这是USACO2001-2007月赛全集。 usaco是美国中学生的官方竞赛网站。是美国著名在线题库,专门为信息学竞赛选手准备。推荐直接阅读英语原文,既准确可靠又可提高英语水平。做题方式模拟正式比赛,采用标准测评机、文件...
资源包包括USACO 2001-2007年月赛的测试数据;usaco月赛十年题典(2000-2009),usaco月赛2002-2008题解。单独下载需资源分30分以上。为了方便编程爱好者,我这边统一下载打包。欢迎下载。
USACO培训网站 我为章节解决方案。 每个文件的多行USACO标识信息注释 第1章全部的解决方案 第2章全部的解决方案
USACO-TurtleCamera 该存储库包含我对USACO问题的所有解决方案。 CSE 199工作区目录将是我用来帮助开发USACO课程的主要目录。
usaco 2010-2011 nov news,喜欢usaco的朋友可以看看
我的USACO题解和程序
Java中的USACO金问题 YYMM 姓名 文件夹 笔记 代码 1812 美食 1812 牛适应性 1812 团队合作
USACO-Guide
usaco历年测试数据