微信紅包アルゴリズムコード実現

32488 ワード
アルゴリズム 雑文
微信紅包アルゴリズム思考学習研究
暇な時は大丈夫です.微信の紅包アルゴリズムを研究して、実現できる他のアルゴリズムを考えて、略して記録します.
WeChat Packetのランダムアルゴリズムは、赤いカバンを出す時にいいということではなく、ユーザーがお年玉を受け取る時に、リアルタイムでお客さんがお金を受け取る金額を計算します.だから、おひねりのアルゴリズムはどのように公平に受取人が受け取るおひねりの金額を算出するかがポイントです.問題に変えることができます.資金がSで、個数がNの紅包池からランダムにランダムに一つの乱数を取って、保証を要求します.
総乱法
計算方法の説明:現在の紅包池の金額はB=100と仮定し、受取人数はP=10であり、その中からランダムな紅包のアルゴリズムを受け取る時、お客様ごとに紅包が受領できることを保証するために、最小予約金額K=P=10を保留して、他の部分に直接ランダム値R=rand()%(B-P)=rand(%)90を取り、最後にR+1を今回ランダムに受け取る紅包の金額とします.長所と短所:アルゴリズムが不公平で、平均値の範囲内で変動していないので、結果の差が大きいです.主な実現アルゴリズムは以下の通りである.
//      
//     ：           B=100，      P=10，              
//             ，         K=P=10,             
// R=rand()%(B-P)=rand()%90，   R+1             
//    ：     ，            ，      
static size_t PickRand(size_t nBal, size_t nNum)
{
    size_t nPick = nBal - nNum;
    if (nNum != 1)
    {
        nPick = (nPick ? rand() % nPick : 0) + 1;
    }
    else
    {
        nPick = nBal;
    }
    cout << "   ，         :" << nPick / 100.0f << " " << endl;
    return nPick;
}
平均値加減法
アルゴリズムの説明:現在の紅包池の金額をB=100と仮定して、受領人数はP=10であり、その中からランダムな紅包のアルゴリズムを受け取ると、先に取った平均数AVG=B/P=10を平均数で加算または平均数以内の乱数RAVG=rand()/AVGとして、紅包池からランダムな金額の紅包R=AVGRAVG=AVG=AVG=AVG=AVG=AVG=AVG=AVG=AVG=AVG=AVG=AVG=AVG=AVG=AVG=AVGのいずれかを取得することができます.注意して、紅包池内のP=1の場合、ランダムな紅包の金額を直接取ったのは紅包池の金額B、つまりR=Bの長所短所です.アルゴリズムが公平で、平均の範囲内で変動します.
//       
//     ：           B=100，      P=10，              ，
//       AVG=B/P=10，                         RAVG=rand()/AVG，
//                     R=AVG+RAVG R=AVG-RAVG
//   ，     P=1 ，                B， R=B
//    :    ，        
static size_t PickAvgPM(size_t nBal, size_t nNum)
{
    //        
    size_t nPick = 1;

    if(nNum != 1)
    {
        //        
        nBal -= nNum;

        //     :   ±        
        size_t nAvg = nBal / nNum;
        size_t nRand = (nAvg ? rand() % nAvg : 0);
        nAvg += (rand() % 2 ? nRand : 0 - nRand);
        nPick += nAvg;
    }
    else
    {
        nPick = nBal;
    }

    cout << "   ，         :" << nPick / 100.0f << " " << endl;
    return nPick;
}
ウィーチャットの包み方
アルゴリズムの説明:現在の紅包池の金額をB=100と仮定して、受取人数はP=10で、その中からランダムな紅包のアルゴリズムを受け取る時、先に取った平均数AVG=B/P=10を計算して、今回の受領金額の範囲は2 AVG、つまり1から20で、このように紅包池からランダムな金額の紅包R=rand(%(2 AVG)=1+20).注意して、紅包池内のP=1の場合、ランダムな紅包の金額を直接取ったのは紅包池の金額B、つまりR=Bの長所短所です.アルゴリズムが公平で、平均の範囲内で変動します.
//      
//     ：           B=100，      P=10，              ，
//       AVG=B/P=10，               2*AVG， 1 20，
//                     R=rand()%(2*AVG)=1 + rand()%20
//   ，     P=1 ，                B， R=B
//    :    ，        
static size_t PickAvgWx(size_t nBal, size_t nNum)
{
    size_t nPick = nBal;
    if (nNum != 1)
    {
        //    *2
        //    -                    
        size_t nAvg = (nBal-nNum)/nNum;
        nPick = (nAvg? rand()%nAvg:0) + 1;
    }
    cout << "   ，         :" << nPick / 100.0f << " " << endl;
    return nPick;
}
テストコード
#include 
#include 
#include 
#include 
#include 

