微信、QQ現金入り封筒アルゴリズム(Java版)
1380 ワード
私达がふだん微信を使って、QQがお年玉を夺う时、いつもとても不思议だと感じて、そこで今日暇を割いてそのアルゴリズムを研究して、それからいくつかのブログと自分の理解を参考にして、1つのアルゴリズムを书きました.
ルール:
1.すべての人が奪った金額の和はお年玉の金額に等しく、超えてはいけないし、少なくてはいけない.
2.一人一人が少なくとも1銭を奪った.
3.すべての人が金額を奪う確率が等しいことを保証しなければならない.
アルゴリズムの説明:
1)まずすべての金額mを最小単位分に換算し、その値はm:例えば1元=100分(m=100)、4.23=423分(m=423)である.
2)その後,区間(0,m)で(n−1)個の乱数を得,全金額をランダムにn部に分割した.nはお年玉の個数で、つまりお年玉を奪う人数です.
3)得られた乱数をリストに入れ,リストに0とmの2つの要素(主に後で金額を計算しやすいように)を加えてリストをソートする.
コードの例:
実行結果:
第1人抢到:6第2人抢到:11第3人抢到:13第4人抢到:2第5人抢到:20第6人抢到:4第7人抢到:5第8人抢到:10
9人目の強盗:20
10人目の強盗:9
もちろん、このアルゴリズムには最適化の場所があります.コメントエリアで議論することを歓迎します.
ルール:
1.すべての人が奪った金額の和はお年玉の金額に等しく、超えてはいけないし、少なくてはいけない.
2.一人一人が少なくとも1銭を奪った.
3.すべての人が金額を奪う確率が等しいことを保証しなければならない.
アルゴリズムの説明:
1)まずすべての金額mを最小単位分に換算し、その値はm:例えば1元=100分(m=100)、4.23=423分(m=423)である.
2)その後,区間(0,m)で(n−1)個の乱数を得,全金額をランダムにn部に分割した.nはお年玉の個数で、つまりお年玉を奪う人数です.
3)得られた乱数をリストに入れ,リストに0とmの2つの要素(主に後で金額を計算しやすいように)を加えてリストをソートする.
コードの例:
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
*
* @author Tony
* m : 1 =100 ,4.23=423
* (0,m) (n-1) , n 。n 。
*/
public class RedPackets{
public static void main(String[] args) {
int peopleCount = 10;
int totalMoney = 100;
getRandomMoney(peopleCount, totalMoney);
}
private static void getRandomMoney(int peopleCount, int totalMoney) {
List list = new ArrayList();
for(int i=0; i
実行結果:
第1人抢到:6第2人抢到:11第3人抢到:13第4人抢到:2第5人抢到:20第6人抢到:4第7人抢到:5第8人抢到:10
9人目の強盗:20
10人目の強盗:9
もちろん、このアルゴリズムには最適化の場所があります.コメントエリアで議論することを歓迎します.