微信現金入り封筒アルゴリズム実現(JAVA)
3275 ワード
概要
ネット上では2つの比較的公平なアルゴリズムがあり、1つは2倍平均法であり、1つは線分切断法である.次の2つのアルゴリズムの実装について説明します.
にじゅうへいきんほう
げんり
残りのお年玉の金額M、残りの人数N、それでは:毎回奪い取る金額=ランダム(0,M/N*2)は毎回ランダムな金額の平均値が公平であることを保証して10人、お年玉の金額の100元の第一人者:100/10*2=20、ランダムな範囲(0,20)、平均は10元の第二人:90/9*2=20を奪い取ることができて、ランダムな範囲(0,20)、平均は10元の第三人:80/8*2=20を奪い取ることができますランダム範囲(0,20)は、平均10元を奪うことができます.これによって、ランダム範囲の平均値は等しい欠点です.最後の1回を除いて、どの1人当たりの金額の2倍を超えず、任意のランダムではありません.
インプリメンテーション
セグメントせつだんほう
げんり
お年玉の総額を長い線分に想像しますが、一人一人が奪った金額は、この主線分で分割されたいくつかのサブ線分です.
N人でお年玉を奪う場合は、N-1カットポイントを特定する必要があります.
したがって,N人が合計金額Mのお年玉を奪う場合,N−1個の切断点を決定するためにN−1回のランダム演算を行う必要がある.
ランダムな範囲区間は[1100*M).すべてのカットポイントが決定されると、サブセグメントの長さも決定されます.これにより、一人一人がお年玉を取りに来た場合、サブセグメントの長さに等価なお年玉の金額を順次受け取るだけです.
インプリメンテーション
ネット上では2つの比較的公平なアルゴリズムがあり、1つは2倍平均法であり、1つは線分切断法である.次の2つのアルゴリズムの実装について説明します.
にじゅうへいきんほう
げんり
残りのお年玉の金額M、残りの人数N、それでは:毎回奪い取る金額=ランダム(0,M/N*2)は毎回ランダムな金額の平均値が公平であることを保証して10人、お年玉の金額の100元の第一人者:100/10*2=20、ランダムな範囲(0,20)、平均は10元の第二人:90/9*2=20を奪い取ることができて、ランダムな範囲(0,20)、平均は10元の第三人:80/8*2=20を奪い取ることができますランダム範囲(0,20)は、平均10元を奪うことができます.これによって、ランダム範囲の平均値は等しい欠点です.最後の1回を除いて、どの1人当たりの金額の2倍を超えず、任意のランダムではありません.
インプリメンテーション
//
public static List divideRedPackage(Integer totalAmount,
Integer totalPeopleNum) {
List amountList = new ArrayList();
// random.nextInt(Integer) 100 , main 100
//
Integer restAmount = totalAmount * 100;
Integer restPeopleNum = totalPeopleNum;
Random random = new Random();
for (int i = 0; i < totalPeopleNum - 1; i++) {
// :[1, ),
int amount = random.nextInt(restAmount / restPeopleNum * 2 - 1) + 1;
restAmount -= amount;
restPeopleNum--;
amountList.add(amount);
}
amountList.add(restAmount);
return amountList;
}
セグメントせつだんほう
げんり
お年玉の総額を長い線分に想像しますが、一人一人が奪った金額は、この主線分で分割されたいくつかのサブ線分です.
N人でお年玉を奪う場合は、N-1カットポイントを特定する必要があります.
したがって,N人が合計金額Mのお年玉を奪う場合,N−1個の切断点を決定するためにN−1回のランダム演算を行う必要がある.
ランダムな範囲区間は[1100*M).すべてのカットポイントが決定されると、サブセグメントの長さも決定されます.これにより、一人一人がお年玉を取りに来た場合、サブセグメントの長さに等価なお年玉の金額を順次受け取るだけです.
インプリメンテーション
//
private static List divide(double money, int n) {
//
// random.nextInt(Integer) 100 , main 100
//
int fen = (int) (money * 100);
if (fen < n || n < 1) {
System.out.println(" 0, 1 ");
}
List boards = new ArrayList<>();
boards.add(0);
boards.add(fen);
//
while (boards.size() <= n) {
int index = new Random().nextInt(fen - 1) + 1;
if (boards.contains(index)) {
//
continue;
}
boards.add(index);
}
// ,
Collections.sort(boards);
List list = new ArrayList<>();
for (int i = 0; i < boards.size() - 1; i++) {
Integer e = boards.get(i + 1) - boards.get(i);
list.add(e);
}
return list;
}
public static void main(String[] args) {
// List accountList = divideRedPackage(50, 1000);
List accountList = divide(50, 10);
BigDecimal count = new BigDecimal(0);
for (Integer amount : accountList) {
// 100
BigDecimal tmpcount = new BigDecimal(amount).divide(new BigDecimal(100));
count = count.add(tmpcount);
System.out.println(" :" + tmpcount);
}
System.out.println("total=" + count);
}