昨天参加腾讯的笔试,结果答的一塌糊涂,大题第一题是关于格雷码的递归实现的,当时没写出来,今天查了下资料试着用C++实现一下。

#include <iostream>
#include <cmath>
#include <string>
using namespace std;
unsigned int *uIntGaryCode(int N);//二进制格雷码
string *sGaryCode(int N);//字符串型格雷码 int main()
{
int N;
N=;
string *sCode=sGaryCode(N);
for(int i=;i<pow(,N);i++)
cout<<sCode[i]<<endl;
system("pause");
return ;
} unsigned int *uIntGaryCode(int N)//二进制型格雷码的递归实现
{
unsigned int *code=new unsigned int[(int)pow(,N)];
if(==N)
{
code[]=;
code[]=;
}
else
{
int length=(int)pow(,N-);
unsigned int*uiCode=uIntGaryCode(N-);
for(int i=;i<length;i++)
{
code[i]=uiCode[i] ;
code[length+i]= uiCode[length-i-]+pow(,N-);
}
delete []uiCode;
}
return code;
} string *sGaryCode(int N)//字符串型格雷码的递归实现
{
string *code=new string[(int)pow(,N)];
if(==N)
{
code[]='';
code[]='';
}
else
{
int length=(int)pow(,N-);
string *sCode=sGaryCode(N-);
for(int i=;i<length;i++)
{
code[i]=""+sCode[i];
code[length+i]=''+sCode[length-i-];
}
delete [] sCode;
}
return code;
}
05-11 22:14