红包算法

解决红包金额随机生成的问题。
红包分配规则：

  1. 所有人抢到金额之和等于红包金额。
  2. 每个人至少抢到一分钱。
  3. 保证所有人抢到金额的概率相等。

法一：二倍均值法

设剩余红包金额为M，剩余人数为N，金额公式：

每次抢到的金额=（0， M / N X 2）

公式保证每次随机金额的平均值是相等的，不会因为抢红包的先后顺序而造成不公平。

问题：除了最后一次，每次抽到的金额都小于人均金额的两倍，并不是任意的随机。

法二：线段切割法

划分方法如下：

如何在[0, M]确定N-1个切割点?

当所有切割点确定以后，子线段的长度也随之确定。这样每个人来抢红包的时候，只需要顺次领取与子线段长度等价的红包金额即可。

问题：切割点重复出现如何解决？

洗牌算法

从n个数中随机抽出m个不重复的数。

参考 三种洗牌算法，介绍其中常用的Knuth-Durstenfeld Shuffle。

Knuth 和 Durstenfeld 在Fisher 等人的基础上对算法进行了改进，算法时间复杂度为O(n)，空间复杂度为O(1)。该算法的基本思想和 Fisher 类似，每次从未处理的数据中随机取出一个数字，然后把该数字放在数组的尾部，即数组尾部存放的是已经处理过的数字。

算法步骤为：

  1. 建立一个数组大小为 n 的数组 arr，分别存放 1 到 n 的数值;
  2. 生成一个从 0 到 n - 1 的随机数 x；
  3. 输出 arr 下标为 x 的数值，即为第一个随机数；
  4. 将 arr 的尾元素和下标为 x 的元素互换；
  5. 同2，生成一个从 0 到 n - 2 的随机数 x；
  6. 输出 arr 下标为 x 的数值，为第二个随机数；
  7. 将 arr 的倒数第二个元素和下标为 x 的元素互换；
    ……
    如上，直到输出 m 个数为止;

联系作者