分治法生成格雷码

谁践踏了优雅 2022-01-06 10:29 352阅读 0赞

1、格雷码的介绍  
[格雷码 百度百科][Link 1]

2、找规律的方式，产生格雷码  
代码来源：[构造Gray码的分治算法][Gray]

#include "iostream"
    #include "cmath"
    using namespace std;
    
    const int N=10;
    int arr[N*N][N]; //arr[i][j]表示第i个格雷码的第j位
    
    //构造b位格雷码
    //a为格雷码的个数
    void gray(int a, int b)
    {
        if(b==1) //如果格雷码宽度为1
        {
            arr[0][0] = 0;3
            arr[1][0] = 1;
            return;
        }
        for(int i=0; i<a/2; i++) //格雷码最高位
        {
            arr[i][b-1] = 0;  //生成的格雷码前一半最高位填“0”
            arr[a-i-1][b-1] = 1;  //后一半最高位位填“1”
        }
        gray(a/2, b-1);  //生成b-1位格雷码，填写到目标码高半部分
        for(int i=a/2; i<a; i++) //格雷码低半部分
            for(int j=0; j<b-1; j++)
                arr[i][j] = arr[a-i-1][j];
    }
    
    int main()
    {
        int b;
        cout << "输入格雷码位数：";
        cin >> b;
        int a = pow(2, b);  //格雷码个数
        gray(a, b);
        cout << "格雷码为：\n";
        for(int i=0; i<a; i++)
        {
            for(int j=0; j<b; j++)
                cout << arr[i][j];
            cout << endl;
        }
        return 0;
    }cd

图解上述程序：（回头补上）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzM4ODE2OTI0_size_16_color_FFFFFF_t_70]

2、产生格雷码的正确打开方式  
递归生成码表  
这种方法基于格雷码是反射码的事实，利用递归的如下规则来构造：

*  1位格雷码有两个码字
 *  (n+1)位格雷码中的前2n个码字等于n位格雷码的码字，按顺序书写，加前缀0
 *  (n+1)位格雷码中的后2n个码字等于n位格雷码的码字，按逆序书写，加前缀1 \[4\]
 *  n+1位格雷码的集合 = n位格雷码集合(顺序)加前缀0 + n位格雷码集合(逆序)加前缀1

代码来源：16级柏哥  
参考代码：[一个小编程题-递归方式生成N位格雷码][-_N]

//参考 16级柏哥程序
    //2019/6/24
    #include<iostream>
    #include<string>
    #include<vector>
    
    using namespace std;
    
    vector<string> g;
    
    void Grid(int n) 
    {
    	if(n<1)
    		return;
    	if(n==1)
    	{
    		g.push_back("0");
    		g.push_back("1");
    	}
    	else
    	{
    		Grid(n-1);
    		int length=g.size();
    		for(int i=0;i<length;i++)
    			g.push_back("0"+g[i]);
    		for(int i=length-1;i>=0;i--)
    			g.push_back("1"+g[i]);
    		g.erase(g.begin(),g.begin()+length);
    	}
    } 
    
    
    
    int main(void) 
    {
    	int n;
    	while(cin>>n)
    	{
    		g.clear();
    		Grid(n);
    		for(int i=0;i<g.size();i++)
    			cout<<g[i]<<endl; 
    		cout<<"total grid:"<<g.size()<<endl;
    	} 
    }

图解代码：（回头补上）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzM4ODE2OTI0_size_16_color_FFFFFF_t_70 1]

参考文章  
[格雷码 百度百科][Link 1]  
[构造Gray码的分治算法][Gray]  
[一个小编程题-递归方式生成N位格雷码][-_N]

[Link 1]: https://baike.baidu.com/item/%E6%A0%BC%E9%9B%B7%E7%A0%81/6510858?fr=aladdin
[Gray]: https://blog.csdn.net/u012319493/article/details/49851799
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzM4ODE2OTI0_size_16_color_FFFFFF_t_70]: /images/20211227/0ee086126ffc4a679c8ae7e431467806.png
[-_N]: https://brokendreams.iteye.com/blog/2241203
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzM4ODE2OTI0_size_16_color_FFFFFF_t_70 1]: /images/20211227/5fc07d64660847a4aa1b50287ff943aa.png