分治法求解格雷码

分治法 简介： 将一个大的问题分解成为一些较小的子问题，分别求解各个子问题，然后将各个子问题合并就可以得到问题的解。 分治法和递归的思想非常类似，分治法一般是划分为 若干个相等 的子问题，而递归则一般是 逐层减一 得到最简单的子问题，接着再一层一层返回。 格雷码（Grey） Grey码是一个长度为2ⁿ的序列，序列中无相同元素，且每个元素都是长度为n的二进制位串，相邻元素恰好只有1位不同。例如长度为2³的格雷码为(000,001,011,010,110,111,101,100)。设计分治算法对任意的n值构造相应的Grey码。 输入 每个元素的长度值n。 输出 将所有相应的Grey码分行输出，即每一行输出一个二进制位串。 例如：3 输出： 3位格雷码 000001011010110111101100 基本思想：       应用分治法进行求解； （1）通过观察不难发现n位格雷码有2^n；（2）每次将序列划分为两个序列，例如第i次划分，二进制位串上的第i位上分别为0和1；（3）当划分后剩下一位时，每一个格雷码的最后一位根据上一个格雷码决定，并输出该格雷码；（4）合并，将各个子问题合并起来，该问题没有明显体现，划分后的每一个二进制位串组合起来就是n位格雷码 算法中心实现： int Gery(int n,int t){//格雷码长度为t=num int i,j; if(n>1) Gery(n-1,t); /*如果上次最末尾为0，此次变为1*/ if(a[n-1]==0) a[n-1]=1; /*如果上次最末尾为1，此次变为0*/ else a[n-1]=0; /*输出此次格雷码*/ for(int i=t-1;i>=0;i--) printf("%d",a[i]); printf("\n"); if(n>1) Gery(n-1,t); } 注意：int Gery（int n ,int t ）中n代表 第几次划分 ,t代 表格雷码的位数 ，其中从 n变为n-1 表示将 求解2^n个格雷码变为2^(n-1)个格雷码 。