[usaco] 海明码

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):

        0x554 = 0101 0101 0100
        0x234 = 0010 0011 0100
Bit differences: xxx  xx

Since five bits were different, the Hamming distance is 5.

PROGRAM NAME: hamming
INPUT FORMAT
N, B, D on a single line

SAMPLE INPUT (file hamming.in)
16 7 3

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.

SAMPLE OUTPUT (file hamming.out)
0 7 25 30 42 45 51 52 75 76
82 85 97 102 120 127

-----------------------------------------------------------------------------
关键之处在于:
求两个数字键的海明距离。
x=a xor b ,其中为1的位即表示a和b不同的地方。
只需要计算x中1的个数即可。
对于8位二进制数,计算1的个数的方法是:
 x=(x & 0x55555555)+((x>>1)& 0x55555555); 
 x=(x & 0x33333333)+((x>>2)& 0x33333333); 
 x=(x & 0x0F0F0F0F)+((x>>4)& 0x0F0F0F0F); 
 x=(x & 0x00FF00FF)+((x>>8)& 0x00FF00FF); 
 x=(x & 0x0000FFFF)+((x>>16)& 0x0000FFFF); 
经过以上步骤之后,x就是1的个数。

我的程序:
----------------------------------- ----------------------------------------------------------------------
/*
ID: yunleis2
PROG: hamming
LANG: C++
*/
#include<iostream>
#include<fstream>
#include <cmath>
using namespace std;
int N, B, D;
typedef unsigned int uint;
int distance1(uint a,uint b);
int main()
{
 fstream fin("hamming.in",ios::in);
 fin>>N>>B>>D;
 uint src;
 uint end=(1<<B)-1;
 uint  *result= new uint[N];
 result[0]=0;
 int ptr=1;
 for(uint i=1;i<=end;i++)
 {
  bool  flag=true;
  for(int j=0;j<ptr;j++)
  {
   if(distance1(i,result[j])<D)
   {
    flag=false;
    break;
   }
  }
  if(flag)
  {
   result[ptr++]=i;
  }
  if(ptr==N)
   break;
 }
 fstream fout("hamming.out",ios::out);
 for(int i=0;i<ptr;i++)
 {
  fout<<result[i];
  if(((i+1)%10)==0||i==(ptr-1))
   fout<<endl;
  else fout<<" ";
 }
 
}
int distance1(uint a,uint b)
{
 uint x=a^b;
 x=(x & 0x55555555)+((x>>1)& 0x55555555); 
 x=(x & 0x33333333)+((x>>2)& 0x33333333); 
 x=(x & 0x0F0F0F0F)+((x>>4)& 0x0F0F0F0F); 
 x=(x & 0x00FF00FF)+((x>>8)& 0x00FF00FF); 
 x=(x & 0x0000FFFF)+((x>>16)& 0x0000FFFF); 
 return x;

}

时间: 2024-12-20 18:49:58

[usaco] 海明码的相关文章

计算机体系结构(四)——海明码

    海明码(Hamming Code )是一种常用数据校验的编码.它是在信息位为k位,增加r位冗余位(校验码),构成一个n=k+r位的码字.它可以用于检验数据的正误和判别错误位置. [计算海明码]     (1)校验位的确定     最终生成的海明码是n位,其中k位信息位+r位冗余位(校验码).r位的校验位可以表示 2r 个数,但是只有一种表示是正确的,剩余2r -1都是错误的,所以若有2r -1>k+r,即可判别错误位置.       (2)校验位的生成     举例说明吧:有效信息位为1

通俗理解海明码

该文章原文地址http://blog.csdn.net/lycb_gz/article/details/8214961     海明码(Hamming Code)是一个可以有多个校验位,具有检测并纠正一位错误代码的纠错码,所以它也仅用于信道特性比较好的环境中,如以太局域网中,因为如果信道特性不好的情况下,出现的错误通常不是一位.     海明码的检错.纠错基本思想是将有效信息按某种规律分成若干组,每组安排一个校验位进行奇偶性测试,然后产生多位检测信息,并从中得出具体的出错位置,最后通过对错误位取

RAID磁盘阵列技术全面介绍

