« 问题描述
Gray码是一个长度为2n的序列。序列中无相同的元素，每个元素都是长度为n位的串，相邻元素恰好只有一位不同。用分治策略设计一个算法对任意的n构造相应的Gray码。
« 编程任务
利用分治策略试设计一个算法对任意的n构造相应的Gray码。
« 数据输入
由文件input.txt提供输入数据n。
« 结果输出
程序运行结束时，将得到的所有编码输出到文件output.txt中。
输入文件示例
输出文件示例
input.txt
output.txt
3
0 0 0
0 0 1
0 1 1
0 1 0
1 1 0
1 1 1
1 0 1
1 0 0
« 实现提示
把原问题分解为两个子问题，分别对两个子问题的每个数组后一位加0和1。
这是典型的分治法问题，采用分治的思想，代码如下：
#include<iostream> #include<math.h> #include<fstream> using namespace std; void getGray(int **arr,int n,int row) { //结束标志 if(n == 1){ arr[0][n-1] = 0; arr[1][n-1] = 1; return; } for(int i = 0; i < row/2 ; i++) { arr[i][n-1] = 0; //上半部分赋值为0 arr[row-i-1][n-1]=1; //下半部分赋值为1 } getGray(arr,n-1,row/2); for(int j=row/2; j<row; j++) for(int k=0; k<n-1; k++) arr[j][k] = arr[row-j-1][k]; } int main() { ifstream in("F://不归路//编程//算法设计与分析B//文件夹//input.txt"); ofstream out("F://不归路//编程//算法设计与分析B//文件夹//output.txt"); int n = 0; //文件内容 in>>n; if(n==0 || n>20) { cout<<"输入错误"<<endl; return 0; } // cout<<n<<endl; int row=pow(2,n); int **arr=new int*[row]; for(int m=0;m<row;m++){ arr[m]=new int[n]; } //调用递归函数 getGray(arr,n,row); //输出 for(int i=0;i<row;i++){ for(int j=n-1;j>=0;j--){ cout<<arr[i][j]; out<<arr[i][j];} cout<<endl; out<<"\n";} return 0; }