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

[xjx0524]

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

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

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

[c742435]

最少需要1次，直接蒙对

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

[kmvan]

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

[xjx0524]

@kmvan 恩，是最多。。。

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

[binux]

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

[binux]

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

[xjx0524]

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

[binux]

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

[chone]

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

[dingyaguang117]

m*n

[Exin]

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

[takato]

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