在计算机发展的初期,"大容量"硬盘的价格还相当高,解决数据存储安全性问题的主要方法是使用磁带机等设备进行备份,这种方法虽然可以保证数据的安全,但查阅和备份工作都相当繁琐.1987年, Patterson.Gibson和Katz这三位工程师在加州大学伯克利分校发表了题为<A Case of Redundant Array of Inexpensive Disks(廉价磁盘冗余阵列方案)>的论文,其基本思想就是将多只容量较小的.相对廉价的硬盘驱动器进行有机组合,使其性能超过一只

校验码(海明校验,CRC冗余校验,奇偶校验)

循环冗余校验码 CRC码利用生成多项式为k个数据位产生r个校验位进行编码,其编码长度为n=k+r所以又称 (n,k)码. CRC码广泛应用于数据通信领域和磁介质存储系统中. CRC理论非常复杂,一般书就给个例题,讲讲方法.现在简单介绍下它的原理: 在k位信息码后接r位校验码,对于一个给定的(n,k)码.可以证明(数学高手自己琢磨证明过程)存在一个最高次幂为 n-k=r 的多项式g(x),根据g(x)可以生成k位信息的校验码,g(x)被称为 生成多项式 用C(x)=C(k-1)C(k-2)...C

HTAP数据库 PostgreSQL 场景与性能测试之 16 - (OLTP) 文本特征向量 - 相似特征(海明...)查询

标签 PostgreSQL , HTAP , OLTP , OLAP , 场景与性能测试 背景 PostgreSQL是一个历史悠久的数据库,历史可以追溯到1973年,最早由2014计算机图灵奖得主,关系数据库的鼻祖Michael_Stonebraker 操刀设计,PostgreSQL具备与Oracle类似的功能.性能.架构以及稳定性. PostgreSQL社区的贡献者众多,来自全球各个行业,历经数年,PostgreSQL 每年发布一个大版本,以持久的生命力和稳定性著称. 2017年10月,Pos

海量数据,海明距离高效检索(smlar) - 阿里云RDS PosgreSQL最佳实践

标签 PostgreSQL , 海明距离 , smlar , GiST索引 背景 http://www.cnblogs.com/lushilin/p/6549665.html SimHash的应用 通过上面的步骤,我们可以利用SimHash算法为每一个网页生成一个向量指纹,那么问题来了,如何判断2篇文本的相似性? 这里面主要应用到是海明距离. (1)什么是海明距离 两个码字的对应比特取值不同的比特数称为这两个码字的海明距离.在一个有效编码集中,任意两个码字的海明距离的最小值称为该编码集的海明距离

《伟大的计算原理》一第3章 Great Principles of Computing 信  息

    本节书摘来自华章出版社<伟大的计算原理>一书中的第3章,第3.1节,作者[美]彼得 J. 丹宁(Peter J. Denning)克雷格 H. 马特尔(Craig H. Martell),更多章节内容可以访问"华章计算机"公众号查看. 第3章 Great Principles of Computing 信 息 通信的内容语义与通信工程无关. --Claude E. Shannon 软件并不只是交互设备,更生成了一个用户生活空间. --Terry Winograd 自

大话存储系列5——RAID原理

整理自网络和大话存储2: 1.预备知识:条带化 当多个进程同时访问一个磁盘时,可能会出现磁盘冲突.大多数磁盘系统都对访问次数(每秒的 I/O 操作,IOPS)和数据传输率(每秒传输的数据量,TPS)有限制.当达到这些限制时,后面需要访问磁盘的进程就需要等待,这时就是所谓的磁盘冲突.     避免磁盘冲突是优化 I/O 性能的一个重要目标,而 I/O 性能的优化与其他资源(如CPU和内存)的优化有着很大的区别 ,I/O 优化最有效的手段是将 I/O 最大限度的进行平衡.     条带化技术就是一种

RAID 独立磁盘真阵列

RAID技术主要包含RAID 0-RAID 50等数个规范,它们的侧重点各不相同,常见的规范有如下几种:       RAID 0:RAID 0连续以位或字节为单位分割数据,并行读/写于多个磁盘上,因此具有很高的数据传输率,但它没有数据冗余,因此并不能算是真正的RAID结构.RAID 0只是单纯地提高性能,并没有为数据的可靠性提供保证,而且其中的一个磁盘失效将影响到所有数据.因此,RAID 0不能应用于数据安全性要求高的场合.         RAID 1:它是通过磁盘数据镜像实现数据冗余,在成