微信紅包算法

微信紅包有多種玩法，其中一種就是指定金額、人數(m)，拆紅包的人收到的金額是隨機，收到的金額保留兩位小數，至少有一分，所有人的紅包加起來等于指定金額。

我想到一種做法就是：將指定金額放大100倍，也就是變成單位“分”，這時金額就是整數了，設為n，從1到n這個整數區間隨機抽取m(是人數)個整數，這樣1到n的整數區間就分成了m或m+1(這種情況，最后的兩個區間合成一個區間)個區間。

比如輸入金額1.00元，人數m=3，n=100 * 1。從1到100之間隨機選中的三個整數為15、42、88，這時產生了m+1個區間，最后的兩個區間合并，最終得到三個區間：1--15，16--42，43--100，根據這三個區間計算金額為0.15、0.42-0.15=0.27、1.00-0.42=0.58，最終得到的隨機金額為：0.15、0.27、0.58。

抽樣算法是參考《編程珠璣》這本書中的。java代碼如下，使用BigDecimal便于精度控制，使用junit進行了簡單測試。

package com.wss.lsl.test.driven.arithmetic.prob;

import java.math.BigDecimal;
/**

微信紅包算法

@author sean
*/
public class WeixinRedEnvelopes {
/**

金額的精度：保留兩位小數
*/
private static int scale = 2;
/**

普通玩法
<p>
輸入金額、人數，隨機輸出金額列表，例如：<br>
輸入：1.0 3<br>
輸出：0.11 0.37 0.52
</p>

@return
*/
public static BigDecimal[] generalPlay(final BigDecimal money,

 int numberOfPeople) {

// 檢驗參數的合法性
 checkGeneralPlayValidParam(money, numberOfPeople);
// 將金額轉化為分，就能轉化為整數
 BigDecimal divisor = new BigDecimal(100);
 int n = money.multiply(divisor).intValue();
 // 從1--n之間隨機抽出numberOfPeople個數。其實這里就是一個抽樣問題
 BigDecimal[] result = new BigDecimal[numberOfPeople];
 int m = numberOfPeople;
 int index = 0;
 for (int i = 0; i < n; i++) {

 long bigrand = bigRand();
 if (bigrand % (n - i) < m) {
     result[index++] = new BigDecimal(i + 1).divide(divisor, scale,
             BigDecimal.ROUND_HALF_UP);
     m--;
 }

}
 // 分區間處理
 for (int i = numberOfPeople - 1; i > 0; i--) {

 if (i == (numberOfPeople - 1)) {
     // 最后一個就取剩余的
     result[i] = money.subtract(result[i - 1]);
 } else {
     result[i] = result[i].subtract(result[i - 1]);
 }

}
 return result;
}
/**

產生一個很大的隨機整數

@return
/
private static long bigRand() {
 long bigrand = (long) (Math.random()  Integer.MAX_VALUE)

     + Integer.MAX_VALUE;


return bigrand;
}
/**

檢查方法{@link #generalPlay(BigDecimal, int)}參數的有效性
*/
private static void checkGeneralPlayValidParam(final BigDecimal money,
 int numberOfPeople) {

 // 確保人數大于等于1
 if (numberOfPeople < 1) {
 throw new RuntimeException("人數 " + numberOfPeople + " 應該大于0！");

 }
 // 確保每個人至少能分到0.01元
 if (money.compareTo(new BigDecimal("0.01").multiply(new BigDecimal(
     numberOfPeople))) < 0) {
 throw new RuntimeException("人數太多，錢不夠分！");

 }
 // 確保money只有兩位小數
 if (money.scale() > scale) {
 throw new RuntimeException("金額數據不對，最多保留兩位小數！");

 }
}
}</pre>

源碼：WeixinRedEnvelopes.java 
測試：WeixinRedEnvelopesTest.java 



來自：http://my.oschina.net/u/2007041/blog/421761