题目信息

题目类型
练习
题目年份
2025
题目题型
编程题
关 键 词
海明码

题目题干

海明码

给出 N,B 和 D:找出 N 个编码(1 <= N <= 64),每个编码有 B 位(1 <= B <= 8),使得两两编码之间至少有 D 个单位的“海明距离”(1 <= D <= 7)。“海明距离”是指对于两个编码,他们的二进制表示法中的不同二进制位的数目。看下面的两个编码 0x554 和 0x234 之间的区别(0x554 表示一个十六进制数,每个位上分别是 5,5,4):qSm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

    0x554 = 0101 0101 0100
    0x234 = 0010 0011 0100

不同的二进制位: xxx xxqSm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

因为有五个位不同,所以“海明距离”是 5。qSm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入

一行,包括 N, B, D。qSm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输出

N 个编码(用十进制表示),要排序,十个一行。如果有多解,你的程序要输出这样的解:假如把它化为 2^B 进制的数,它的值要最小。qSm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

样例

输入

16 7 3

输出

0 7 25 30 42 45 51 52 75 76
82 85 97 102 120 127

提示

Hamming Codes Rob Kolstad Given N, B, and D: Find a set of N codewords (1 <= N <= 64), each of length B bits (1 <= B <= 8), such that each of the codewords is at least Hamming distance of D (1 <= D <= 7) away from each of the other codewords. The Hamming distance between a pair of codewords is the number of binary bits that differ in their binary notation. Consider the two codewords 0x554 and 0x234 and their differences (0x554 means the hexadecimal number with hex digits 5, 5, and 4):qSm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

    0x554 = 0101 0101 0100
    0x234 = 0010 0011 0100

Bit differences: xxx xxqSm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

Since five bits were different, the Hamming distance is 5.qSm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

PROGRAM NAME: hamming INPUT FORMAT N, B, D on a single lineqSm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

SAMPLE INPUT (file hamming.in) 16 7 3qSm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

OUTPUT FORMAT N codewords, sorted, in decimal, ten per line. In the case of multiple solutions, your program should output the solution which, if interpreted as a base 2^B integer, would have the least value.qSm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

SAMPLE OUTPUT (file hamming.out) 0 7 25 30 42 45 51 52 75 76 82 85 97 102 120 127qSm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

答案解析

相关题目

序言页码 一类书的序言是以罗马数字标页码的。传统罗马数字用单个字母表示特定的数值,一下是标准数字表: I 1 L 50 M 1000 V 5 C 100 X 10 D 500 最多3个可以表示为1
海明码 给出 N,B 和 D:找出 N 个编码(1 <= N <= 64),每个编码有 B 位(1 <= B <= 8),使得两两编码之间至少有 D 个单位的“海明距离”(1
健康的好斯坦奶牛 农民JOHN以拥有世界上最健康的奶牛为骄傲。他知道每种饲料中所包含的的牛所需的最低的维他命量是多少。请你帮助农夫喂养他的牛,以保持他们的健康,使喂给牛的饲料的种数最少。 给出牛所需的
三值的排序 排序是一种很频繁的计算任务。现在考虑最多只有三值的排序问题。一个实际的例子是,当我们给某项竞赛的优胜者按金银铜牌序的时候。 在这个任务中可能的值只有三种1,2和3。我们用交换的方法把他排
跳棋的挑战 检查一个如下的6 x 6的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行,每列,每条对角线(包括两条主对角线的所有对角线)上都至多有一个棋子。 列号 1 2 3 4 5 6 1 | |
数字金字塔 考虑在下面被显示的数字金字塔。 写一个程序来计算从最高点开始在底部任意处结束的路径经过数字的和的最大。 每一步可以走到左下方的点也可以到达右下方的点。 7 3 8 8 1 0 2 7
母亲的牛奶 农民约翰有三个容量分别是A,B,C升的桶,A,B,C分别是三个从1到20的整数,最初,A和B桶都是空的,而C桶是装满牛奶的。有时,约翰把牛奶从一个桶倒到另一个桶中,直到被灌桶装满或原桶空了
等差数列 一个等差数列是一个能表示成a, a+b, a+2b,..., a+nb (n=0,1,2,3,...) 在这个问题中a是一个非负的整数,b是正整数。 写一个程序来找出在双平方数集合S中长度为
修理牛棚 在一个暴风雨的夜晚,农民约翰的牛棚的屋顶、门被吹飞了。 好在许多牛正在度假,所以牛棚没有住满。 剩下的牛一个紧挨着另一个被排成一行来过夜。 有些牛棚里有牛,有些没有。 所有的牛棚有相同的宽度
混合牛奶 牛奶包装是一个如此低利润的生意,所以尽可能低的控制初级产品(牛奶)的价格变的十分重要。 请帮助快乐的牛奶制造者(Merry Milk Makers)以可能的最廉价的方式取得他们所需的牛奶。

提示声明

  • 免责声明:本站资源均来自网络或者用户投稿,仅供用于学习和交流:如有侵权联系删除!
  • 温馨提示:本文属于积分文章,需要充值获得积分或升级VIP会员,也可在会员中心投稿获取。

猜你喜欢