欢迎访问
讨论版列表 - 面试求职 - 主题数: 42 | 文章数: 46 | 管理员: (无)

面试求职

版面 | 文摘区 | 马克区

文章数: 1 | 分页: << 1 >>
admin
[回复] [修改] [删除] [返回版面] 1  
作者: admin, 讨论版: 面试求职, 发表时间: 2014-01-04 20:40:19 PST
标题: De Bruijn sequence
关键字:

4位的密码,遍历完所有0000-9999的可能性后,锁就能打开。

把所有的可能密码连接在一起成为总长度为4*10000=40000的string。这个string的某
连续四位肯定能够能解开锁。

上面的string不是唯一的。比如实际密码是2345,string的某5位是12345,1234是一个
组合,2345是另一个组合。也就是说他们共享了一些数字。导致总长度降低。

现在求一个最短的string,其中某连续4位一定是可以解开锁的密码。

解答见: De Bruijn sequence. 简而言之, 构造一个De Buijn graph, 从一个顶点出发, 走一个Euclerian cycle(访问每一条边一次, 最后返回出发点)即可.


--

最后修改: admin on 2014-01-05 01:36:20 PST
※ 来源: homecox.com  [来自: 66.]


Reply

Please log in first.