题目描述

给出 n,b,d,要求找出 n 个由 0,10,1 组成的编码,每个编码有 b 位),使得两两编码之间至少有 d 个单位的 “Hamming距离”。“Hamming距离”是指对于两个编码,他们二进制表示法中的不同二进制位的数目。看下面的两个编码 0x5540x234(十六进制数)

0x554 = 0101 0101 0100
0x234 = 0010 0011 0100
不同位    xxx  xx

因为有五个位不同,所以“Hamming距离”是 5。

输入格式

一行,包括 n,b,d。

输出格式

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

输入输出样例

输入 #1

16 7 3

输出 #1

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

说明/提示

【数据范围】
对于 100% 的数据,1n641b81d71\le n \le 64,1\le b \le 8,1\le d \le 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.


( ノ^ω^)ノ゚ 稻 花 香 里 说 丰 年 , 听 取 WA 声 一 片 。(╥╯^╰╥)