概率

概率计算

• 长度为1的线段，随机选2点将其分为3段，求这3段可以构成三角形的概率

  Ans. 1/8

• 元首会面

• 54张派发给3个人，求至少有一个拿到炸弹（仅指四张同点的）的概率

• 2个人抛硬币，谁先抛出正面谁赢。求先抛的人获胜的概率

  Ans. 2/5. 提示：

• 混乱的登机问题

排列组合

• 名额分配

生成随机数

随机数发生器构造，一般通过拒绝采样法

• 一个随机数发生器以概率p生成0,1-p生成1，由此发生器生成一个生成0与1的均匀发生器

  提示： 找出两个发生概率相同的事件，各自编码为1和0即可

• 用上述得到的0与1的均匀发生器生成1到N的均匀发生器

  提示：考虑N的二进制

• 用两个六面体生成1到4，其中1的概率为0.4,2的概率为0.3,3的概率为0.2,4的概率为0.1

  提示：

• 一个六面体，出现1,2,3,4的概率均为1/5，出现5,6的概率均为1/10.构造一个1到9的均匀发生器。

  提示：

• 由 rand7() 生成 rand10()

  提示：

• 带权采样问题
  n 个元素，n个对应权值。

迷惑性问题

• 三门问题