In the online test server , A colleague's red envelope algorithm is required to be optimized , Listen to their discussion , What kind of probability theory should be used for the final result , Never heard of the term to solve . I said I was confused *. In fact, the problem to be solved is one ： The red packet algorithm is not average enough , There is a probability that the amount difference will be too large .
Solutions to this problem , There are four （ Common law , Line cutting method , Double random method , Shooting basketball ）. The first three algorithms , The Internet is basically spreading , Basketball shooting algorithm , It's my own blind name . This algorithm is still due to the school enrollment , Beijing Mobile graffiti interview , The interviewer led me to a question on the spot , The example of shooting basketball is used . And when I wrote this blog , Think of that algorithm , It's quite applicable , So he was called a basketball player .
One , Common law ： Each time for the remaining total amount to do a random , The random value is the number of the first person . This algorithm is also the algorithm that this colleague wrote before and asked to be optimized . The advantage of this algorithm is completely random , The disadvantage is that it is very likely to cause the predecessors to rob too much , Too few descendants . for example ,100 Yuan to 10 personal , The first person is here 0-100 random , The average value is 50. And the second person's average is only one 25, And then it was 12.5.
// Common law There is a guarantee //iTotalGold Total amount iNum Number of copies iBaseGold Guaranteed amount void oldThink(int iTotalGold,
int iNum, int iBaseGold) { if (iBaseGold*iNum > iTotalGold) { cout << " Too many guarantees "
<< 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 <<
" Common law :" << endl; copy(veGold.begin(), veGold.end(), ostream_iterator<int>(cout,
" ")); cout << endl; }
Two , Line cutting method ： Think of the total amount as a line of that length , Need to be split into num share , random num-1 second , Map the random value of each time to the line segment . The advantage of this is that the random number will be given to the program , The disadvantage is that there is a small probability that someone will be over allocated . for example ,100 Individual points 10 A red envelope , We need to consider the coincidence of random values , Each time is completely random , It may cause a situation that is not random enough .
// Line cutting method No guarantee //iTotalGold Total amount iNum Number of copies iBaseGold Guaranteed amount 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 << " Line cutting method ( No guarantee ):" << endl; int iPreLine
= 0; for (auto &it : setGold) { cout << it - iPreLine << " "; iPreLine = it; }
cout << iTotalGold - iPreLine << " "; cout << endl; }
Three , Double random method ： Every time it's random , take 0- Average amount per person 2 Multiple random . This is basically what we want , It's a good way . for example ：100 Individual points 10 branch , Every time it's random 0-100/10*2 De randomization , Basically, we can ensure that everyone is on average 10 about , It's a fairly average algorithm . However, it should be noted that the last few people may not be enough 20 The situation of .
// Double random method //iTotalGold Total amount iNum Number of copies iBaseGold Guaranteed amount void twobase(int iTotalGold, int
iNum, int iBaseGold) { if (iNum *iBaseGold > iTotalGold) { cout << " Too many guarantees " <<
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 << " Double random method :" << endl; copy(veGold.begin(), veGold.end(),
ostream_iterator<int>(cout, " ")); cout << endl; }
Four , Shooting basketball ： Before always with the amount of people to remove num To seek the average . It's basketball , It is based on the unit value of the amount . The above three algorithms are trying their best to find random , And the rule of shooting basketball is to make sure it's completely average . for example ：100 Individual points 10 branch , The minimum unit value of each withdrawal amount , Like a dollar , And then put 10 Individual as a basket , One dollar for basketball , I shoot every time . The advantage is that you don't have to imitate completely random , He's completely random , The harm is also obvious , Too many cycles . So the unit value of the minimum amount is used here , For example, take three at a time , Five . The code is simple ：
// Shooting basketball There is a guarantee //iTotalGold Total amount iNum Number of copies iBaseGold Guaranteed amount void basketball(int
iTotalGold, int iNum, int iBaseGold) { if (iBaseGold*iNum > iTotalGold) { cout
<< " Too many guarantees " << iBaseGold << endl; return; } iTotalGold -= (iBaseGold *iNum);
std::vector<int> veGold(iNum, iBaseGold); for (int i = 0; i < iTotalGold; i +=
2) // Here the benchmark is used 2, Reduce the number of cycles { int iPos = rand() % iNum; veGold[iPos] += 2; } cout <<
" Shooting basketball :" << endl; copy(veGold.begin(), veGold.end(), ostream_iterator<int>(cout,
" ")); cout << endl; }
test result ：
Tested several times , Now the worst is the common law , Because all the big money is concentrated in the first few people . The double random method and the basketball throwing method are basically near the average value , The difference is not very large , But considering the number of calls , Double random method , If you think about the simplicity of the code , Better way to throw basketball . Line cutting is not suitable for our game planning needs , But the difference between the larger red envelope should be more suitable for some simple APP Application of .
Technology