【算法设计】将整数M随机分成N份的解决方法

    将整数M随机分成N份,看似很简单的问题其实也不简单。
    最近博主写段程序需要用到这个功能,首先是看看有没有现成的API或者解决方案,发现网上很多方法都是错误的,这里总结两个典型的错误方案,然后给出自己设计的一个算法,时间复杂度的为O(N)。
    这个很类似微信抢随机红包的功能,例如把一块钱随机分到10个红包,就相当于把100分钱随机分成10份,每份至少为1分钱。重要的是保证其公平性,从统计学上讲,就是假设有10人共同参与抢红包,抢巨大数量的随机金额红包后,每个人抢到红包金额总数都应该差不多。但参考微信红包的随机算法是怎样实现的?里面的说法,微信随机红包不是一次性分开的,也不是所谓的随机,是有额度限制的。例如把100元随机分成5个红包,每个红包至少一分钱,理论上可能出现一个红包有99.66元,其余四个红包0.01元,但实际上每个红包不会超过平均金额的两倍即40.00元。

    博主这里需要的是一个没有阈值的一次性将整数M随机分成N份(即N个整数的和)的 方法。

【一】按照人类的思维,一刀能把蛋糕分为两块,因此最直观的方法是,在0到M范围内产生N-1个随机数作为划分点,就能把M分成N份。

【二】另外一个做法是,按照随机的比例进行分配,先生成N个0到M的随机数r1,r2,r3…,然后将这N个随机数相加得到总数sum=r1+r2+r3+…,最后计算每一份的数量Num(i)=r(i)*sum/M.

    【未完】

发表评论

电子邮件地址不会被公开。 必填项已用*标注