馬上過年了。過年微信紅包很火,最近有個項目也要做搶紅包,于是寫了個紅包的生成算法。
紅包生成算法的需求
預先生成所有的紅包還是一個請求隨機生成一個紅包
簡單來說,就是把一個大整數m分解(直接以“分為單位,如1元即100)分解成n個小整數的過程,小整數的范圍是[min, max]。
最簡單的思路,先保底,每個小紅包保證有min,然后每個請求都隨機生成一個0到(max-min)范圍的整數,再加上min就是紅包的錢數。
這個算法雖然簡單,但是有一個弊端:最后生成的紅包可能都是min錢數的。也就是說可能最后的紅包都是0.01元的。
另一種方式是預先生成所有紅包,這樣就比較容易控制了。我選擇的是預先生成所有的紅包。
理想的紅包生成算法
理想的紅包生成結果是平均值附近的紅包比較多,大紅包和小紅包的數量比較少。
可以想像下,生成紅包的數量的分布有點像正態分布。
那么如何實現這種平均線附近值比較多的要求呢?
就是要找到一種算法,可以提高平均值附近的概率。那么利用一種”膨脹“再”收縮“的方式來達到這種效果。
先平方,再生成平方范圍內的隨機數,再開方,那么概率就不再是平均的了。
具體算法:
public class HongBaoAlgorithm {   static Random random = new Random();   static {     randomsetSeed(SystemcurrentTimeMillis());   }      public static void main(String[] args) {     long max = 200;     long min = 1;      long[] result = HongBaoAlgorithmgenerate(100_0000, 10_000, max, min);     long total = 0;     for (int i = 0; i < resultlength; i++) {       // Systemoutprintln("result[" + i + "]:" + result[i]);       // Systemoutprintln(result[i]);       total += result[i];     }     //檢查生成的紅包的總額是否正確     Systemoutprintln("total:" + total);      //統計每個錢數的紅包數量,檢查是否接近正態分布     int count[] = new int[(int) max + 1];     for (int i = 0; i < resultlength; i++) {       count[(int) result[i]] += 1;     }      for (int i = 0; i < countlength; i++) {       Systemoutprintln("" + i + " " + count[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 < resultlength; 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 < resultlength; i++) {         if (total > 0 && result[i] < max) {           result[i]++;           total--;         }       }     }     // 如果錢是負數了,還得從已生成的小紅包中抽取回來     while (total < 0) {       for (int i = 0; i < resultlength; i++) {         if (total < 0 && result[i] > min) {           result[i]--;           total++;         }       }     }     return result;   }    static long sqrt(long n) {     // 改進為查表?     return (long) Mathsqrt(n);   }    static long sqr(long n) {     // 查表快,還是直接算快?     return n * n;   }      static long nextLong(long n) {     return randomnextInt((int) n);   }    static long nextLong(long min, long max) {     return randomnextInt((int) (max - min + 1)) + min;   } } 統計了下生成的結果,還是比較符合要求的。
以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持武林網。
新聞熱點
疑難解答