蓄水池算法等概率问题
2021/12/30 17:09:21
本文主要是介绍蓄水池算法等概率问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
蓄水池算法
假设有一个源源吐出不同球的机器,只有装下10个球的袋子,每一个吐出的球,要么放入袋子,要么永远扔掉,如何做到机器吐出每一个球之后,所有吐出的球都等概率被放进袋子里?
思路:第k个球到来的时候,以10/k的概率放入袋子,扔的时候10个里面随机选一个
public class RandomBox { private int[] bag; private int N; private int count; public RandomBox(int capacity) { bag = new int[capacity]; N = capacity; count = 0; } private int rand(int max) { return (int) (Math.random() * max) + 1; } public void add(int num) { count++; if (count <= N) { bag[count - 1] = num; } else { if (rand(count) <= N) { bag[rand(N) - 1] = num; } } } }
470. 用 Rand7() 实现 Rand10()
已有方法 rand7
可生成 1 到 7 范围内的均匀随机整数,试写一个方法 rand10
生成 1 到 10 范围内的均匀随机整数。
不要使用系统的 Math.random()
方法。
方法:
用4个二进制位表示,最多可以表示0-15, 只取1-10 使用rand7等概率的返回0或1 1-3 -> 0 4-6 -> 1 7 -> 重来
public int rand10() { int r; while(true) { r = (rand_01()<<3)+(rand_01()<<2)+(rand_01()<<1)+rand_01(); if(r>=1 && r<=10) { break; } } return r; } public int rand_01(){ int r7; int t; while(true) { r7 = rand7(); if(r7 == 7) { continue; }else { if(r7 >= 1&& r7 <= 3) { t = 0; }else { t = 1; } break; } } return t; }
这篇关于蓄水池算法等概率问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)