当前时区为 UTC + 8 小时



发表新帖 回复这个主题  [ 12 篇帖子 ] 
作者 内容
1 楼 
 文章标题 : 一道Google算法题:n位编码的海明码生成
帖子发表于 : 2008-04-22 9:01 
论坛管理员

注册: 2005-03-27 0:06
帖子: 10116
系统: Ubuntu 12.04
送出感谢: 7
接收感谢: 128
来源: http://www.blogjava.net/copydogcn/archi ... 94256.html

写一个算法生成n位编码的编码串(结果有多种,任意一种都可以接受)并且符合如下条件:相邻的两个编码之间有且只能有一位不同,并给出时间与空间复杂度

比如 2位的二进制的编码生成的编码串:00 01 11 10
比如 3位的二进制编码生成的编码串:001 011 111 101 100 110 010 000


页首
 用户资料  
 
2 楼 
 文章标题 :
帖子发表于 : 2008-04-22 20:43 
头像

注册: 2008-02-18 0:25
帖子: 424
送出感谢: 0 次
接收感谢: 0 次
什么是时间与空间复杂度?


_________________
图片


页首
 用户资料  
 
3 楼 
 文章标题 :
帖子发表于 : 2008-04-24 18:32 
头像

注册: 2007-11-20 20:12
帖子: 16
地址: 中国北京
送出感谢: 0 次
接收感谢: 0 次
这个题有点意思


页首
 用户资料  
 
4 楼 
 文章标题 :
帖子发表于 : 2008-04-25 12:20 
头像

注册: 2007-04-16 15:34
帖子: 120
送出感谢: 0 次
接收感谢: 0 次
递规 :lol: :lol: :lol: :lol:
代码:
public class HaiMingBin {

   public HaiMingBin() {
      // TODO Auto-generated constructor stub
   }

   /**
    * @param args
    */
   public static void main(String[] args) {
      HaiMingBin hm = new HaiMingBin();
      int time = 13;
      int m = exp(2, time);
      System.out.println(m);
      int[] arr = new int[m];
      hm.calc(arr, time);
      for (int i = 0; i < m; i++) {
         System.out.println(cvtBinNum(arr[i], time));
      }
   }

   public void calc(int[] arr, int time) {
      if (time == 0) {
         arr[0] = 0;
         return;
      }
      int m = exp(2, time);
      calc(arr, time - 1);
      for (int i = 0; i < m / 2; i++) {
         arr[m - 1 - i] = (m / 2) | arr[i];
      }
   }

   public static int exp(int num, int time) {
      int k = 1;
      int t = time;
      while (t-- > 0) {
         k *= num;
      }
      return k;
   }

   public static String cvtBinNum(int num, int digit) {
      StringBuffer sb = new StringBuffer();
      for (int i = digit - 1; i >= 0; i--) {
         if ((exp(2, i) & num) != 0) {
            sb.append('1');
         } else {
            sb.append('0');
         }
      }
      return sb.toString();
   }

}


页首
 用户资料  
 
5 楼 
 文章标题 :
帖子发表于 : 2008-04-25 12:21 
头像

注册: 2006-07-02 11:16
帖子: 12522
地址: 廣州
送出感谢: 0 次
接收感谢: 8
忘记了, 2007NORP初赛倒数第二题


_________________
^_^ ~~~
要理解递归,首先要理解递归。

地球人都知道,理论上,理论跟实际是没有差别的,但实际上,理论跟实际的差别是相当大滴。


页首
 用户资料  
 
6 楼 
 文章标题 :
帖子发表于 : 2008-04-25 12:43 
头像

注册: 2006-07-02 11:16
帖子: 12522
地址: 廣州
送出感谢: 0 次
接收感谢: 8
代码:
#!/usr/bin/python
import sys, string

def Genhm(n):
    if n <= 0 :
        yield ''
    else:
        tmp = []
        for i in Genhm(n-1):
            yield '0' + i
            tmp.append(i)
        while tmp : # is not empty
            yield '1' + tmp.pop()

if '__main__' == __name__ :
    print sys.argv[1]
    for i in Genhm(string.atoi(sys.argv[1])):
        print i


生成器能反转用吗, 现在只好用一个stack了..

时 O(2^n) 空 O(2^n)


_________________
^_^ ~~~
要理解递归,首先要理解递归。

地球人都知道,理论上,理论跟实际是没有差别的,但实际上,理论跟实际的差别是相当大滴。


最后由 BigSnake.NET 编辑于 2008-04-25 13:32,总共编辑了 2 次

页首
 用户资料  
 
7 楼 
 文章标题 :
帖子发表于 : 2008-04-25 13:06 
头像

注册: 2006-07-02 11:16
帖子: 12522
地址: 廣州
送出感谢: 0 次
接收感谢: 8
时间测试

代码:
n       用时
1       0.00s
2       0.00s
3       0.01s
4       0.00s
5       0.00s
6       0.00s
7       0.01s
8       0.01s
9       0.00s
10      0.00s
11      0.01s
12      0.01s
13      0.02s
14      0.03s
15      0.05s
16      0.10s
17      0.20s
18      0.38s
19      0.78s
20      1.57s
21      3.05s
22      5.93s
23      11.81s
24      24.08s
25      48.22s


_________________
^_^ ~~~
要理解递归,首先要理解递归。

