中国の新年はもうすぐ来ます。 Wechat Red Envelopesは、旧正月に非常に人気があります。最近、プロジェクトも赤い封筒をつかみたかったので、赤い封筒の生成アルゴリズムを書きました。
赤いエンベロープ生成アルゴリズムの要件
すべての赤い封筒を事前に作成するか、1つのリクエストで1つの赤い封筒をランダムに生成します
簡単に言えば、それは大きな整数Mを分解するプロセスです(1元、100、100、100などの単位の単位で直接「単位」ユニット)。小さな整数の範囲は[min、max]です。
最も簡単なアイデアは、最初に収益を保証することです。各小さな赤いエンベロープには最小があり、それぞれの要求が0から(最大-min)の範囲の整数をランダムに生成し、次に赤い封筒のお金にMinを追加します。
このアルゴリズムは単純ですが、1つの欠点があります。最終的に生成された赤い封筒はすべて最小のお金かもしれません。言い換えれば、最後の赤い封筒は0.01元である可能性があります。
別の方法は、すべての赤い封筒を事前に作成して、制御が容易になることです。私はすべての赤い封筒を事前に作成することを選択しました。
理想的な赤いエンベロープ生成アルゴリズム
理想的な赤いエンベロープ生成の結果は、平均値の近くに赤い封筒が多く、大きな赤い封筒と小さな赤い封筒が比較的少ないことです。
ご想像のとおり、生成された赤いパケットの数の分布は、正規分布のようなものです。
では、平均線の近くでより多くの値のこの要件を達成するにはどうすればよいですか?
平均周辺の確率を高めることができるアルゴリズムを見つけることです。次に、「拡張」と「収縮」方法を使用して、この効果を達成します。
最初に正方形の場合、次に正方形の範囲で乱数を生成し、次に四角に生成すると、確率はもはや平均になりません。
特定のアルゴリズム:
パブリッククラスHongbaoAlgorithm {static Random = new Random(); static {randomsetSeed(SystemCurrentTimemillis()); } public static void main(string [] args){long max = 200;長いmin = 1; long [] result = hongbaoalgorithmgenerate(100_0000、10_000、max、min);長い合計= 0; for(int i = 0; i <resultLength; i ++){// SystemOutPrintln( "result [" + i + "]:" + result [i]); // systememoutprintln(result [i]);合計 +=結果[i]; } //生成された赤いパケットの合計量が正しいかどうかを確認します。SystemEmoutPrintln( "合計:" +合計); //各お金の赤いパケットの数を計算し、正規分布に近いかどうかを確認します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 ++){systememoutprintln( "" + i + "" + count [i]); }} /*** minとmaxの間に乱数を生成しますが、確率は平均ではなく、minからmax方向までの確率が徐々に増加します。 *最初に正方形に、次に正方形の値範囲内で乱数を生成し、次に四角化します。これにより、「拡張」と「収縮」の効果が生成されます。 * * @param min * @param max * @return */ static long xrandom(long min、long max){return sqrt(nextlong(sqr -min))); } / **** @param合計*合計赤い赤い封筒量* @param count* @param max* @param max* @param minの最大量* @param min*各小さな赤いエンベロープの最小量*各小さな赤い封筒の値の配列*生成された* /公共のstatic [count = max、count、long count、count、long count、long count、count、long count、long count長い平均=合計 /カウント;長いa =平均-min;長いb = max -min; // //このような乱数の確率は実際に変化しており、多数を生成する可能性は小数点以下数を生成する可能性よりも小さくなります。 //これは、ほとんどの赤い封筒が平均周辺の価値を持っていることを達成します。大きな赤い封筒と小さな赤い封筒は少ないです。長距離1 = SQR(平均-min);長距離2 = sqr(max -平均); for(int i = 0; i <resultLength; i ++){//小さな赤い赤い封筒の数は通常、大きな赤い封筒の数よりも高いためです。 //乱数>平均値の場合、小さな赤い封筒が生成される//乱数<平均値が生成されると、大きな赤い封筒が生成される場合(nextlong(min、max)>平均){//平均線のお金を減らす// long temp = min + sqrt(nextlong(range1)); long temp = min + xrandom(min、平均); result [i] = temp;合計 - =温度; } else {//平均線にお金を追加// long temp = max -sqrt(nextlong(range2)); long temp = max -xrandom(平均、max); result [i] = temp;合計 - =温度; }} //まだお金が残っている場合は、小さな赤い封筒に追加してみてください。追加できない場合は、次のものを試してください。 while(total> 0){for(int i = 0; i <resultlength; i ++){if(total> 0 && result [i] <max){result [i] ++;合計 - ; }}} //お金が負の場合、生成された小さな赤い封筒から引き戻す必要があります(合計<0){for(int i = 0; i <resultlength; i ++){if(total <0 && result [i]> min){result [i] - ;合計++; }}} return result; } static long sqrt(long n){//テーブルルックアップに改善しましたか? return(long)mathsqrt(n); } static long sqr(long n){//テーブルの検索は速いですか、それとも速く直接計算されていますか? 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; }}生成された結果をカウントした後、それらは要件に非常に沿っています。
上記はこの記事のすべての内容です。みんなの学習に役立つことを願っています。誰もがwulin.comをもっとサポートすることを願っています。