民族建设集团有限公司官方网站,国内最常用的邮箱,无锡高端网站定制,手机网站可以做百度商桥吗目录 前言问题介绍解决方案代码编写java语言版本c语言版本c语言版本 思考感悟写在最后 前言
当前所有算法都使用测试用例运行过#xff0c;但是不保证100%的测试用例#xff0c;如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识#xff01; 问题介… 目录 前言问题介绍解决方案代码编写java语言版本c语言版本c语言版本 思考感悟写在最后 前言
当前所有算法都使用测试用例运行过但是不保证100%的测试用例如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识 问题介绍
原问题 存在一个吐球的机器该机器吐球的顺序是 1号球2号球3号球…m号球,一共吐m个求 现在你有一个袋子大小是nnm当m个球吐完之后你的袋子中应该有n个球那么现在设计一个算法保证袋子中的n个球每一个球进入袋子中的概率都是相等的都是n/m
解决方案
原问题 解法很简单证明在后面 1、首先创建一个数组作为“袋子”用来获取等概率的结果 2、循环将球放入袋子在袋子装满之前所有球都放入袋子 3、如果袋子满了此时为第i个球判断rand(i)是否大于n如果小于袋子的大小则随机找袋子中的某个位置覆盖否则不放入 4、循环完成即可此时袋子中每一个球放入的概率都是n/m
代码编写
java语言版本
原问题 方法一:
/*** 二轮测试蓄水池算法* param k* param max* return*/public static int[] getKNumRandCp1(int k, int max) {int[] container new int[k];// 初始化//for (int i 0; i max; i) {// container[i] i 1;//}for (int i 0; i max; i) {if (i k) {container[i] i 1;continue;}// 如果随机数没有超过k则随机替换一个if (rand(i) k) {container[randCp1(k) - 1] i;}}return container;}public static int randCp1(int num) {return (int)(Math.random() * num 1);}public static void main(String[] args) {CommonUtils.printArr(getKNumRandCp1(5, 9));}
c语言版本
正在学习中
c语言版本
正在学习中
思考感悟
如果不看证明我其实不知道为什么这样就一定是等概率的。 然后看了书里面的概率计算公式之后算是有些明白了 首先我们看看第i号球如何才能被选中踢出去被n1号球替换 首先要满足两个条件1、rand(n1) n 2、rand(n) i 那么这两个事件的概率乘积就是i被k1号球替换的概率n/(n1) * (1/n) 那么反过来i球留下来的概率就是 1- 1/(n1) nn1 同理可以计算出没有被n2n3换出来的概率 n2 (n1)/(n2) n3 : (n2)/(n3) ok如果在每一轮的随机下最终i球留下来没有被替换出去那么就算是i球被选中了所以接下来我们求n轮后i号球留下来的概率即可 也就是从n1一直到m所有没有被换出去的概率乘积 n/n1 * (n1)/(n2) * (n2)/(n3) … m-1/m n/ m
这个概率刚好是等概率替换的概率完美的证明~
写在最后 方案和代码仅提供学习和思考使用切勿随意滥用如有错误和不合理的地方务必批评指正~ 如果需要git源码可邮件给2260755767qq.com 再次感谢左大神对我算法的指点迷津
