[回复]
[修改] [删除]
[返回版面]
|
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.]
|
|
|