由rand_a()实现rand_b()

简介: 前言阿里的一道随机数生成的题目,这里进行一下解释 题目给定了rand7,如何生成rand3? 思路一个非常直观的思路,就是不断的调用rand7,直到它产生1-3之间的数,然后返回。

前言

阿里的一道随机数生成的题目,这里进行一下解释
 

题目

给定了rand7,如何生成rand3?
 

思路

一个非常直观的思路,就是不断的调用rand7,直到它产生1-3之间的数,然后返回。代码如下:(如果有同学说这里没有3,但是不代表我不能判断和3的大小比较吧)
 
[cpp]  view plain copy
 
  1. #include   
  2.   
  3. int rand_3()  
  4. {  
  5.     int x;  
  6.   
  7.     while (x = rand_7()) {  
  8.         if (x <= 3) {  
  9.             return x;  
  10.         }  
  11.     }  
  12. }  

接下来,就是判断rand_3是否能等概率的产生1,2,3.也就是我们需要计算产生1,2,3的概率是否都是1/3.
 
首先,rand_7可以等概率的产生1-7,我们以rand_3生成1为例,假设:
  • 第一次生成1的概率是1/7
  • 第二次生存1的概率是4/7 * 1/7,因此第一次肯定是生成了大于3的数例如4,5,6,7,概率是4/7
  • 同理,第三次生成1的概率是(4/7)^2 * 1/7
因此,rand_3生成1的概率是P(x=1)= 1/7 +  (4/7) * 1/7 + (4/7)^2 * 1/7 + ... + (4/7)^n-1 * 1/7 //等比数列
                                                  =  1/7 * ((1 - (4/7)^n) / 1 - 4/7) = 1/7 * 7/3 = 1/3
 
同理,可验证生成2,3的概率均为1/3
 

结论

上述证明说明rand3可以等概率的产生1,2,3.从上面的分析,我们可以得出一个更一般的结论:
 
如果a>b,我们一定可以用rand_a去实现rand_b.其中,rand_a是等可能的生成1-a,rand_b是等可能的生成1-b
 
 

扩展

参考链接:
 
现在给定两个生成随机数的函数rand_a和rand_b,rand_a和rand_b分别产生1-a和1-b的随机数,a和b不相等,现在让你用rand_a实现rand_b,方法如下:
  1. 如果a>b,则可以直接采用上述方法
  2. 如果a
 

举例说明

阿里2014年笔试题目,是给定生成1-7的随即函数rand_7,看是否能生成其它随机数?
 
我们先看一下是否能等概率生成1-49,构造rand_49 = 7 * (rand_7 - 1) + rand_7 (ps:别问我7从哪里来的,rand_7既然能随即生成1-7,我当然可以获得到7了)
 
rand_7 - 1能等概率的生成0, 1, 2, 3, 4, 5, 6,每个数的生成概率都是1/7,所以*7之后,可以等概率的生成0,7,14,21,28,35,42,每个数的概率都是1/7
 
既然0,7,14,21,28,35,42每个数的概率都是1/7,当每个数都加上+rand_7之后,则1-49是等概率产生的,1/7 × 1/7 = 1/49,中间不会出现重复数据
 
所以,我们用rand_7产生了rand_49,有了rand_49,按照最初上面过滤的方法,我们当然可以获得任何小于49的随机函数
 
目录
相关文章
|
Kubernetes 容器
rancher 卸载及清理
rancher 卸载及清理
669 0
|
4月前
|
缓存 负载均衡 监控
微服务架构下的电商API接口设计:策略、方法与实战案例
本文探讨了微服务架构下的电商API接口设计,旨在打造高效、灵活与可扩展的电商系统。通过服务拆分(如商品、订单、支付等模块)和标准化设计(RESTful或GraphQL风格),确保接口一致性与易用性。同时,采用缓存策略、负载均衡及限流技术优化性能,并借助Prometheus等工具实现监控与日志管理。微服务架构的优势在于支持敏捷开发、高并发处理和独立部署,满足电商业务快速迭代需求。未来,电商API设计将向智能化与安全化方向发展。
|
11月前
|
Ubuntu Java Linux
如何检查 Java 版本是否兼容
要检查Java版本是否兼容,可在命令行输入“java -version”查看当前安装的Java版本,然后对比目标应用所需的Java版本,确保其满足要求。
796 1
|
消息中间件 Unix Java
进程间通信(IPC)的各种方式与比较
进程间通信(IPC)的各种方式与比较
|
敏捷开发 监控 前端开发
深入理解自动化测试框架Selenium的架构与实践
【4月更文挑战第16天】 在现代软件开发过程中,自动化测试已成为确保产品质量和加快迭代速度的关键手段。Selenium作为一种广泛使用的自动化测试工具,其开源、跨平台的特性使得它成为业界的首选之一。本文旨在剖析Selenium的核心架构,并结合实际案例探讨其在复杂Web应用测试中的高效实践方法。通过详细解读Selenium组件间的交互机制以及如何优化测试脚本,我们希望为读者提供深入理解Selenium并有效运用于日常测试工作的参考。
|
机器学习/深度学习 数据处理 计算机视觉
LabelStudio环境搭建以及使用且解除上传文件限制
LabelStudio是开源的数据标注工具,支持多种类型如文本、图像、音频、视频的标注任务。它具有多种标注类型、可扩展性、团队协作和版本控制等功能,并可在本地、云端或Docker中部署。通过设置环境变量`DATA_UPLOAD_MAX_NUMBER_FILES`,可以解除上传文件数量限制。使用Docker安装时,可运行包含该变量的命令以启动容器,并通过http://localhost:8080访问。遇到文件数限制问题,可增大此变量值以解决。
3485 3
|
弹性计算 人工智能 运维
全面上云这条路,洋葱学院已经走了近7年
洋葱学院需要确保业务稳定性,采用阿里云容器服务与云数据库融合解决方案,在应用不变的情况下,快速平稳实现扩容的问题!
8493 95
全面上云这条路,洋葱学院已经走了近7年
|
IDE 算法框架/工具 开发工具
【学习笔记】用VGG16实现猫狗分类
【学习笔记】用VGG16实现猫狗分类
【学习笔记】用VGG16实现猫狗分类
|
存储 缓存 小程序
小程序数据缓存机制应用
小程序数据缓存机制应用
357 0
小程序数据缓存机制应用
|
XML JSON 安全
生成微信支付二维码接口(2)| 学习笔记
快速学习 生成微信支付二维码接口(2)
468 0