©2020-2024 ioDraw All rights reserved,
Privacy Policy
线上测试服务器中，有个同事做的抢红包算法被要求优化，大概听了下他们的讨论，最后的结果竟然要用什么概率论等等一系列我听过的、没听过的名词去解决。我表示一脸懵*。其实解决的问题就是一个：抢红包算法不够平均，先抢后抢有概率造成金额差值过大。
针对这个问题的解决方法，有四种（普通法，线段切割法，双倍随机法，投篮球法）。前三种算法，网上基本都在流传，投篮球算法，是我自己瞎起的名字。这个算法还是因为当年校招，面试北京涂鸦移动，面试官现场引导我一个问题，用了投篮球这个例子。而我写这篇博客的时候，想起那个算法，蛮适用的，因而叫他投篮球算法。
一、普通法：每次针对剩余总金额做一次随机，随机值就是第一个人的数值。这个算法也就是这个同事之前写的要求被优化的算法。这个算法的好处是完全随机，坏处是极有可能造成前人抢的太多，后人太少。例如，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<<endl; return; } iTotalGold -= (iBaseGold *iNum); std::vector<int>
veGold(iNum); for (int i = 0; i < iNum-1; ++i) { int iAddNum = 0; if(iTotalGold
!= 0) iAddNum += rand() % (iTotalGold); veGold[i] = iAddNum + iBaseGold;
iTotalGold -= iAddNum; } veGold[iNum - 1] = iTotalGold + iBaseGold; cout <<
"普通法:" << endl; copy(veGold.begin(), veGold.end(), ostream_iterator<int>(cout,
" ")); cout << endl; }
二、线段切割法：将总金额想象成一条那么长的线段，需要分割成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<int> 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; }
三、双倍随机法：每次随机的时候，取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<int> 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<int>(cout, " ")); cout << endl; }
四、投篮球法：之前总是用金额去除以人数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<int> 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<int>(cout,
" ")); cout << endl; }
测试结果：
测试了几次，目前最差的就是普通法，因为所有大金额全部集中在前几个人。双倍随机法和投篮球法基本上都在平均值附近，差值并非很大，但考虑到调用次数的话，双倍随机法生出，如果考虑到代码简洁的话，投篮球法稍好。线段切割法不适用于我们游戏中策划的需求，但是差值大一些的抢红包应该更适用于平时一些简单APP的应用。