第三十一天(脑筋急转弯)

今天完成题目:1033,292,1227 1033:移动石子直到连续

• 最大情况=最大数-最小数-2

• 最小情况

  • 存在一个间隙的石子,例如,1,3,6.则结果为1

  • 三个已经连续,则结果为0

  • 左边两个或右边两个连续,则结果为1

  • 其他情况为2.

292:Nim游戏

• 4为false,则5,6,7可以通过拿掉1,2,3个使得对方为false,自己为true

• 同理,得出8,12,16...为false

1227:飞机座位概率

• 1 号乘客是 1 号座位，(ps：1 号 票丢了，并不知道自己坐 1 号座位)

• 2 号乘客 是 2 号座位

• 我们要求的是最后一位乘客 n 最终能坐到自己座位，即 n 号座位的概率

• 因为 1 号 票丢了，因此分析 1 号 坐不同座位的情况，它有 3 种选择

  • 1 号有 1 / n 的概率 坐到 1 号座位，那么不会对 [2, n] 号乘客产生影响，因为它们都有票，那么 n 号乘客坐到自己座位的概率为 1

  • 1 号有 1 / n 的概率 坐到 n 号座位，那么 n 号 肯定坐不到 n 号座位，那么概率为 0

  • 1 号有 n - 2 / n 的概率 坐到 [2, n - 1] 号座位，假设是 k 号座位，

    那么对于 k 号乘客来说它有 3 种选择

    • k 号有 1 / n - 1 的概率 坐到 1 号座位，那么不会对其他乘客产生影响，那么 n 号乘客坐到自己座位的概率为 1（为什么分母是 n - 1？ 因为 k 号座位被坐了，它必定不会去坐）

    • k 号有 1 / n - 1 的概率 坐到 n 号座位，那么 n 号 肯定坐不到 n 号座位，那么概率为 0

    • k 号有 n - 3 / n - 1 的概率坐到 除 1、k、n 外的座位，假设是 m 号座位

    • 递归分析

      if n == 1:
      return 1.0
      else:
      return 1.0/n + (n-2)/n*self.nthPersonGetsNthSeat(n-1)