本文主要是介绍处女座与汉明距离，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目描述】
定义两个数之间的汉明距离为两个数异或值的二进制中1的个数。
问是否存在一个 0-2^(n-1) 的排列 a，使得相邻两个数 ai 和 ai+1 的汉明距离均为 m，a2^n 和 a1 也算相邻。
【输入描述】
一行，两个数n和m
2<=n<=20, 1<=m<n【输出描述】
如果存在这样的排列，第一行输出"YES",下面2n行，每行一个整数，输出这个排列。如果有多组答案，输出任意一组即可
如果不存在，输出”NO”【样例】
示例1
输入
2 1
输出
YES
0
1
3
2
思路：
首先判断奇偶性，当 m 为偶数是，肯定不可能的，而当 m 为奇数时，需要进行构造，可以使用格雷码
对于格雷码，从 n 位变为 n+1 位，就是把后一半的数首位变为 1，后 n 位进行关于前一半的镜像排列，这样可以保证相连两个数的汉明距离为 m
对于 m=1 时，使用格雷码即可，从而可以构造出 m=n-1 的情况，只需将偶数行取反即可，因此可以先构造 (m+1,m) 的情况，然后从 m+1 递推到 n
【源代码】
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#define PI acos(-1.0)
#define E 1e-6
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define N 2000000
#define LL long long
using namespace std;
int n,m;
int a[N];
int b[N];
int calculate(int x){//计算x转为二进制后1的个数int res=0;while(x){res++;x=x&(x-1);}return res;
}int main(){scanf("%d%d",&n,&m);if (m%2==0){printf("NO\n");return 0;}else{//构造格雷码a[0]=0; a[1]=1;for(int i=1;i<n;i++)for(int j=(1<<i);j<(1<<(i+1));j++)a[j]=(1<<i)^(a[(1<<(i+1))-1-j]);if(m==1){//等于1的情况printf("YES\n");for(int i=0;i<(1<<n);i++)printf("%d\n",a[i]);}else{//大于1的情况printf("YES\n");for(int i=0;i<(1<<(m+1));i++){if(i%2==0)//偶数取反b[i]=a[i];elseb[i]=a[i]^((1<<(m+1))-1);}for(int i=m+1;i<n;i++){int p=-1;for(int j=0;j<(1<<i);j++){if(calculate(b[j]^b[(1<<i)-1])==m-1 && calculate(b[(j+(1<<i)-1)%(1<<i)])==m-1){//计算1的位数p=j;break;}}if(p==-1)return 0;for(int j=0;j<(1<<i);j++)b[(1<<i)+j]=(1<<i)^b[(p+j)%(1<<i)];}for(int i=0;i<(1<<n);i++)printf("%d\n",b[i]);}}return 0;
}
这篇关于处女座与汉明距离的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
