// 分段的随机命中
// VC2008
#include "stdafx.h"
#include <stdlib.h>
#include <assert.h>
#include <time.h>
// nTotal: 权重总和
// nNum: 分段数
// pData: 命中权重
// 返回: 命中的下标, 出错为-1
int RandomHit(int nTotal, int nNum, int *pData)
{
if(nTotal <= 0 || nNum <= 0)
{
return -1;
}
int nT = nTotal;
for(int i=0; i<nNum; ++i)
{
assert(nT >= 0);
if(rand() % nT < pData[i])
{
// 命中
return i;
}
// 剩下的总数
nT -= pData[i];
}
// 只有pData总和小于nTotal才会运行到这里
return -1;
}
int _tmain(int argc, _TCHAR* argv[])
{
srand(time(0));
int nData[5] = {1,2,3,4,5};
int nTotal = 1+2+3+4+5;
int nSel[5] = {};
int nLoopTime = 10000;
for(int i=0; i<nLoopTime; i++)
{
int nR = RandomHit(nTotal, 5, nData);
nSel[nR]++;
}
for(int i=0; i<5; i++)
{
printf("[%d] = %d (%d%%)\n", i, nSel[i], nSel[i]*100/nLoopTime);
}
return 0;
}
/* 输出
[0] = 619 (6%)
[1] = 1319 (13%)
[2] = 2012 (20%)
[3] = 2636 (26%)
[4] = 3414 (34%)
*/
/*
如果直接rand() %nTotal然后查找命中位置,
也是O(N)复杂度, 但是可以少调用rand().
另外, 如果pData保存的依次是前面的部分总和而构成的升序数组, 则可使用二分查找.
*/