在博客中看到過一次格雷碼生成算法，我在這里也想寫一下。

原文中的算法為：假設(shè)已經(jīng)生成了k位格雷碼，那么k+1位格雷碼的生成方式為(1) 按序在k位格雷碼前插入一位0，生成一組編碼，(2)按逆序在k位格雷碼前插入一位1，生成另外一組編碼，兩組編碼合起來就是k+1位格雷碼。

如下例：

已有2位格雷碼：00, 01, 11, 10，要生成3位格雷碼，采用此算法：

(1)按序在各碼前插入0，生成000,001,011,010；

(2)按逆序在各碼前插入1，生成110,111,101,100；

(3)將兩組編碼組合起來：000, 001, 011, 010, 110, 111, 101, 100，為3位格雷碼。

另外一種算法與此算法類似，不同的是插入的位是在格雷碼的后面：

對(duì)于k位格雷碼，在各格雷碼后面分別插入0, 1 或 1, 0，生成兩個(gè)編碼，所有插入完成后組合起來的編碼為k+1位格雷碼。

如已有2位格雷碼：00,01,11,10，生成3位格雷碼，采用此算法：

(1)在00編碼后面分別插入0,1，生成000, 001;

(2)在01編碼后面分別插入1,0，生成011, 010;

(3)在11編碼后面分別插入0,1，生成110, 111;

(4)在10編碼后面分別插入1,0，生成101,100;

(5)將生成的編碼組合起來：000, 001, 011, 010, 110, 111, 101, 100，為3位格雷碼。

代碼如下：

#include#include#include#includevoid?GrayCodeOne(int?num);
void?GrayCodeTwo(int?num);

using?namespace?std;

int?main()
{
	int?count;
	cout?<<?"Input?Code?Number:";
	cin?>>?count;

	cout?<<?"Produce?Gray?Code?using?method?1"?<<?endl;
	clock_t?beginOne?=?clock();
	GrayCodeOne(count);
	clock_t?endOne?=?clock();
	cout?<<?"Gray?Code?First?Method?using?time:?"?<<?(endOne?-?beginOne)?<<?endl;

	cout?<<?"Produce?Gray?Code?using?method?2"?<<?endl;
	clock_t?beginTwo?=?clock();
	GrayCodeTwo(count);
	clock_t?endTwo?=?clock();
	cout?<<?"Gray?Code?Second?Method?using?time:?"?<<?(endTwo?-?beginTwo)?<<?endl;

	return?0;
}


//?Method?to?produce?gray?code?using?method?inserting?0?in?front?of?old?gray?code?by?positive
//?and?inserting?1?in?front?of?old?gray?code?by?nagative.
void?GrayCodeOne(int?num)
{
	if?(num?<?1)
	{
		cout?<<?"Error?input?Integer"?<<?endl;
		return;
	}

	vectorcodeVec;

	int?cIdx?=?1;
	for?(;?cIdx?<=?num;?cIdx++)
	{
		if?(codeVec.size()?<?2)
		{
			codeVec.push_back("0");
			codeVec.push_back("1");
		}
		else
		{
			vectortranVec;
			tranVec.resize(2?*?codeVec.size());
			int?tranIdx?=?0;
			vector::iterator?codeIter?=?codeVec.begin();
			for?(;?codeIter?!=?codeVec.end();?codeIter++)
			{
				string?str?=?"0";
				str.append(*codeIter);
				tranVec[tranIdx++]?=?str;
			}

			vector::reverse_iterator?rCodeIter?=?codeVec.rbegin();
			for?(;?rCodeIter?!=?codeVec.rend();?rCodeIter++)
			{
				string?str?=?"1";
				str.append(*rCodeIter);
				tranVec[tranIdx++]?=?str;?
			}

			codeVec.assign(tranVec.begin(),?tranVec.end());
		}
	}

	//vector::iterator?vecIter?=?codeVec.begin();
	//for?(;?vecIter?!=?codeVec.end();?vecIter++)
	//{
	//	cout?<<?*vecIter?<<?endl;
	//}

	return;
}


//?Method?to?produce?gray?code?using?method?inserting?0/1?in?the?back?of?first?gray?code
//?then?inserting?1/0?in?the?back?of?next?gray?code.
void?GrayCodeTwo(int?num)
{
	if?(num?<?1)
	{
		cout?<<?"Input?error?Integer"?<<?endl;
		return;
	}



	vectorcodeVec;

	int?cIdx?=?1;
	for?(;?cIdx?<=?num;?cIdx++)
	{
		if?(codeVec.size()?<?2)
		{
			codeVec.push_back("0");
			codeVec.push_back("1");
		}
		else
		{
			vectortranVec;
			int?tranIdx?=?0;
			int?cIdx?=?codeVec.size();

			tranVec.resize(2?*?cIdx);
			for?(int?vIdx?=?0;?vIdx?<?cIdx;?vIdx++)
			{
				string?str?=?codeVec[vIdx];
				if?(0?==?(vIdx?%?2))
				{
					string?str0?=?str;
					str0.append("0");
					tranVec[tranIdx++]?=?str0;

					string?str1?=?str;
					str1.append("1");
					tranVec[tranIdx++]?=?str1;
				}
				else
				{
					string?str0?=?str;
					str0.append("1");
					tranVec[tranIdx++]?=?str0;

					string?str1?=?str;
					str1.append("0");
					tranVec[tranIdx++]?=?str1;
				}
			}

			codeVec.assign(tranVec.begin(),?tranVec.end());
		}
	}

	//vector::iterator?vecIter?=?codeVec.begin();
	//for?(;?vecIter?!=?codeVec.end();?vecIter++)
	//{
	//	cout?<<?*vecIter?<<?endl;
	//}

	return;
}

運(yùn)行時(shí)間的測試：

12位格雷碼，方法一和方法二所需時(shí)鐘數(shù)

16位格雷碼，兩種方法所需時(shí)鐘數(shù)