首页 > 代码库 > 概率/随机数算法
概率/随机数算法
0-1等概率问题
问题描述
- 一个随机数产生器以概率P生成0,以概率(1-P)生成1,怎样生成等概率的0和1?
主要思路
- 如果用这个产生器产生两个位,出现00的概率为P^2,出现01的概率为P(1-P),出现10的概率为P(1-P),而出现11的概率为(1-P)^2。故而可以用10表示1,01表示0,从而保证生成0和1的概率是相同的。
代码实现
int generate01(int (*func)()) { if (func == NULL) return -1; int num1 = -1; int num2 = -1; int ret = -1; while(num1 != num2){ num1 = func(); num2 = func(); if (num1 == 1 && num2 == 0) { ret = 1; break; } else if (num1 == 0 && num2 == 1) { ret = 0; break; } } return ret; }
0-1问题扩展
- 利用这个随机数生成器,等概率的生成1,2,……,n
主要思路
- 利用上面实现的等概率生成0-1的生成器,等概率的生成k为二进制的bit,而其表示的整数值X在0~n-1的范围时,输出X+1,否则重复产生。
代码实现
int generateRandomNum(int max) { if (max < 1) { return -1; } int bit_num = 0, i = 0; int result = 0; while((0x01 << bit_num) < max) ++bit_num; //while(result > n) { while(bit_num > i) { if (generate01()) result |= 0x01 <<bit_num; //result |= 0x01<<i i++; } i = 0; // } return result; }
不重复随机数的产生
问题描述
- 随机产生0~n-1中的k个不重复的随机数。
主要思路
- 借用蓄水池算法。先定义一个1~n-1的数组,然后从中抽样K个数。
生成给定范围的随机数
问题描述
给定能随机生成整数1~5的函数,写出能随机生成整数1~7的函数
解决思路
产生K个数(k>1),假定产生的数分别为N1,N2,……Nk,则产生的数为:N1-1+(N2-1)*5 + (N3-1)*5^2,……,(Nk-1)*5^(k-1),即产生的数位于(0,5^(k-1))区间呢。然后把区间等分成k分,则产生的随机数位于(0~6),然后+1即可。如果位于K等分的余数范围,则重新执行上述过程。(PS:不用担心余数问题,当K取3时,落到余数范围的概率已经降为6/125,而且余数不会导致概率的问题,只会影响效率。次解法相当于五进制)
代码实现
int generateRandom(int n) { if (n < 1) return -1; unsigned long long result = 0; for (int i = 0; i < n; i++) { result += rand5(); } result /= 5; return result; }
如何随机选取1000个关键字
问题描述
- 给定一个数据流,其中包含无穷尽的搜索关键字(比如,人们在谷歌搜索时不断输入的关键字)。如何才能从这个无穷尽的流中随机的选取1000个关键字?
主要思路
- 利用蓄水池算法。先生成一个大小为1000的数组,将前1000个关键字填入数组中,随后的关键字随机进行交换。
在半径为1的圆中随机选取一点
主要思路
- 假设圆心(0,0)。在X轴[-1,1],Y轴[-1,1]的正方形内随机选点,然后判断该点是否在圆内。正方形的面积为4,圆形的面积为Pi,故而正方形内的随机点落在圆内的概率为: Pi/4
代码实现
void generatePoint(double*x, double *y, int r){ int base = 10000; while (pow(*x, 2) + pow(*y, 2) > pow(r, 2)) { *x = random() % 10000; *y = random() % 10000; *x = (2 * r / (*x)) - r; *y = (2 * r / (*y)) - r; } }
蓄水池算法
问题描述
- 从N个数中,随机抽取K个,是的每个数的抽取概率相同,并且事先不知道K的值
主要思想:
- 保持一个集合(这个集合中的每个数字出现),作为蓄水池,依次遍历所有数据的时候以一定概率替换这个蓄水池中的数字。将前K个元素都放到水库中,然后对之后的第i个元素,以k/i的概率替换掉这个水库中的某一个元素。
方法证明:
- 初始情况。水库中k个元素的出现概率都一致,都是1。
- 第一步:处理第k+1个元素。分两种情况:① 元素全部都没有替换;② 其中某个元素被k+1元素替换。
- 对于case ②:第k+1个元素被选中的概率是k/(k+1),故而这个新元素在水库中出现的概率就一定是k/(k+1)。而水库中剩余的元素出现的概率也就是1-P(P为元素被替换的概率)。水库中任意一个元素被替换的概率为:(k/k+1) * (1/k) = 1/(k+1)。而旧元素出现的概率为k/k+1。即旧元素和新元素出现的概率是相等的。
- 对于case①:当没有元素被替换时,每个元素出现的概率是一样的。具体为:1-P(P为第k+1个元素被选中) = 1 - k/(k+1) = 1/(k+1)
- 利用归纳法:
- 对于第k+i个元素,其中i ∈(0, length-k)。其出现在水库中的概率为k/(k+i)。利用上面的两步可以得出结论。
算法实现:
int impounding_reservoir(int *array,int length, int k) { if (k <= 0 || array == NULL || length <= 0 || k > length) { return 0; } int result[k]; int i = 0, j = 0; srand((unsigned) time(NULL)); for (i = 0; i < k; i++) { result[i] = array[i]; } for (i = k; i < length; i++) { j = random() % length; if(j < k) result[j] = array[i]; } for (i = 0; i < k; i++) printf("%d ", result[i]); printf("\n"); return k; }
产生1~400范围内不重复的20个随机数
int * generateRandom(int *array, int num, int start, int end) { int size = end / 32 + end % 32 > 0 ? 1: 0; int tmp_arr[size] = {0}; int index = 1, count = 0; srand(time(NULL)); while(count < num){ index += rand() ; index %= 400 + 1; if (test_bit(tmp_arr, index)) { continue; } else { set_bit(tmp_arr, index); array[count] = index; index = 1; count++; } } return array; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。