P1461 海明码 Hamming Codes

2024-04-16 01:58
文章标签 hamming codes 明码 p1461

本文主要是介绍P1461 海明码 Hamming Codes,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述
给出 n,b,dn,b,d,要求找出 nn 个由 0,10,1 组成的编码,每个编码有 bb 位),使得两两编码之间至少有 dd 个单位的 “Hamming距离”。“

Hamming距离”是指对于两个编码,他们二进制表示法中的不同二进制位的数目。看下面的两个编码 0x554 和 0x234(十六进制数)

0x554 = 0101 0101 0100
0x234 = 0010 0011 0100
不同位 xxx xx
因为有五个位不同,所以“Hamming距离”是 55。

输入格式
一行,包括 n,b,dn,b,d。

输出格式
nn 个编码(用十进制表示),要排序,十个一行。
如果有多解,你的程序要输出这样的解:假如把它化为 2^b2
b
进制数,它的值要最小。

输入输出样例
输入 #1复制
16 7 3
输出 #1复制
0 7 25 30 42 45 51 52 75 76
82 85 97 102 120 127
说明/提示
【数据范围】
对于 100%100% 的数据,1\le n \le 641≤n≤64,1\le b \le 81≤b≤8,1\le d \le 71≤d≤7。

请解释:“必须与其他所有的数相比,Hamming 距离都符合要求,这个数才正确”

答:如样例输出,0,70,7,0,250,25,比较都符合海明码,同样 7,257,25,7,307,30,比较也符合要求,以此类推。题中至少有 dd 个单位,意思就是大于等于 dd 个单位的都可以。

USACO 2.1

翻译来自NOCOW

思路: 一开始还真没看懂题。其实就是最多8位,然后你顺序找出所有二进制位差异大于等于d的数。异或后1的位数就是差异数。

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;int a[1005];
int n,b,d;
int cnt;int cal(int x)
{int res = 0;while(x){res += x & 1;x >>= 1;}return res;
}int check(int x)
{for(int i = 1;i <= cnt;i++){if(cal(x ^ a[i]) < d){return false;}}return true;
}int main()
{scanf("%d%d%d",&n,&b,&d);for(int i = 0;i < (1 << b);i++){if(check(i)){a[++cnt] = i;}}for(int i = 1;i <= n;i++){printf("%d",a[i]);if(i % 10 == 0)printf("\n");else if(i != n)printf(" ");}return 0;
}

这篇关于P1461 海明码 Hamming Codes的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/907516

相关文章

转载:从小白鼠试毒问题-海明码

问题提出: 有1000瓶水,其中有一瓶有毒,小白鼠只要尝一点带毒的水24小时后就会死亡,至少要多少只小白鼠才能在24小时时鉴别出哪瓶水有毒? 问题分析: 需要多少只小白鼠?这个很容易想到是10只(二进制),但是如何鉴别哪一瓶水有毒?(即如何安排小白鼠?)原贴如下:https://blog.csdn.net/mengtnt/article/details/8477747 海明码计算: 转载

PCI Device Class Codes

目录 Class Code 0: Pre 2.0 Class Code 1: Mass Storage Controllers Class Code 2: Network Controllers Class Code 3: Display Controllers Class Code 4: Multimedia Devices Class Code 5: Memory Co

记Codes 开源研发项目管理平台——管理系统颠覆性创新实现之事件驱动+信息流

引言       市面上所有管理系统,数据都不是以推流的方式展现到前端,有新数据产生需主动刷新页面才能看到,也就是“人找事”;而不是主动推送的“事找人”,Codes 敢为人先,采用事件驱动+信息流实现“事找人”。 1、背景       一个研发团队内主要就这两类人:干活的、和做管理的;采用项目管理工具主要是为了协同、提效和便于管理;对于做管理的人主要用管理相关的功能;对于干活的人,主要是

海明码的基本原理

海明码 一、什么是海明码二、校验位的分布方式1、奇偶校验2、海明码校验位 三、检错原理四、纠错原理 一、什么是海明码 首先来看一下百度的介绍: ‌‌海明码(‌Hamming Code)‌是一种具有检错和纠错能力的编码方式,由‌理查德·汉明(Richard Hamming)于1950年提出。它通过增加少数几个校验位,能够检测出两位同时出错的情况,也能检测出一位出错并自动恢复其正

记Codes 重新定义 SaaS模式开源免费研发项目管理平台——多事项闭环迭代的创新实现

原计划本篇要写0代码接口测试,因最近询问Codes 迭代的人多,就先写多事项闭环迭代的创新实现。      1、简介      Codes 重新定义 SaaS 模式 = 云端认证 + 程序及数据本地安装 + 不限功能 + 30 人免费       Codes  是一个 高效、简洁、轻量的一站式研发项目管理平台。包含需求管理,任务管理,测试管理,缺陷管理,自动化测试,cicd

Java --- serial port communication example codes

/** public SerialBean(int PortID) 本函数构造一个指向特定串口的SerialBean,该串口由参数PortID所指定。PortID = 1 表示COM1,PortID = 2 表示COM2,由此类推。 public int Initialize() 本函数初始化所指定的串口并返回初始化结果。如果初始化成功返回1,否则返回-1。初始化的结果是该串口被Serial

UVa 729: The Hamming Distance Problem

这道题只要枚举出所有情况就可以了。 从最左边一位开始分别讨论为0和为1 两种情况,向右递归。 我的解题代码如下: #include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <cstdlib>#include <string>using namespace std;int s[1

汉明码(海明码)的计算的规则

一.汉明码的由来 1.汉明码(Hamming Code),是在电信领域的一种线性调试码,以发明者理查德·卫斯里·汉明的名字命名。汉明码在传输的消息流中插入验证码,当计算机存储或移动数据时,可能会产生数据位错误,以侦测并更正单一比特错误。由于汉明编码简单,它们被广泛应用于内存(RAM)。 2.海明码一般只能纠1位错。 二.基本知识 设数据位是n位,校验位是k位,则n和k必须满足关系: 2ᵏ-

[Android] Build.VERSION_CODES类下面的版本信息

获取手机版本号:Build.VERSION.SDK_INT Build.VERSION_CODES类下面的版本信息: static int BASE //October 2008: The original, first, version of Android. static int BASE_1_1 //February 2009: First Android update, offi

海明码简单计算方法

海明码校验位大家初学者很难以理解,学习过海明码之后发现了一个简单的方法,计算海明码,特来分享,原理很简单,在将数据位插入校验位空值后,求第x位校验位就直接 从第x位开始, 连续选择x个数据位,再连续略过x个数据位,遇到校验位就舍去, 循环此过程,直至末尾 在校验时,求校验位进行不用舍去计算,直接计算,详细过程如下图: