From 我的房门锁 To 算法题?

[sennes]

http://senneszi.com/post/article/2015-11-26

我不是搞算法的，然后这个题，不知道从哪里开始想。

到底怎样才能没冗余的去破解这样一个串行序列检测。

是不是有什么算法能得到这个最优解序列呢?

[sennes]

是不是应该 move 到"程序员"那边会比较好?

[ybao]

这个题目有太多不明细的地方了，比如：有多少扇门需要设置的，或者说，密码的最短多少，最长多少等等。。

[sennes]

@ybao hi ，我觉得应该挺清楚的。
有多少扇门需要设置的 → "使得任意房门都能打开"
密码的最短多少，最长多少 → "用户设定的房门密码不超过 16 位数字"

[mathcoder23]

真心脑洞大开啊。我假设最高是二位依然没有思路，感觉和动态规划，代数系统那方面有点儿关系啊。。。如果有解，希望通知哇。

[popo233]

想了一下两位密码的情况，想到了以前看过的七桥问题。于是这个问题可以转化为：

一个圆上 10 个点，从某点出发不间断地画有向的线（起点终点都在点上），要求最后每两个点之间都有来回两条，每个点还得有个返回自身的，求画出这个图形的最短线段数

如果能保证每种线段都只画一次，肯定最少了。假设可以，那么因为每个点上都有 10 条进入的， 10 条出去的，也就是“奇点”个数为 0 。根据七桥问题的那个结论，应该是可以一笔画下来的。

列一下 4 个数的：
11213142233244341 ，共 4*4+1 位
6 个数的：
1121314151662636465545352232443342561 ，共 6*6+1 位
10 个数应该需要 101 位，不列了，套路一样。


密码位数更多的情况暂时不考虑了.. 有勇士可以试试。

[exch4nge]

@popo233 感谢思路！自己想半天也没想出来。

具体位数的话我来补充下，假设有 m 个字符集 n 位密码的话，在 m 为偶数的情况下，需要 pow(m, n) + n - 1 位。奇数情况的话肯定比这更多……

[exch4nge]

额，再想了想好像没法把问题映射到七桥问题吧…… 上述回复先无视掉吧……

[ryrubyy]

话说 MIUI 锁屏解锁是不是也是串行序列检测呢？

[zhly]

https://en.wikipedia.org/wiki/De_Bruijn_sequence

[wy315700]

@popo233
不对吧，你这个 4 位数的 不包含 1234 这个序列啊

[skydiver]

@zhly 哈哈哈原来问题早就有解了……

[Pan940425]

@wy315700 认真看嘛，人家说的“ 4 位数”是指数字只有“ 1,2,3,4 ”四个数，而最大的位数 @popo233 在回复的第一句就说了，“两位密码的情况”，所以需要有的组合只有 11,12,13,14,21,22,23,24,31,32,33,34,41,42,43,44 共计 16 种，而 @popo233 提供的答案“ 11213142233244341 ”中，以上组合均包含。