现在的位置: 首页 > 综合 > 正文

Hamming Codes

2012年07月21日 ⁄ 综合 ⁄ 共 1036字 ⁄ 字号 评论关闭

完全没找着方法

结果看了别人的答案,竟然说是简单的dfs就好了~

(1)本来还自以为聪明的决定先计数那些和别的编码距离小于给定值d的个数,然后排除不满足给定n的个数。结果发现根本就是给定集合的排列,每个编码个的编码距离都是一定的。这样计算下来每个的值都相同。

看了网上别人做的代码,模仿着使用dfs计算

(2)只能老实的使用dfs,遍历解空间

每个编码只有两种情况:1在解集合中2不在解集合中

 

ps:总是把简单问题复杂化,每次总想找捷径,结果最后还是最保守的办法解决问题。

 

*计算2^n,可以使用1<<n

 

USACO:

We also know that 0 can be one of the numbers in the set, because if the minimum number in the set were N instead of 0, we could XOR N to each number in the set and they would still be the same distance apart.

我们可以知道0在解集合中,因为如解结合中最小值为N,而不是0,那么可以让 N和集合中的每个数字异或,他们也将会分别有同样距离。

还是没理解~

--------------------------------------

 

 

一下为从网上找来的题目翻译:

Hamming Codes
海明码
Rob Kolstad
译 by Felicia Crazy
给出 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。
PROGRAM NAME: hamming
INPUT FORMAT
一行,包括 N, B, D。
SAMPLE INPUT (file hamming.in)
16 7 3
OUTPUT FORMAT
N 个编码(用十进制表示),要排序,十个一行。如果有多解,你的程序要输出这样的解:假如把它化为 2^B 进制的数,它的值要最小。
SAMPLE OUTPUT (file hamming.out)
0 7 25 30 42 45 51 52 75 76
82 85 97 102 120 127

抱歉!评论已关闭.