- 2019-07-17 12:02
*views 6*- Advanced data structure and algorithm
- Grab a red envelope
- Line cutting method
- informal essay

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

- Python187 blogs
- Java177 blogs
- Vue93 blogs
- Flow Chart80 blogs
- algorithm54 blogs
- C++52 blogs
- MySQL49 blogs
- javascript49 blogs
- more...

Daily Recommendation

views 1

views 0

©2020-2021 ioDraw All rights reserved

lstm prediction model _ use LSTM Forecast stock price Prepare for the Blue Bridge Cup — enumeration ——[USACO Nov08] deal 14:00 interview ,14:08 Just came out , The question is too much ...Python Write and read Excel Tabular data jquery Detailed explanation of method properties Linux Study notes （1）SpringMVC Source code analysis 【Hadoop】——JavaAPI operation 【Redis】—— Cache penetration , Buffer breakdown , Cache avalanche TCP and UDP What is it? ? What's the difference ?