抢红包算法--四种抢红包算法对比（附源码）

发布人：147小编来源：微信抢红包群,支付宝红包群,红包群,红包扫雷群发布时间：2022-08-10 01:49:23 热度：

还记着longlong ago

我还在做绿色征途手游版的时候

有天

策划同学要求同事

一定要优化下抢红包算法

本着划水第一

吃瓜并列第一的原则

于是

我听到了一堆数学名词

***定理

XXX公式

呼~

是我不配了

怪我没有好好学习

再仔细听一听

问题原来是

原先的红包分配算法是

先抢的人从总金额随机

后抢的人从剩余金额中随机

所以导致抢红包越早

抢的金额就越大

策划现在就想让金额稍微平均下

嚯，我直呼好家伙

就这个东西

有必要整那些有的没的吗

一会定理

一会公式的

最后他们的方案

也很务实

就是每个人先做个保底

再根据之前的红包算法进行分配

嘿果然大隐隐于市

翠花，上酸菜

分析：

针对这个问题的解决方法，有四种（普通法，线段切割法，双倍随机法，投篮球法）。

前三种算法，网上基本都在流传，投篮球算法，是我自己瞎起的名字。

这个算法还是因为当年校招，面试北京涂鸦移动，面试官现场引导我一个问题，用了投篮球这个例子。而我写这篇博客的时候，想起那个算法，蛮适用的，因而叫他投篮球算法。

一、普通法：每次针对剩余总金额做一次随机，随机值就是第一个人的数值。这个算法也就是这个同事之前写的要求被优化的算法。这个算法的好处是完全随机，坏处是极有可能造成前人抢的太多，后人太少。例如，100元分给10个人，第一个人在0-100随机，均值为50。而第二个人的均值只剩25，之后是12.5。

而他们修改后的方案，大致就是先有保底。然后再随机，大致算法如下：

//普通法有保底 //iTotalGold总金额 iNum份数 iBaseGold保底金额 void oldThink(int iTotalGold, int iNum, int iBaseGold) { if (iBaseGold*iNum > iTotalGold) { cout << "保底太多 " << iBaseGold<

运行结果：

二、线段切割法：将总金额想象成一条那么长的线段，需要分割成num份，随机num-1次，将每次的随机值映射到该线段上。这样的好处是将随机交给程序，缺点是有小概率造成某个人分配过多。例如，100个人分10个红包，我们除了需要考虑随机值重合之外，每次完全随机，可能造成不够随机的情况。

//线段切割法无保底 //iTotalGold总金额 iNum份数 iBaseGold保底金额 void cutline(int iTotalGold, int iNum) { if (iNum > iTotalGold) { return; } if (iNum == iTotalGold) { for (int i = 0; i < iNum; ++i) cout << 1 << " "; cout << endl; return; } std::set setGold; for (int i = 0; i < iNum-1; ++i) { while (1) { int iPos = rand() % iTotalGold; if (setGold.find(iPos) == setGold.end()) { setGold.insert(iPos); break; } } } cout << "线段切割法(无保底):" << endl; int iPreLine = 0; for (auto &it : setGold) { cout << it - iPreLine << " "; iPreLine = it; } cout << iTotalGold - iPreLine << " "; cout << endl; } int main() { int iTotalGold = 100; int iNum = 10; int iBaseGold = 5; cutline(iTotalGold, iNum); return 0; }

运行结果：

这种算法，相比于第一种已经非常好了。如果觉得过于随机，可以针对这种算法做保底策略。可以预见，效果也一定好于第一种。

三、双倍随机法：每次随机的时候，取0-每个人平均金额的2倍进行随机。这样已经基本完成了我们想要的样子，不错的方法。例如：100个人分10分，每次随机都是0-100/10*2去随机，基本可以保证每个人平均在10左右，是相当平均的算法。不过需要注意最后几个人可能已经不足20的情况。

//双倍随机法 //iTotalGold总金额 iNum份数 iBaseGold保底金额 void twobase(int iTotalGold, int iNum, int iBaseGold) { if (iNum *iBaseGold > iTotalGold) { cout << "保底太多 " << iBaseGold << endl; return; } std::vector veGold(iNum, iBaseGold); iTotalGold -= iNum*iBaseGold; int iBaseTmp = iTotalGold / iNum * 2; for (int i = 0; i < iNum - 1; ++i) { if (iTotalGold == 0) break; int iTmp = 0; if (iTotalGold >= iBaseTmp) iTmp = rand() % iBaseTmp; else iTmp = rand() % iTotalGold; veGold[i] += iTmp; iTotalGold -= iTmp; } veGold[iNum - 1] = iTotalGold; cout << "双倍随机法:" << endl; copy(veGold.begin(), veGold.end(), ostream_iterator(cout, " ")); cout << endl; } int main() { int iTotalGold = 100; int iNum = 10; int iBaseGold = 5; twobase(iTotalGold, iNum, iBaseGold); return 0; }

运行结果：

从效果可以看出，这种随机方法，已经达到了非常棒的随机效果。几乎可以避免玩家的投诉了。

四、我自创的名字，投篮球法：之前总是用金额去除以人数num以寻求平均。而投篮球法，则是以金额的单元值最为基准。以上三种算法都在极力的寻求随机，而投篮球法则是为了保证完全平均。例如：100个人分10分，每次取金额的最小单元值，比如一块钱，然后把10个人当成篮筐，一块钱当成篮球，每次都去投篮。这样的好处是不用模仿完全随机，他本身就是完全随机，坏处也很明显，循环次数过多。

针对于他循环过多的缺点，我自己做了一层优化。采用最小金额的单元值，例如每次取三块、五块。这种优化，一来可以避免循环过多。二来也可以避免极端情况下过于随机的结果。

//投篮球法有保底 //iTotalGold总金额 iNum份数 iBaseGold保底金额 void basketball(int iTotalGold, int iNum, int iBaseGold) { if (iBaseGold*iNum > iTotalGold) { cout << "保底太多 " << iBaseGold << endl; return; } iTotalGold -= (iBaseGold *iNum); std::vector veGold(iNum, iBaseGold); for (int i = 0; i < iTotalGold; i += 2) //这里基准值用了2，减少循环次数 { int iPos = rand() % iNum; veGold[iPos] += 2; } cout << "投篮球法:" << endl; copy(veGold.begin(), veGold.end(), ostream_iterator(cout, " ")); cout << endl; } int main() { int iTotalGold = 100; int iNum = 10; int iBaseGold = 5; basketball(iTotalGold, iNum, iBaseGold); return 0; }

运行结果：

闲杂人等回避

我要装b了

从数学理论来说，只要随机次数足够多，那么结果一定是无限趋近于平衡的。所以这种算法，虽然循环次数过多，但是数据量够大的情况下，他一定是最优、最平衡的。

当然，算法服务于功能，上述结论局限于，策划希望大家拿到的都差不多。

最后，四种算法一起运行下，来对比下结果。

上图还存在一个小点，两次运行程序，得到的结果完全相同。这是因为rand函数在C++老版本里的随机因子是固定值的问题。关于随机因子和随机数，改天有空了再整理一篇文章专门讲述下。

这里，先解决下这种情况。只需要每次在程序运行时，重新给定随机因子就可以了。例如：srand((unsigned)time(0));

运行结果：

源码：

include include include include include include using namespace std; //普通法有保底 //iTotalGold总金额 iNum份数 iBaseGold保底金额 void oldThink(int iTotalGold, int iNum, int iBaseGold) { if (iBaseGold*iNum > iTotalGold) { cout << "保底太多 " << iBaseGold<

关注公众号【头发头发等等我】，查看更多分享

...　