1. 问题
    有个密码锁,密码是000-999中的某个数,但是只有两位是有效的,即只需猜中其中的两个数字就可以打开,比如密码是235,那么当你试2*5或*35或23*都可以打开锁。
    (1)构造一个策略,使得这个策略在最坏情况下,所需要的次数最少,并且求这个最少的次数
    (2)证明你构造的策略是最优的
  2. 问题理解
    • 问题没有指明所需要试的次数最少是为了得出这个密码呢,还是为了打开密码锁所
      俺假设是求,为了打开密码锁所需的最坏最少次数
    • 俺开头忽略了三位实际密码仅有一个,而是想当然认为2位实际密码可以任意
      按照这个假设,三位有效密码可以是28个,29个或30个
      后来发现,这不是题目的本意
    • 问题相当于有效密码不仅是1个,而是28个(9+9+9+1),即只要试中这28个数中的一个,即可打开密码锁
    • 因为只要两位有效,所以当固定其中一位时,尝试10×10=100遍总是能打开锁,所以问题的解只能<=100
  3. 尝试解答
    其实对这个问题,有这么一个解答,虽然要执行这个方法有事实上的困难。
    这个策略其实就是一种排列,排列的对象是从000-999共1000个数,所以路径有1000!这么多,在这么多的路径中,题目要求我们选出的路径要符合这样的条件
    • 因为密码可以是000-999中的任意一个,假设路径是path,程序描述如下:
      for i in 000-999
          遍历path,直到打开密码箱
          尝试次数存入try(i)
      取try(i)【i from 000 to 999】的最大值
    • 对1000!个这样的path,我们有1000!个这样的最大值
      在这些1000!个最大值中,选最小值,即和这些最小值对应的path,即为题目所解

结论:

很显然3描述的算法,逻辑上是正确的,问题是1000!很大很大,一般计算机要穷举这些可能要花巨长的时间,所以不现实。

Advertisements