等概率随机分配彩票问题

抽签是一种既公平，又随机的游戏，很容易用O(n)复杂度算法实现。本文来讨论一中执行效率更高的算法。

代码很精简，但是不太好理解，如下，

int get_rand_pos(int bkt_num)
{
	int tmp = 0;
	int pos = 0;
	while(tmp < bkt_num) {
		pos = tmp;
		tmp = (pos + 1) / rand();
	}
	return pos;
}

手算过程如下

代码验证过程如下，

using namespace std;

#define bkt_num 1000

double trans_prob[bkt_num][bkt_num] = { 0 };
double bkt_prob[bkt_num] = { 0 };

int main()
{
	double sum = 0;

	for (int i = 0; i < bkt_num; i++) {
		for (int j = i + 1; j < bkt_num; j++) {
			trans_prob[i][j] = (1 - 1.0 * (i + 1) / (j + 1)) - (1 - 1.0 * (i + 1) / j);
		}
		trans_prob[i][i] = 1.0 * (i + 1) / bkt_num;
	}

	bkt_prob[0] = 1;
	for (int i = 0; i < bkt_num; i++) {
		for (int j = i + 1; j < bkt_num; j++) {
			bkt_prob[j] += bkt_prob[i] * trans_prob[i][j];
		}
		bkt_prob[i] = bkt_prob[i] * trans_prob[i][i];
		sum += bkt_prob[i];
	}

	_asm int 3

	return 0;
}