Google面经题密码箱问题解法求问

哪位大神可以解释下什么是暴力破解的最短序列？我的理解就是生成0000-9999的一万个数，但是不管用什么序列方法，最坏情况不应该都是把这一万个数过一遍才能知道密码的么?
还是说不同的方法生成下一个数的代价是不一样的？比如类似转轮密码盘从0009拨到0010要拨两次，0010到0011只要一次，然后求序列让生成代价最小？

starcroce 发表于 2016-1-25 15:18
哪位大神可以解释下什么是暴力破解的最短序列？我的理解就是生成0000-9999的一万个数，但是不管用什么序列 ...

首先你要弄明白你面对的是一个神马密码锁，它的特性是这样的：
一个长度为n=4的密码框，一个键盘有k=10个按键，分别是0~9。
你输入0000，系统会验证0000是否是正确密码。
这时候你再输入一个1，不同的密码锁有不同的处理方式
一种会reset，也就是说前面的4个0消失了，你需要继续输入4个数供系统判断。
另一种不会reset，它会验证最近键入的4歌数字，即0001。
我们面对的是后一种。

如果是前一种的话，没啥好想的，破解序列就是4*10000
但是后一种，可以做到长度为10003的破解序列覆盖所有可能的10000个4位数。
题目就是让你找到这个序列。

这里有个贴子说得很清楚：http://xwk.iteye.com/blog/2129621

dietpepsi 发表于 2016-1-26 00:40
首先你要弄明白你面对的是一个神马密码锁，它的特性是这样的：
一个长度为n=4的密码框，一个键盘有k=10 ...

那就是把0000 - 9999看成10000个点，每个点出去可以到10个其他的点，比如abcd -> (bcd0, .., bcd9)，也有10个点 (0abc, .., 9abc) 可以到 abcd。。。
然后问比如从0000出发是否存在一条路径，路过所有其他点各一次？
没刷过ACM的弱渣表示，根据残存的小学奥赛经验，我只能知道这么个路径好像是存在的？具体怎么求出路径应该是DFS加上一些优化吧。。。
sigh碰这题就只能听天由命了。。。

这个题目应该是构造状态做欧拉回路

汉密尔顿回路是NPC，不行的

可以暴力解吧，DFS + Backtracking，不过很慢就是了，但是个可以当场写出的算法。从0000开始，往后添0-9，hashset保存已经产生过得密码，然后往下递归；遇到重复就返回，否则往下递归。

这道题另一个思路是利用AC自动机的思想：
https://zh.wikipedia.org/wiki/AC%E8%87%AA%E5%8A%A8%E6%9C%BA%E7%AE%97%E6%B3%95
如果将所有可能组合generate成一个AC自动机的话，这道题就等价于
1. 利用AC自动机倒数第二层和倒数第一层所有的node以及前向/失配指针，构造出一个图，求这个图的Eular Path
2. 利用AC自动机倒数第一层的所有node，以及前向/失配指针加上倒数第二层的节点（每条边由失配指针+倒数第二层节点+前向指针构成），求这个图的Hamilton Path
用AC自动机的一个好处是，如果词典不等长，AC自动机也可以给出解，只需要类比这个算法，构造出最后一层节点之间最短的边，求Hamilton Path即可
但是无论如何，这题太难了。。。

dietpepsi 发表于 2016-1-25 09:47
我觉得这道题在题意明确的情况下，把所有状态看成点，状态之间的转移看成边是比较自然的。
这样就有两种看 ...

转化为欧拉回路的部分讲得很清楚，感谢

感谢分享～～～学习了～～～