【题解】海明码
题目描述
给出 n,b,d，要求找出 n 个由 0,10,1 组成的编码，每个编码有 b 位），使得两两编码之间至少有 d 个单位的 “Hamming距离”。“Hamming距离”是指对于两个编码，他们二进制表示法中的不同二进制位的数目。看下面的两个编码 0x554 和 0x234（十六进制数）
0x554 = 0101 0101 0100
0x234 = 0010 0011 0100
不同位 xxx xx因为有五个位不同，所以“Hamming距离”是 5。
输入格式
一行，包括 n,b,d。
输出格式
n 个编码（用十进制表示），要排序，十个一行。 如果有多解，你的程序要输出这样的解：假如把它化为 2b2^b2b 进制数，它的值要最小。
输入输出样例
输入 #1
16 7 3输出 #1
0 7 25 30 42 45 51 52 75 76
82 85 97 102 120 127说明/提示
【数据范围】 对于 100% 的数据，1≤n≤64，1≤b≤8，1≤d≤71\le n \le 64，1\le b \le 8，1\le d \le 71≤n≤64，1≤b≤8，1≤d≤7。
请解释：“必须与其他所有的数相比，Hamming 距离都符合要求，这个数才正确”
答：如样例输出，0,7，0,25，比较都符合海明码，同样 7,25，7,30，比较也符合要求，以此类推。题中至少有 d 个单位，意思就是大于等于 d 个单位的都可以。
题目解析
题目要求输出n个相互之间海明距离至少为d的数字，并按格式进行输出。
其中，0是在里面的。我们就从1开始一个个找，看是否与前面的数的海明距离至少为d。
框架：
for(int i=1;cnt<n;i++){
if(check(i)){//i与前面的每个数海明距离都至少为d
输出 i
cnt++;//满足条件的数的个数增加
}
}那么如何统计两个数字x和y之间的海明距离呢？
海明距离的定义为：是指对于两个编码，他们二进制表示法中的不同二进制位的数目。那么也就是说找两个数的二进制数中不同位的个数。我们利用^来找不同，^符号，相同为0，不同为1，统计x^y 的二进制中的1的个数即可。
统计x的二进制中1的个数:
int count(int x){
//统计x对应二进制中1的数量
int cnt=0;
while(x){
x&=(x-1);//消去二进制中最低位的1
cnt++;
}
return cnt;
}代码实现
#include <iostream>
#include <cstdio>
using namespace std;
int count(int x){
//统计x对应二进制中1的数量
int cnt=0;
while(x){
x&=(x-1);//消去二进制中最低位的1
cnt++;
}
return cnt;
}
int num[70];//存放已符合条件的数字
int main(){
int n,b,d;
cin>>n>>b>>d;
int cnt=1;//0是第一个数
cout<<0<<" ";
for(int i=1;cnt<n;i++){
//判断i是否和前面的数都至少有d个单位的hamming距离
bool flag=true;
for(int j=0;j<cnt;j++){
//如果i与前面的某个数海明距离<d,他就不符合要求
if(count(i^num[j])<d){
flag=false;
break;
}
}
if(flag){
cout<<i<<" ";
num[cnt++]=i;//存入数组
if(cnt%10==0) cout<<endl;//每行10个
}
}
return 0;
}Q.E.D.
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