地球人都知道,理论上,理论跟实际是没有差别的,但实际上,理论跟实际的差别是相当大滴。


页首
 用户资料  
 
8 楼 
 文章标题 : Re: 一道Google算法题:n位编码的海明码生成
帖子发表于 : 2009-07-20 7:34 

注册: 2008-02-27 8:15
帖子: 2
送出感谢: 0 次
接收感谢: 0 次
PHP语言解法
代码:
function go($n)
{
    if (!is_int($n) || $n < 1) return;
    if ($n-- == 1) return array('0', '1');
    return array_merge(array_map(create_function('$item', 'return "0" . $item;'), go($n)), array_map(create_function('$item', 'return "1" . $item;'), array_reverse(go($n))));
 
}
print_r(go(4));


页首
 用户资料  
 
9 楼 
 文章标题 : Re: 一道Google算法题:n位编码的海明码生成
帖子发表于 : 2009-07-20 8:19 
头像

注册: 2008-07-27 8:51
帖子: 711
地址: 广西玉林|广东深圳
系统: Ubuntu/Windows
送出感谢: 1
接收感谢: 3
代码:

1位
real   0m0.040s
user   0m0.020s
sys   0m0.004s

2位
real   0m0.041s
user   0m0.024s
sys   0m0.004s

3位
real   0m0.039s
user   0m0.016s
sys   0m0.012s

4位
real   0m0.041s
user   0m0.024s
sys   0m0.000s

5位
real   0m0.042s
user   0m0.020s
sys   0m0.008s

6位
real   0m0.039s
user   0m0.028s
sys   0m0.004s

7位
real   0m0.039s
user   0m0.020s
sys   0m0.012s

8位
real   0m0.059s
user   0m0.016s
sys   0m0.012s

9位
real   0m0.039s
user   0m0.016s
sys   0m0.016s

10位
real   0m0.040s
user   0m0.024s
sys   0m0.004s

11位
real   0m0.045s
user   0m0.028s
sys   0m0.000s

12位
real   0m0.048s
user   0m0.024s
sys   0m0.012s

13位
real   0m0.056s
user   0m0.036s
sys   0m0.004s

14位
real   0m0.076s
user   0m0.044s
sys   0m0.012s

15位
real   0m0.110s
user   0m0.084s
sys   0m0.008s

16位
real   0m0.183s
user   0m0.160s
sys   0m0.004s




页首
 用户资料  
 
10 楼 
 文章标题 : Re: 一道Google算法题:n位编码的海明码生成
帖子发表于 : 2009-08-23 22:46 
头像

注册: 2007-01-12 22:59
帖子: 192
地址: GDUT
送出感谢: 0 次
接收感谢: 0 次
支持递归~~~
代码:
public class GenHammingCode {

   private static Boolean isAppendLeft;

   public String[] gen(final Integer bitCount) {
      if (bitCount == 1)
         return new String[] { "0", "1" };
      String[] result = new String[2 << bitCount - 1];
      String[] temp = gen(bitCount - 1);
      isAppendLeft = new Random().nextBoolean();
      for (int i = 0; i < temp.length; i++) {
         result[i] = append(temp[i], "0", isAppendLeft);
         result[result.length - 1 - i] = append(temp[i], "1", isAppendLeft);
      }
      return result;
   }

   private String append(String src, String appendStr, Boolean isAppendLeft) {
      return isAppendLeft ? appendStr + src : src + appendStr;
   }

   public static void main(String[] args) {
      System.out.println(Arrays.deepToString(new GenHammingCode().gen(3)));
   }
}


页首
 用户资料  
 
11 楼 
 文章标题 : Re:
帖子发表于 : 2009-10-02 21:01 

注册: 2008-07-15 10:44
帖子: 7
地址: 天津市
送出感谢: 0 次
接收感谢: 0 次
BigSnake.NET 写道:
忘记了, 2007NORP初赛倒数第二题

NOIP2007提高组初赛
格雷码- -
挺经典的一道题= =


_________________
瑶宫寂寞锁千秋,
九天御风只影游。
不如笑归红尘去,
共我飞花携满袖。


页首
 用户资料  
 
12 楼 
 文章标题 : Re: 一道Google算法题:n位编码的海明码生成
帖子发表于 : 2009-10-03 11:32 

注册: 2009-08-04 8:47
帖子: 11
送出感谢: 0 次
接收感谢: 0 次
binary Gray code

代码:
#!/usr/bin/env python

for i in xrange(1 << input()):
   print('%d ' % (i ^ i >> 1))


页首
 用户资料  
 
显示帖子 :  排序  
发表新帖 回复这个主题  [ 12 篇帖子 ] 

当前时区为 UTC + 8 小时


在线用户

正在浏览此版面的用户:没有注册用户 和 1 位游客


不能 在这个版面发表主题
不能 在这个版面回复主题
不能 在这个版面编辑帖子
不能 在这个版面删除帖子
不能 在这个版面提交附件

前往 :  
本站点为公益性站点,用于推广开源自由软件,由 DiaHosting VPSBudgetVM VPS 提供服务。
我们认为:软件应可免费取得,软件工具在各种语言环境下皆可使用,且不会有任何功能上的差异;
人们应有定制和修改软件的自由,且方式不受限制,只要他们自认为合适。

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
简体中文语系由 王笑宇 翻译