[请教] 生活中的算法题：密码尝试次数

[acr0ss]

最近想到一个算法题，和生活有关的。

出租屋最近换了密码锁，6 位密码。实际操作中，在密码前后输入多位其他数字，也能验证成功。既 prefix + password + suffix 的输入，也能解锁。

那么问题来了，6 位密码最多输入多少次能破解？ 假设密码锁的判断方式是最近输入的 12 位字符，既 length(prefix + password + suffix) = 12

没有思路，请教诸君。

[nerkeler]

所有排列的情况减去 六位正确密码在十二位从头滑动到末尾的情况？

[acr0ss]

@nerkeler 我题意没说清，应该是最多试多少次一定破解。 你这算法肯定超过 6 位密码 10^6 上界了。

[nuk]

假设是 12 位密码，然后容许的 12 位密码有 10 的 6 次方*6 个，基本上就是试 6 次密码的 1/6 ，就是 1/10^5 几率

[acr0ss]

@nuk 我是算次数，不是概率。而且你这算法很奇怪，逻辑很跳跃不知道是什么的概率。

[smdbh]

感觉是，大概在 1/6 * 10^6 多一点

[acr0ss]

@smdbh 有什么思路吗？ brutal force 也行

[smdbh]

@smdbh 12 位数字，一次可以试 0-6 ，1-7 ，2-8 ，。。。7-12 ，7 个密码，试过的就 hash 查表标记。但这个排列是有相关性的，到后面可能会有重复的，一次查不满 7 个

[acr0ss]

@smdbh 如果要暴力枚举，计算量是 10**12 ，这个机器扛不住。而且类似贪心，不一定是最少的次数（最优解）。

[TongNianShanHe]

感觉好像 leetcode 752

[acr0ss]

@TongNianShanHe 谢谢回复，看了题目，不一样但有启发。可以用广度优先来做，但是时间复杂度数量级是 10**12 ，约等于不行。

[acr0ss]

@acr0ss 又想了一下，bfs/dfs 的初始状态没法确定，visited 数组得按路径维护，内存消耗太大。

[NoOneNoBody]

只要直接输入密码也能打开，就意味着真密码前后的几位，对防暴力破解是没有意义的，它只是对于写下来，即使被别人看到了，也难以猜到而已
例如真密码是六个 0 ，000000+六个任意数字能打开不？能打开的话，那第一次就成功了，意味着最大次数就只和真密码有关

[geelaw]

你需要搜索的是 de Brujin 序列 (sequence)

[jjyy1008]

@NoOneNoBody 这才是正解！楼上的钻书里去了？门禁密码锁设置前缀和后缀的目的就是为了防偷窥用的，哪怕背后有人瞟到了一部分真正密码或者全部真正密码，你接着瞎按一串再确认，这样对防人肉破解很有效。

[huibosa]

如果想自己编程实现这种机制该怎么做呢，比如强制服务端只存储密码的哈希，如果想达到最优性能需要用到哪些算法呢（当然题主讨论的密码锁应该用的不是这种方式）

[xuhai951753]

function recur(pre, times) {
const cur = times === 0 ? 1 / (9 ** 6) : (1 - pre) / 9;

return times < 6 ? (cur + recur(cur, times + 1)) : cur;
}

recur(0, 0);

[acr0ss]

@NoOneNoBody 按我的体重描述，“000000+六个任意数字”可以打开，对应位 len(prefix)=0, (suffix)=6 。如果知道真密码，那一次就行。我只是借着这个场景，实际想要表达的问题是：需要多少个 12 位，就能穷举 6 位数的所有可能。

[acr0ss]

@xuhai951753 不理解，能否解释一下？问题是求次数，但为什么结果是一个小 1 的小数？

[acr0ss]

@jjyy1008 不知道可以不回答，不用趾高气扬、指手划脚。

[NoOneNoBody]

@acr0ss #17
不用想那么多，假设身旁没有人，你会前面多按几个无用的数字么？你只会按 6 位，所以密码就是前 6 位匹配
别人来暴力破解，也是前 6 位对了就可以了

所以，决定因素就是对方是否知道密码为 6 位，知道的话，他也不会那么傻试第 7 位，如果不知道，只能硬着头皮输入 12 位的话，那就是穷举到“密码+000000”的位置结束，按这个思路解
如果已经知道 12 个数字，不知道顺序，就是这 12 个数字的组合，按某个顺序把其结果排序，第一个出现前六位匹配的位置结束
如果知道 12 个数字，且知道顺序，那就更简单了，每次错误去掉第一个数，到成功时，最多应该仅仅只是 prefix 的长度而已，所以，这说明无论多少位，还是不要让别人知道顺序为好，这是最重要的

从上面几点看，穷举后排序的方式是很重要的，它影响了到达“前六位匹配”的距离，从电脑角度看都是 0-->9 正序，但实际意义上这个排序方式是不定的，所以就看题面“最多”是怎么理解了，它是表示求最短距离，还是求正序穷举个数，还是有区别的，“中文博大精深”