算法设计与分析课程设计题目:Gray码的分治构造算法专业:网络工程班级:学号:姓名:计算机工程系2012年11月16日一、算法问题描述Gray码是一个长度为的序列。序列中无相同元素,每个元素都是长度为n位的串,相邻元素恰好只有1位不同。用分治策略设计一个算法对任意的n构造相应的Gray码。二、算法问题形式化表示用分治算法构造Gray码的问题可形式化地表示如下: n位Gray码=三、期望输入与输出 输入:以(0,1)串为例,输入元素的宽度n输出:得到长度为的Gray码序列输入输出长度(位)(0,1)串n=101n=200011110n=30000010110101********** 四、算法分析与步骤描述 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<b/2;i++){ arr[i][n-1]=0;//若宽度大于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<b;k++)//再将(n-1)位的Gray码逆序后, //填入目标码字的低半部分 for(intj=0;j<n-1;j++) arr[k][j]=arr[b-k-1][j]; }五、问题实例及算法运算步骤 定义序列中每个元素的位数称为元素的“宽度”。 下面给出一组宽度为4的Gray码,并以此为例,对它的编码规律进行分析。 如下图,对于宽度为4的Gray码,除最高位以外,虚线①的上下两侧是对称的,对称的两组码字恰好均是宽度为3的Gray码,并且虚线①上方最高位全为“0”
格雷码Gray的分治构造算法 来自淘豆网m.daumloan.com转载请标明出处.
