红包算法-详细内容 - 黄兵的个人博客

文章内容

2017/1/4 15:15:14,作者: 黄兵

红包算法

注意，本算法在条件接近临界值的时候，会导致后续大量的红包始终为最小值的情况，有待优化

推导

（下列涉及钱的部分均使用了单位分，这样能保证在计算过程中涉及的数字均为整数）

现有钱m分，要分成n份，每份最少a分，最多b分，求每次应该分的钱x

显然：

(1) an <= m <= bn

(2) a <= x <= b

当进行一次分配后

(3) a(n - 1) <= m - x <= b(n - 1)

上式中间只保留x可得

(4) m - bn + b <= x <= m - an + a

另由式(1)可得

m - bn + b <= b

m - an + a >= a

综上所述，x的取值范围应该是

(5) max(a, m - bn + b) <= x <= min(b, m - an + a)

证明

由于(1)(2)(4)式互为充要条件，故当n = 0时，m = 0

代码

/// <summary>  
/// 红包算法1  
/// </summary>  
/// <param name="money">总钱数，单位为分</param>  
/// <param name="count">份数</param>  
/// <param name="min">每次分配最小值，单位为分</param>  
/// <param name="max">每次分配最大值，单位为分</param>  
/// <param name="random">随机数生成器，如果不传使用默认的</param>  
/// <returns>每次应该分配的钱数</returns>  
IEnumerable<int> LuckyMoneyAlgorithm1(int money, int count, int min, int max, Random random)  
{  
    if (count <= 0)  
        throw new ArgumentOutOfRangeException("count");  
  
    if (max <= 0)  
        throw new ArgumentOutOfRangeException("max");  
  
    if (min < 0 || min > max)  
        throw new ArgumentOutOfRangeException("min");  
  
    if (money < min * count || money > max * count)  
        throw new ArgumentOutOfRangeException("money");  
  
    if (random == null)  
        random = new Random();  
  
    do  
    {  
        int min2 = Math.Max(min, money - max * count + max);  
        int max2 = Math.Min(max, money - min * count + min);  
        int dist = random.Next(min2, max2 + 1); //注意Random不能取到上限  
        yield return dist;  
        money -= dist;  
    }  
    while (--count > 0);  
}