【算法】格雷码问题

  1.问题描述

对于给定的正整数n，格雷码为满足如下条件的一个编码序列：

(1) 序列由2n个编码组成，每个编码都是长度为n的二进制位串。

(2) 序列中无相同的编码。

(3) 序列中位置相邻的两个编码恰有一位不同。

例如：n=2时的格雷码为：{00, 01, 11, 10}。

设计求格雷码的递归算法并实现。

 2. 具体要求

输入的第一行是一个正整数m，表示测试例个数。接下来几行是m个测试例的数据，每个测试例的输入数据由一行组成，用一个正整数n (n<=20)，表示格雷码的位数。

输出：对于每个测试例输出2n行，表示2n个长度为n的格雷码。第一行为最长递增子序列的长度，第二行为最长递增子序列，整数之间用一个空格隔开。两个测试例的输出数据之间用一个空行隔开。

3. 测试数据

如, 输入：
2

4

5

输出：0 0 0 0

0 0 0 1

0 0 1 1

0 0 1 0

0 1 1 0

0 1 1 1

0 1 0 1

0 1 0 0

1 1 0 0

1 1 0 1

1 1 1 1

1 1 1 0

1 0 1 0

1 0 1 1

1 0 0 1

1 0 0 0

     

0 0 0 0 0

0 0 0 0 1

.

.

.


4、程序实现
 1import java.io.*;
 2import java.math.*;
 3public class Exc2
 4{
 5    public static void main(String[] args) throws Exception
 6    {
 7        Exc2 yeyunce=new Exc2();
 8        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
 9        System.out.println("请输入测试例个数:");
10        String str=br.readLine();
11        int m=Integer.parseInt(str);
12        yeyunce.Test(m);
13    }
14
15    public static String[] GeLeiMa(int n)
16    {
17        double num=Math.pow(2,n);
18        String[] s=new String[(int)num];
19        if(n==1)
20        {
21            s[0]="0";
22            s[1]="1";
23        }
24        else if(n>1)
25        {
26            String[] tm=GeLeiMa(n-1);
27            for(int i=0;i<tm.length;i++)
28            {
29                s[i]="0 "+tm[i];
30                s[2*(tm.length)-1-i]="1 "+tm[i];
31            }
32        }
33        return s;
34    }
35    public void Test(int m)
36    {
37        int[] is=new int[m];
38        for(int i=0;i<m;i++)
39        {
40            try
41            {
42                BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
43                String str=br.readLine();
44                int d=Integer.parseInt(str);
45                is[i]=d;
46            }
47            catch(IOException e)
48            {
49                System.out.println(e);
50            }
51        }
52        for(int h=0;h<m;h++)
53        {
54            System.out.println();
55            String[] glm=GeLeiMa(is[h]);
56            for(int k=0;k<glm.length;k++)
57            {
58                System.out.println(glm[k]);
59            }
60        }
61    }
62}
5、运行结果
运行结果

posted on 2009-04-11 18:46 intrl 阅读(1273) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法

只有注册用户登录后才能发表评论。
<2009年4月>
日一二三四五六
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

导航

统计

随笔分类(55)

随笔档案(34)

网址收藏

资源下载

随笔导航

搜索

最新评论

阅读排行榜

评论排行榜