格雷码问题：输出当输入为n时的格雷码

梦里梦外; 2023-01-09 12:55 135阅读 0赞

**1、写出n=5时的格雷码，要求写出求解过程中变量的变化过程以及求解结果**  
当n=5时，格雷码为：  
00000 00001 00011 00010 00110 00111 00101 00100 01100 01101 01111 01110 01010 01011 01001 01000 11000 11001 11011 11010 11110 11111 11101 11100 10100 10101 10111 10110 10010 10011 10001 10000  
当n=5时，需要递归调用n=4时的格雷码，同理，当n=4时需调用n=3时的格雷码，并以此类推，当要求n=5时的格雷码，则需递归调用出n小于5时的格雷码，如下图所示：  
![在这里插入图片描述][20210121142059118.png]  
**2、写出算法分析过程，试编写程序求输入n时对应的格雷码，并分析算法的时间复杂度**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20210121142211416.png]

package grayCode;
    import java.util.Arrays;
    import java.util.Scanner;
    public class GrayCode { 
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner in = new Scanner(System.in);  	
    		System.out.println("请输入n：");
        	int n = in.nextInt(); 
        	in.close();
        	String[] codes = new String[(int) Math.pow(2, n)];
        	codes = GrayCodeMethod(n);
        	System.out.println("n="+n+"时的格雷码为： "+Arrays.toString(codes));
    	}
    	
    	public static String[] GrayCodeMethod(int n) { 
        	//2的n次方的数组长度
        	String[] graycode = new String[(int) Math.pow(2, n)];
        	if(n == 1) { 
        		graycode[0] = "0";
        		graycode[1] = "1";
        		return graycode;
        	}
        	
        	String[] last = GrayCodeMethod(n-1); //递归调用之前的格雷码
        	System.out.println("n="+(n-1)+"时的格雷码："+Arrays.toString(last));
        	
        	for(int i = 0; i < last.length; i++) {  //循环添加0和1
        		graycode[i] = "0" + last[i];
               //注意对称
        		graycode[graycode.length - 1 - i] = "1" + last[i]; 
        	}
        	return graycode;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70 1]  
如有错误还请指正。

[20210121142059118.png]: /images/20221119/04e72c0c67af42c0b7ce0e709dbf421a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70]: /images/20221119/f0893de9ebff48108afde180b9b9c9a1.png
[20210121142211416.png]: /images/20221119/6528edaecf5c4ec4b5b594cc27ad2e7d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70 1]: /images/20221119/08b5d474b71145fd9151b6b78a94ff3b.png