这是一个创建于 358 天前的主题，其中的信息可能已经有所发展或是发生改变。
最近想到一个算法题，和生活有关的。
出租屋最近换了密码锁，6 位密码。实际操作中，在密码前后输入多位其他数字，也能验证成功。既 prefix + password + suffix 的输入，也能解锁。
那么问题来了，6 位密码最多输入多少次能破解？ 假设密码锁的判断方式是最近输入的 12 位字符，既 length(prefix + password + suffix) = 12
没有思路，请教诸君。
第 1 条附言 · 358 天前
题意没有表达清楚，应该是：最多试多少次一定破解。
第 2 条附言 · 358 天前
在换种方式描述一下问题。
一次输入 12 位，可以拆分位 7 个连续的 6 位密码，即分别为 1-6 ，2-7 ，3-8……7-12 位。意味着能同时验证 7 个密码。
有没有一种算法，能够计算出，最少尝试多少次 12 位密码，就一定能试出密码。
一次输入 12 位，可以拆分位 7 个连续的 6 位密码，即分别为 1-6 ，2-7 ，3-8……7-12 位。意味着能同时验证 7 个密码。
有没有一种算法，能够计算出，最少尝试多少次 12 位密码，就一定能试出密码。
第 3 条附言 · 357 天前
算法问题抽象：
十二位数字用字符串形式表示为：000000000000-999999999999 。六位数用字符串形式表示为：000000-999999 。
一个十二位数字可以拆分为七个六位数，例如 12345789012 拆分为 123456, 234567, 345678, 456789, 567890, 678901, 789012 七个六位数，即一个十二位数包含七个六位数。
请问，最少需要多少个十二位数字，包含所有 000000-999999 的六位数。
十二位数字用字符串形式表示为：000000000000-999999999999 。六位数用字符串形式表示为：000000-999999 。
一个十二位数字可以拆分为七个六位数，例如 12345789012 拆分为 123456, 234567, 345678, 456789, 567890, 678901, 789012 七个六位数，即一个十二位数包含七个六位数。
请问，最少需要多少个十二位数字，包含所有 000000-999999 的六位数。
 |
1
nerkeler 358 天前 via Android
所有排列的情况减去 六位正确密码在十二位从头滑动到末尾的情况？
|
 |
3
nuk 358 天前
假设是 12 位密码，然后容许的 12 位密码有 10 的 6 次方*6 个，基本上就是试 6 次密码的 1/6 ，就是 1/10^5 几率
|
 |
5
smdbh 358 天前
感觉是，大概在 1/6 * 10^6 多一点
|
|
7
smdbh 358 天前
@smdbh 12 位数字，一次可以试 0-6 ，1-7 ，2-8 ，。。。7-12 ，7 个密码，试过的就 hash 查表标记。但这个排列是有相关性的，到后面可能会有重复的，一次查不满 7 个
|
 |
9
TongNianShanHe 358 天前 via Android
感觉好像 leetcode 752
|
 |
10
acr0ss OP @TongNianShanHe 谢谢回复，看了题目，不一样但有启发。可以用广度优先来做，但是时间复杂度数量级是 10**12 ，约等于不行。
|
 |
12
NoOneNoBody 358 天前  1
只要直接输入密码也能打开，就意味着真密码前后的几位，对防暴力破解是没有意义的，它只是对于写下来，即使被别人看到了，也难以猜到而已
例如真密码是六个 0 ，000000+六个任意数字能打开不？能打开的话，那第一次就成功了，意味着最大次数就只和真密码有关 |
 |
13
geelaw 358 天前
你需要搜索的是 de Brujin 序列 (sequence)
|
 |
14
jjyy1008 358 天前 via iPhone
@NoOneNoBody 这才是正解！楼上的钻书里去了？门禁密码锁设置前缀和后缀的目的就是为了防偷窥用的，哪怕背后有人瞟到了一部分真正密码或者全部真正密码，你接着瞎按一串再确认，这样对防人肉破解很有效。
|
 |
15
huibosa 358 天前
如果想自己编程实现这种机制该怎么做呢，比如强制服务端只存储密码的哈希，如果想达到最优性能需要用到哪些算法呢（当然题主讨论的密码锁应该用的不是这种方式）
|
 |
