ぶんかつほうこうぞうグレイコード

タイトル
グレイコードは長さ2^nのシーケンスであり、シーケンスには同じ要素がなく、各要素は長さnのバイナリビット列であり、隣接する要素はちょうど1ビットしか異なる.例えば、長さ2^3のグレイ符号は(0000010110110111101100)である.設計分治アルゴリズムは任意のn値に対して対応するグレイコードを構築する.
構想
本アルゴリズムは純粋に観察に基づいており,アルゴリズムには分治の影があるが,分治の意味は発見されていない.n=3と仮定すると、10進数シーケンス:
0,1,2,3,4,5,6,7->0,1,2,3,|6,7,4,5->0,1,|3,2,|6,7,|5,4すなわち,数列を毎回左右等の大きさの半分に分割し,右半分の配列を左右の半分に交換することにより,1つのグレイコードの10進数シーケンスを得,さらに2進数文字列に変換すればよい.
c++実装

/*
	  ：     
	  ：Moyu 
*/
#include
#include
#include
#include
#include

using namespace std;

void Init(vector &v, vector &gc, int n)
{
	int m = pow(2,n);
	for(int i = 0; i < m; ++i){
		v.push_back(i);
		
		string s(n,'0');
		gc.push_back(s);
	}
}
void GrayCode(vector &v, int lo, int hi)
{
	if(hi - lo == 2)
		return;
	else{
		int m = (lo + hi) / 2;
		vector t(v.begin()+m,v.begin()+(m+hi)/2);
		copy(v.begin()+(m+hi)/2,v.begin()+hi,v.begin()+m);
		copy(t.begin(),t.end(),v.begin()+(m+hi)/2);
		GrayCode(v,lo,m);
		GrayCode(v,m,hi);
	}
}
void Conver(vector &v, vector &gc)
{
	int n = v.size();
	for(int i = 0; i < n; ++i)
	{
		int t = v[i];
		int j = gc[0].size()-1;
		while(t){
			gc[i][j] = t%2 + '0';
			t /= 2;
			--j;
		}
	}
}
int main()
{
	int n;
	cout << "n = ";
	cin >> n;
	
	vector v;
	vector gc;
	Init(v,gc,n);
	
	GrayCode(v,0,v.size());
	Conver(v,gc);
	
	for(auto i : v)
		cout << i << " ";
	cout << endl;
	for(auto s : gc)
		cout << s << endl;
	return 0;
}

箴言録:
天行健、君子は自強で止まらない.地勢坤、君子は厚徳で物を載せる.