格雷码gray的分治构造算法

《格雷码gray的分治构造算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法设计与分析课程设计题目：Gray码的分治构造算法专业：网络工程班级：学号：姓名：计算机工程系2012年11月16日一、算法问题描述Gray码是一个长度为的序列。序列中无相同元素，每个元素都是长度为n位的串，相邻元素恰好只有1位不同。用分治策略设计一个算法对任意的n构造相应的Gray码。二、算法问题形式化表示用分治算法构造Gray码的问题可形式化地表示如下：n位Gray码=三、期望输入与输出输入：以（0,1）串为例，输入元素的宽度n输出：得到长度为的Gray码序列输入输出长度（位）（0,1）串n=101n=200011110n=300000101101011011

2、1101100四、算法分析与步骤描述n位Gray码可由（n-1）位Gray码及1位“0”或“1”组成。因此，最主要的工作是生成（n-1）位的Gray码，这样，就将问题的规模n缩小为（n-1），元素的个数由缩小为个，从而达到简化问题的目的。同时可以利用这个元素构造全部的个元素。具体算法实现中，参数n表示Gray码的宽度，参数b表示元素个数，数组arr[][]用来存储生成的Gray码。算法如下：voidgraycode(intn,intb,intarr[][]){if(n==0)return;for(inti=0;i

3、宽度大于1，则在前一半码字的第n位添加"0"arr[b-i-1][n-1]=1;//在一半码字的第n位添加"1",//如此生成了目标码字的最高位}graycode(n-1,b/2,arr);//接着生成宽度为(n-1)的Gray码，//填写在目标码字的最高部分for(intk=b/2;k

4、例，对它的编码规律进行分析。如下图，对于宽度为4的Gray码，除最高位以外，虚线①的上下两侧是对称的，对称的两组码字恰好均是宽度为3的Gray码，并且虚线①上方最高位全为“0”，下方全为“1”；对于宽度为3的Gray码，除最高位以外，虚线②的上下两侧也是对称的，对称的两组码字恰好均是宽度为2的Gray码，并且虚线②上方最高位同样全为“0”，下方全为“1”。同理，向下推广至Gray码宽度为2和1，向上推广至宽度为5、6、……。可以发现，这种规律对于任意宽度的Gray码都是适用的。这样，总结出Gray码序列的构造规律，即宽度为n的Gray码，共有个元素，前个元素可由宽度

5、为（n-1）的Gray码和第n位的“0”构成，后个元素可由之前生成的经过逆序的（n-1）位的Gray码和第n位的“1”构成。六、算法运行截图七、算法复杂度分析这是一个基于分治思想的算法，利用Gray码具有的自对称性，将问题的规模不断缩小，从而实现Gray码的生成。若用T(n)表示生成宽度为n的Gray码所需要的时间复杂度，则整个算法的时间复杂度可表示为：T(n)=解此递归式可得：T(n)=O(n)。算法的空间复杂度为：O(n)。