using namespace std;
class CDivideRedPacket
{
private:
    size_t  _nNum;       //     
    size_t  _nBal;       //      ，    。             
    string  _strRemark;  //     

    size_t  _nPicked;    //        
    size_t  _nPickedBal; //        

public:
    //       
    CDivideRedPacket() { Reset(); }

    //     
    bool SetPara(size_t nNum, double fBal, string strRemark = "    ，    ")
    {
        //     
        Reset();
        if (fBal <= 0)
        {
            cout << "        0" << endl;
            return false;
        }
        _nBal = static_cast<size_t>(fBal * 100);
        if (nNum == 0)
        {
            cout << "        0" << endl;
            return false;
        }
        if (nNum > _nBal)
        {
            cout << "      ，    ，   " << endl;
            return false;
        }
        _nNum = nNum;
        _strRemark = strRemark;
        cout << "      ：  [" << _nNum << "]   [" << _nBal / 100.0f << "]   [" << _strRemark << "]" << endl;
        return true;
    }

    //     
    bool Pick()
    {
        //      
        if (_nNum == 0 || _nNum == _nPicked)
        {
            assert(_nBal == _nPickedBal);
            cout << "    ，      "<< endl;
            return false;
        }
        //     
        _nPickedBal += PickAvgWx(_nBal - _nPickedBal, _nNum - _nPicked++);
    }

private:
    void Reset()
    {
        _nBal = 0;
        _nNum = 0;
        _strRemark = "    ，    ";
        _nPicked = 0;
        _nPickedBal = 0;
    }

    //    
    //     ：           B=100，      P=10，              
    //             ，         K=P=10,             
    // R=rand()%(B-P)=rand()%90，   R+1             
    //    ：     ，            ，      
    static size_t PickRand(size_t nBal, size_t nNum)
    {
        size_t nPick = nBal - nNum;
        if (nNum != 1)
        {
            nPick = (nPick ? rand() % nPick : 0) + 1;
        }
        else
        {
            nPick = nBal;
        }
        cout << "   ，         :" << nPick / 100.0f << " " << endl;
        return nPick;
    }

    //       
    //     ：           B=100，      P=10，              ，
    //       AVG=B/P=10，                         RAVG=rand()/AVG，
    //                     R=AVG+RAVG R=AVG-RAVG
    //   ，     P=1 ，                B， R=B
    //    :    ，        
    static size_t PickAvgPM(size_t nBal, size_t nNum)
    {
        //        
        size_t nPick = 1;

        if(nNum != 1)
        {
            //        
            nBal -= nNum;

            //     :   ±        
            size_t nAvg = nBal / nNum;
            size_t nRand = (nAvg ? rand() % nAvg : 0);
            nAvg += (rand() % 2 ? nRand : 0 - nRand);
            nPick += nAvg;
        }
        else
        {
            nPick = nBal;
        }

        cout << "   ，         :" << nPick / 100.0f << " " << endl;
        return nPick;
    }

    //      
    //     ：           B=100，      P=10，              ，
    //       AVG=B/P=10，               2*AVG， 1 20，
    //                     R=rand()%(2*AVG)=1 + rand()%20
    //   ，     P=1 ，                B， R=B
    //    :    ，        
    static size_t PickAvgWx(size_t nBal, size_t nNum)
    {
        size_t nPick = nBal;
        if (nNum != 1)
        {
            //    *2
            //    -                    
            size_t nAvg = (nBal-nNum)/nNum;
            nPick = (nAvg? rand()%nAvg:0) + 1;
        }
        cout << "   ，         :" << nPick / 100.0f << " " << endl;
        return nPick;
    }
};

int main()
{
    CDivideRedPacket rp;
    srand(time(NULL));

    int nNum = 0;
    double fBal = 0.0f;
    while (true)
    {
        nNum = 1 + rand() % 20;
        fBal = (1 + rand() % 1000000) / 100.f;
        if (rp.SetPara(nNum, fBal))
        {
            while (rp.Pick());
        }

        cout << "-----END----" << endl;
        //          ，         ，          
        Sleep(3000);
    }
    return 0;
}
実行結果例
      ：  [4]   [175.05]   [    ，    ]
   ，         :36.35 
   ，         :38.87 
   ，         :26.84 
   ，         :72.99 
    ，      
-----END----
      ：  [6]   [237.17]   [    ，    ]
   ，         :10.41 
   ，         :28.64 
   ，         :41.67 
   ，         :9.61 
   ，         :55.63 
   ，         :91.21 
    ，      
-----END----
      ：  [8]   [264.63]   [    ，    ]
   ，         :9.36 
   ，         :14.42 
   ，         :14.78 
   ，         :37.58 
   ，         :4.21 
   ，         :20.68 
   ，         :54.21 
   ，         :109.39 
    ，      
-----END----
The greatest common divisor gcd(最大公約数)
K-近隣アルゴリズム(怠惰アルゴリズム)