注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

G G I C C I

 
 
 

日志

 
 

递归与分治策略之格雷码 (C++实现)  

2012-04-26 00:01:55|  分类: 算法分析 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1. 格雷码的基本知识链接

维基百科:http://en.wikipedia.org/wiki/Gray_code

百度百科:http://baike.baidu.com/view/358724.htm

简单概括:Gray码是一个长度为 2n 的序列。序列中无相同的元素,每个元素都是长度为 n 位的串, 相邻元素恰好只有 1 位不同。

2. 算法分析

n = 0 的情况:

0
1

n = 1 的情况:

00
01
11
10

n = 2 的情况:

0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000

观察 n = 2 的情况 与 n = 1 的情况的关系:

gray

可见左侧黑灰色彩覆盖的部分为 n = 1 的情况下的Gray码(00,01,11,10),右侧彩色覆盖的部分同样也是 n = 1 情况下的Gray码,只不过红色覆盖的部分为(00,01,11,10),而蓝色覆盖的部分为(10,11,01,00 即是逆序的)。

简单猜测:n = k ( k > 0 ) 情况下的Gray码由两部分组成,左侧部分是 n = k – 1 情况下的 Gray 码(顺序),每一个码带着 n = k – 1 情况下的所有Gray码(如 00 带着 00,01,11,10),而且有顺序和逆序的交替变化。

递归与分治策略之格雷码 (C++, Java 实现) - ___________杰 - __________Ggicci
 
 

观察验证:n = 1 时,用简单猜测可以从 n = 0 得到对应的格雷码序列;n = 3 时,同样可以从 n = 2 得到对应的格雷码序列。

3. 示例代码

C++版本,这个版本只是为了说明思想,具体实现太过简单,不适合 n 太大的情况:

   1: /*********************************
   2:  * Author   Ggicci               *
   3:  * QQ       854032390            *
   4:  * Title    Gray Code Generation *
   5:  *********************************/
   6:  
   7: #include <iostream>
   8: #include <string>
   9: #include <vector>
  10: using namespace std;
  11:  
  12: vector<string>* grayCode(int n);
  13:  
  14: int main()
  15: {
  16:     //把生成的Gray码序列存放到result向量里面
  17:     vector<string> *result = grayCode(2);
  18:     vector<string>::iterator iter = result->begin();
  19:     while(iter != result->end()) //输出序列
  20:     {
  21:         cout << *iter << endl;
  22:         iter++;
  23:     }
  24:     //清理内存
  25:     result->clear();
  26:     delete result;
  27:     return 0;
  28: }
  29:  
  30: vector<string>* grayCode(int n)
  31: {
  32:     vector<string> *vec = new vector<string>();
  33:     //分治, 如果 n = 0 只需返回 n = 0 情况下的最简单的Gray码序列 0 和 1
  34:     if(n == 0)
  35:     {
  36:         vec->push_back("0");
  37:         vec->push_back("1");
  38:     }
  39:     //否则的话用 n-1 情况下的Gray码序列生成 n 情况下的序列
  40:     else
  41:     {
  42:         //把 n - 1 情况下的Gray码序列先存放在sub向量里面
  43:         vector<string> *sub = grayCode(n-1);
  44:         vector<string>::iterator iter, sub_iter;
  45:         vector<string>::reverse_iterator sub_iter_reverse;
  46:         iter = sub->begin();
  47:         //reverse 标志右边部分是否需要逆序排列
  48:         bool reverse = false;
  49:         while(iter != sub->end())
  50:         {
  51:             if(reverse)
  52:             {
  53:                 reverse = false;
  54:                 for(sub_iter_reverse = sub->rbegin(); sub_iter_reverse != sub->rend(); sub_iter_reverse++)
  55:                 {
  56:                     //*iter + *sub_iter_reverse 为两个字符串的连接操作
  57:                     //比如当n=2时,sub里面存放n=1情况下的Gray码序列(00,01,11,10)
  58:                     //那么在左边部分是01的时候需要逆序排列右侧的序列
  59:                     //把0110,0111,0101,0100存放到vec中
  60:                     vec->push_back(*iter + *sub_iter_reverse);
  61:                 }//end for
  62:             }//end if
  63:             else
  64:             {
  65:                 reverse = true;
  66:                 for(sub_iter = sub->begin(); sub_iter != sub->end(); sub_iter++)
  67:                 {
  68:                     vec->push_back(*iter + *sub_iter);
  69:                 }//end for
  70:             }//end else
  71:             iter++;
  72:         }//end while
  73:         //内存清理
  74:         sub->clear();
  75:         delete sub;
  76:     }
  77:     return vec;
  78: }
  评论这张
 
阅读(490)| 评论(0)
推荐

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017