16
xuhai951753 358 天前
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); |
|
17
acr0ss OP @NoOneNoBody 按我的体重描述，“000000+六个任意数字”可以打开，对应位 len(prefix)=0, (suffix)=6 。如果知道真密码，那一次就行。我只是借着这个场景，实际想要表达的问题是：需要多少个 12 位，就能穷举 6 位数的所有可能。
|
|
18
acr0ss OP @xuhai951753 不理解，能否解释一下？问题是求次数，但为什么结果是一个小 1 的小数？
|
|
20
NoOneNoBody 357 天前
@acr0ss #17
不用想那么多，假设身旁没有人，你会前面多按几个无用的数字么？你只会按 6 位，所以密码就是前 6 位匹配 别人来暴力破解，也是前 6 位对了就可以了 所以，决定因素就是对方是否知道密码为 6 位，知道的话，他也不会那么傻试第 7 位，如果不知道，只能硬着头皮输入 12 位的话，那就是穷举到“密码+000000”的位置结束，按这个思路解 如果已经知道 12 个数字，不知道顺序，就是这 12 个数字的组合，按某个顺序把其结果排序，第一个出现前六位匹配的位置结束 如果知道 12 个数字，且知道顺序，那就更简单了，每次错误去掉第一个数，到成功时，最多应该仅仅只是 prefix 的长度而已，所以，这说明无论多少位，还是不要让别人知道顺序为好，这是最重要的 从上面几点看，穷举后排序的方式是很重要的，它影响了到达“前六位匹配”的距离，从电脑角度看都是 0-->9 正序，但实际意义上这个排序方式是不定的，所以就看题面“最多”是怎么理解了，它是表示求最短距离，还是求正序穷举个数，还是有区别的，“中文博大精深” |
|
21
acr0ss OP |
|
22
NoOneNoBody 357 天前
@acr0ss #20
好吧，我直接给你结果就是，你六位密码是多少，就是多少次 假设你的密码是 123456 ，结果就是 123456+1 次 000000000000 开门失败 000000000001 开门失败 ... 000000123455 开门失败 000000123456 开门成功 这个过程就是 123456 次，再加上 12 个 0 一次 这样能明白么？还是我理解错了题意？ |
|
23
TongNianShanHe 357 天前
@acr0ss 我的锅，我没有阐明“只需要猜六位数”的前提条件，昨天就是因为想到了这个前提条件，才会想到这道题的（上面也有老哥提出来了）
|
|
24
TongNianShanHe 357 天前
@NoOneNoBody 本质没错，他的意思是密码前后加无意义数字，其实只需要把前面六个 0 的三个 0 ，移动到最后就行了
|
|
25
TongNianShanHe 357 天前
@NoOneNoBody @acr0ss 哦，我重新看了一下补充，当我没说，如果我没理解错的话，这个可以用滑动窗口？还有楼上说的 de Brujin 序列？（其他其他大佬的解答）
|
 |
26
yw9381 357 天前 via Android
我理解你这个要表达的是
想要完全包含所有的 6 位数。最少需要多少个 12 位数才可以做到 最差情况为不复用任何数字。即一个 12 位当成两个 6 位。也就是需要 50w 个 最优情况应该就是尽可能的复用数字。算法这块我不太懂。但感觉应该可以把尝试次数压到 10w 以内 |
|
27
acr0ss OP |
|
28
acr0ss OP @yw9381 是的，就是想表达这个问题。
首先想到的上界肯定是 50W ，但也肯定能往下缩减。 由于一个十二位能表示七个六位，所以下界肯定是 10**6 / 7 ，当然这个应该是达不到的。 究竟怎么求具体值，我没有算法思路，就连暴力算法也没思路。 |
|
30
geelaw 356 天前 1
@geelaw #13
@acr0ss #29 de Bruijn 序列 B(k, n) 的定义是 { 0, 1, ..., k-1 } 的有限序列 X = X[1]X[2] ... X[L] 使 L >= n 且所有 { 0, 1, ..., k-1 }^n 的元素都在 X' = X[1] X[2] ... X[L] X[1] X[2] ... X[n-1] 恰好作为子串出现一次。已经知道 B(k, n) 的长度是 L = k^n ，注意 X ' 长度为 n 的子串恰好有 L = k^n 个，且 { 0, 1, ..., k-1 }^n 恰好就有 k^n 个元素。 在你的情况里 k=10, n=6 ，但 de Bruijn 序列并不是你直接要的答案，不过已经非常接近了。 你希望寻找一系列长度是 12 的串 Y(1), ..., Y(z) 使得诸 Y(i) 的所有长度为 6 的子串覆盖了 { 0, ..., 9 }^6 ，很明显 z >= ceiling(10^6/7) = 142858 ，而取 Y(i) = X'[7(i-1)+1] ... X[7(i-1)+12] 1 <= i <= 142857 Y(142858) = X'[7(142858-1)+1 = 10^6] ... X'[10^6+(10-1)] 0 0 则诸 Y(i) 的所有长度为 6 的子串当然就包括了 X' 所有长度为 6 的子串，后者就是所有长度为 6 的串。这说明需要的 z 可以是 142858 。 暂且称上面长度为 12 的串是“窗口”。类似地，可以算出密码字符有 k 个，密码长度是 n ，窗口长度是 m 的时候需要的最小的窗口数就是 ceiling(k^n/m)。 计算最小窗口数和计算这一系列窗口是两回事儿，不过后者也不难，de Bruijn 序列有算法可以生成，再练习一下使用搜索引擎的能力就好。 |
|
32
NoOneNoBody 356 天前
好吧，是我读错题了
12 个抽取连续 6 个连续的，只有 7 种可能，每种可能都能满足一个 10**6 10**6/7≈142857.14285714287 |
Select Language