请教一个关于猜测密码的算法题

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 3778 天前的主题，其中的信息可能已经有所发展或是发生改变。

假设有一个n位m进制的密码

每次用一个密码尝试会返回一个结果告诉你有几位猜对了

那请问最少需要几次能猜出完整的密码。

第 1 条附言 · 2014-08-20 13:18:54 +08:00

为什么没人回呢。。。
可以先从n位2进制开始考虑

第 2 条附言 · 2014-08-20 14:21:10 +08:00

说错了，是最多需要多少次就能猜出来
而且数字可以重复，比如11222这样

11 条回复 • 2014-08-21 10:09:26 +08:00

c742435

2014-08-20 13:40:54 +08:00

最少需要1次，直接蒙对

首先用m-1次猜测可以知道密码中每个数各有几位
然后n!次可以猜出密码的排列。（在n>m且每个数在密码中最多出现1次的情况下，如果一个数在密码中出现k次， k>1，则把n! / k!）

kmvan

2014-08-20 13:58:30 +08:00

最少？是最多吧？最少的话，RP足够好，直接正确了。

xjx0524

2014-08-20 14:20:04 +08:00

@kmvan 恩，是最多。。。

@c742435 第一句话理解，后面不太懂，而且n>m时不可能每个数在密码中最多出现1次吧？

binux

2014-08-20 14:35:45 +08:00

n*m 呗，首先试一个全错的（不超过 n*m 次），然后 n 个位每个换 m 次，让猜对次数+1即可

binux

2014-08-20 14:36:53 +08:00

@binux 哦，连全错都没必要，随便来一个数，挨个位换，如果换了猜对数-1了，原来是对的，如果不变，猜 m 让猜对数+1

xjx0524

2014-08-20 15:57:46 +08:00

@binux 额这肯定不是最优的方法啊，换种说法吧，运气最差的情况下最少需要多少次

binux

2014-08-20 16:47:46 +08:00

@xjx0524 如果 m < n 显然比楼上的 n! 快多了！

chone

2014-08-20 17:22:15 +08:00 via iPhone

@xjx0524 运气最差肯定就是所有排列组合了，没办法优化。

dingyaguang117

2014-08-20 18:42:05 +08:00

m*n

Exin

2014-08-20 20:57:21 +08:00

借地方问下有人知道怎么写 1A2B 这个数学趣题的AI算法么？
和楼主这个猜密码很类似的

takato

2014-08-21 10:09:26 +08:00

应该没有多项式时间效率的算法。。