01序列-相邻序列一位不同问题

@[TOC]01序列-相邻序列一位不同问题

今天遇到了这样一个问题：给定一个整数n，求长度为n的所有01序列的一种排列，在这个排列中相邻序列只有一位不同
如下表

当n=1时，结果序列排列为 0 1
当n=2时
在正序的n=1的排列里的每个序列前加上一个0，结果为 00 01
在逆序的n=1的排列里的每个序列前加上一个1，结果为 11 10
综合起来为 00 01 11 10
当n=3时
在正序的n=2的排列里的每个序列前加上一个0，结果为 000 001 011 010
在逆序的n=2的排列里的每个序列前加上一个1，结果为 110 111 101 100
综合起来为000 001 011 010 110 111 101 100
…
由此得到规律，想得到长度为n的序列符合要求的排列
只需
在正序的每个序列长度为n-1的符合要求的排列里的每个序列前加上一个0
在逆序的每个序列长度为n-1的符合要求的排列里的每个序列前加上一个1
综合他们的结果即可
C++参考代码如下：
PS: C++不太会用，C拼接字符串不太方便

#include
using namespace std;

int n;
vector res;

void solve(int n){
	
	bool flag = true;
	vector temp;
	temp.push_back("0");
	temp.push_back("1");
	//定义了temp和res两个字符串数组，辗转储存不同长度为i的序列排列
	//如temp存长度为1时的排列，res根据temp中的排列生成长度为2的排列，然后temp在根据res...
	for (int i = 1; i < n; i ++ ){
	
		int size = (int)pow(2, i);
		if(flag){
			res.clear();
			for (int j = 0; j < size; j ++ )
				res.push_back("0" + temp[j]);
			for (int j = size - 1; j >= 0; j -- )
				res.push_back("1" + temp[j]);
		}
		else{
			temp.clear();
			for (int j = 0; j < size; j ++ )
				temp.push_back("0" + res[j]);
			for (int j = size - 1; j >= 0; j -- )
				temp.push_back("1" + res[j]);
		}
		flag = !flag;
	}	
	//n为奇数时答案存在temp中，需放到res里
	if(n % 2){
		res.clear();
		for (int i = 0; i < temp.size(); i ++ )
			res.push_back(temp[i]);
		temp.clear();
	}
}

int main(){

	cin >> n;
	solve(n);
	for (int i = 0; i < res.size(); i ++ ) cout << res[i] << endl;
	return 0;
	
}

打表后观察得到的规律，拿n=4的情况做分析：
把结果从中间分成两部分，第一列上下两部分相反，其他列都是上下对称的，先把上下两部分第一列填好，然后只需先把除去第一列的上部分求出来，下部分直接复制即可

再看刚才要求的除去第一列的上半部分，再分成两部分，除去现在的第一列发现还是对称，发现规律

C++参考代码：

#include
using namespace std;
const int N = 1025;
int a[N][N];
int n;


void solve(int sx, int sy, int ex, int ey){

	if(sy > ey)
		return ;
	
	for (int i = ex / 2 + 1; i <= ex; i ++ )
		a[i][sy] = 1;
	
	for (int i = sx; i <= ex / 2; i ++ )
		a[i][sy] = 0;
	
	solve(sx, sy + 1, ex / 2, ey);
	
	for (int i = sx + ex / 2; i <= ex; i ++ )
		for (int j = sy + 1; j <= ey; j ++ )
			a[i][j] = a[ex - i + 1][j]; 
	
}

int main(){
	
	cin >> n;
	
	solve(1, 1, (int)pow(2, n), n);
	
	for (int i = 1; i <= (int)pow(2, n); i ++ ){
		for (int j = 1; j <= n; j ++ )
			printf("%d", a[i][j]);
		printf("n");
	}
	return 0;
}

第一次写博客，请多指正