935
財經資訊
微信搶紅包原理，外掛軟件掃雷埋雷控製尾數
過年微信紅包很火，最近有個項目也要做搶紅包，於是寫了個紅包的生成算法。
紅包生成算法的需求
預先生成所有的紅包還是一個請求隨機生成一個紅包
簡單來說，就是把一個大整數m分解（直接以“分為單位，如1元即100）分解成n個小整數的過程，小整數的範圍是[min, max]。
最簡單的思路，先保底，每個小紅包保證有min，然後每個請求都隨機生成一個0到(max-min)範圍的整數，再加上min就是紅包的錢數。
這個算法雖然簡單，但是有一個弊端：最後生成的紅包可能都是min錢數的。也就是說可能最後的紅包都是0.01元的。
另一種方式是預先生成所有紅包，這樣就比較容易控製了。我選擇的是預先生成所有的紅包。
理想的紅包生成算法
理想的紅包生成結果是平均值附近的紅包比較多，大紅包和小紅包的數量比較少。
可以想像下，生成紅包的數量的分布有點像正態分布。
那麼如何實現這種平均線附近值比較多的要求呢？
就是要找到一種算法，可以提高平均值附近的概率。那麼利用一種”膨脹“再”收縮“的方式來達到這種效果。
先平方，再生成平方範圍內的隨機數，再開方，那麼概率就不再是平均的了。
具體算法：
[java]view plain copy
public class HongBaoAlgorithm {
static Random random = new Random();
static {
random.setSeed(System.currentTimeMillis());
}
public static void main(String[] args) {
long max = 200;
long min = 1;
long[] result = HongBaoAlgorithm.generate(100_0000, 10_000, max, min);
long total = 0;
for (int i = 0; i
// System.out.println("result[" + i + "]:" + result[i]);
// System.out.println(result[i]);
total += result[i];
}
//檢查生成的紅包的總額是否正確
//統計每個錢數的紅包數量，檢查是否接近正態分布
int count[] = new int[(int) max + 1];
for (int i = 0; i
count[(int) result[i]] += 1;
}
for (int i = 0; i
}
}
/**
* 生產min和max之間的隨機數，但是概率不是平均的，從min到max方向概率逐漸加大。
* 先平方，然後產生一個平方值範圍內的隨機數，再開方，這樣就產生了一種“膨脹”再“收縮”的效果。
*
* @param min
* @param max
* @return
*/
static long xRandom(long min, long max) {
return sqrt(nextLong(sqr(max - min)));
}
/**
*
* @param total
* 紅包總額
* @param count
* 紅包個數
* @param max
* 每個小紅包的最大額
* @param min
* 每個小紅包的最小額
* @return 存放生成的每個小紅包的值的數組
*/
public static long[] generate(long total, int count, long max, long min) {
long[] result = new long[count];
long average = total / count;
long a = average - min;
long b = max - min;
//
//這樣的隨機數的概率實際改變了，產生大數的可能性要比產生小數的概率要小。
//這樣就實現了大部分紅包的值在平均數附近。大紅包和小紅包比較少。
long range1 = sqr(average - min);
long range2 = sqr(max - average);
for (int i = 0; i
//因為小紅包的數量通常是要比大紅包的數量要多的，因為這裏的概率要調換過來。
//當隨機數>平均值，則產生小紅包
//當隨機數
if (nextLong(min, max) > average) {
// 在平均線上減錢
// long temp = min + sqrt(nextLong(range1));
long temp = min + xRandom(min, average);
result[i] = temp;
total -= temp;
} else {
// 在平均線上加錢
// long temp = max - sqrt(nextLong(range2));
long temp = max - xRandom(average, max);
result[i] = temp;
total -= temp;
}
}
// 如果還有餘錢，則嚐試加到小紅包裏，如果加不進去，則嚐試下一個。
while (total > 0) {
for (int i = 0; i
if (total > 0 && result[i]
result[i]++;
total--;
}
}
}
// 如果錢是負數了，還得從已生成的小紅包中抽取回來
while (total
for (int i = 0; i
if (total min) {
result[i]--;
total++;
}
}
}
return result;
}
static long sqrt(long n) {
// 改進為查表？
return (long) Math.sqrt(n);
}
static long sqr(long n) {
// 查表快，還是直接算快？
return n * n;
}
static long nextLong(long n) {
return random.nextInt((int) n);
}
static long nextLong(long min, long max) {
return random.nextInt((int) (max - min + 1)) + min;
}
}
統計了下生成的結果，還是比較符合要求的。
最後更新：2017-10-08 01:36:41