题目:
给定一个函数rand5(),该函数可以随机生成1-5的整数,且生成概率一样。现要求使用该函数构造函数rand7(),使函数rand7()可以随机等概率的生成1-7的整数。
思路:
很多人的第一反应是利用rand5() + rand()%3来实现rand7()函数,这个方法确实可以产生1-7之间的随机数,但是仔细想想可以发现数字生成的概率是不相等的。rand()%3 产生0的概率是1/5,而产生1和2的概率都是2/5,所以这个方法产生6和7的概率大于产生5的概率。
正确的方法是利用rand5()函数生成1-25之间的数字,然后将其中的1-21映射成1-7,丢弃22-25。例如生成(1,1),(1,2),(1,3),则看成rand7()中的1,如果出现剩下的4种,则丢弃重新生成。
简单实现:
#include <iostream> #include <algorithm> #include <stdio.h> using namespace std; int rand5() { return 1 + rand() % 5; } int rand7() { int x = 0; do { x = 5 * (rand5() - 1) + rand5(); }while(x > 21); return 1 + x%7; } int main() { int i; for (i=0;i<10;i++) printf("%d ",rand7()); printf("\n"); return 0; }
这种思想是基于,rand()产生[0,N-1],把rand()视为N进制的一位数产生器,那么可以使用rand()*N+rand()来产生2位的N进制数,以此类推,可以产生3位,4位,5位...的N进制数。这种按构造N进制数的方式生成的随机数,必定能保证随机,而相反,借助其他方式来使用rand()产生随机数(如 rand5() + rand()%3 )都是不能保证概率平均的。
此题中N为5,因此可以使用rand5()*5+rand5()来产生2位的5进制数,范围就是1到25。再去掉22-25,剩余的除3,以此作为rand7()的产生器。
给定一个函数rand()能产生0到n-1之间的等概率随机数,问如何产生0到m-1之间等概率的随机数?
int random(int m , int n) { int k = rand(); int max = n-1; while(k < m) { k = k*n + rand(); max = max*n + n-1; } return k/(max/n); }
如何产生如下概率的随机数?0出1次,1出现2次,2出现3次,n-1出现n次?
int random(int size) { while(true) { int m = rand(size); int n = rand(size); if(m + n < size) return m+n; } }
相关推荐
【创新工场的笔试题】相关知识点详解 创新工场是一家知名的创业孵化平台,由李开复博士创办,致力于发掘并培养优秀的科技创业者。在招聘过程中,创新工场常常会设置笔试环节,以评估应聘者的综合素质和技术能力。...
IT面试笔试环节是求职者进入腾讯、创新工场、淘宝等知名公司的重要步骤,这些公司的面试题目往往涵盖算法、数据结构、操作系统、网络等多个领域。本文将针对给出的部分面试题目进行解析,帮助读者理解其中涉及的知识...
本文将对这一时期的笔试题目进行详细解析,旨在帮助广大求职者了解创新工场的招聘标准,提升自身的竞争力。 一、创新工场招聘的核心价值观 创新工场在2013年的校园招聘中,主要考察的是应聘者的创新能力、技术实力...
- 面试题目常常涉及基础算法,如五只猴子分桃问题,考查对数学问题的理解和解决能力。该问题实际上是一个数论问题,通过建立数学模型来推导桃子的最小数量。 - 使用rand7()函数构造rand10()的问题,考查对概率分布...
但是,作者鼓励不断学习和分享,并持续关注面试题目的最新动态,例如提到整理了九月和十月份的腾讯、创新工场、淘宝、百度、阿里巴巴和迅雷搜狗等公司的最新面试题。这说明面试题目是随着技术发展和市场需求不断更新...
这篇资料汇集了2012年多个知名IT公司的程序员笔试和面试题目,涵盖了Java程序员需要掌握的各种技术知识点。以下是对这些题目所涉及知识点的详细解释: 1. **字符串操作**: - 反转字符串:这涉及到字符串处理,...
2015创新工场校招研发笔试题.pdf 2015小米校招技术类笔试题.pdf 360校园招聘2015届技术类笔试题.pdf 4399游戏2015校园招聘游戏开发类笔试题.pdf 人人网2015研发笔试卷B.pdf 人人网2015研发笔试卷C.pdf 搜狗2015校园...
“九月腾讯,创新工场,淘宝等公司最新面试三十题(更新至10_04) - 结构之法 算法之道 - 博客频道 - CSDN_NET.mht”更新了近期互联网公司的面试题目;最后,“IT求职宝典.pdf”很可能是一个全面的求职指南,包含...
- **创新工场**:创业导向,可能会注重创新思维、产品设计和前沿科技的理解。 - **美团**:重点可能是O2O(线上线下融合)服务的后台技术支持,如订单处理、推荐系统等。 - **京东**:物流和电商平台相关技术,如...
2015创新工场校招研发笔试题.pdf 2015届阿里巴巴校招测试开发工程师在线笔试题.pdf 2015年欢聚时代(YY)校园招聘Java笔试题目.pdf 2015年欢聚时代校园招聘C++笔试题目.pdf 2015网易校招JAVA开发工程师.pdf...
2015创新工场校招研发笔试题.pdf 2015小米校招技术类笔试题.pdf 2015届阿里巴巴校招测试开发工程师在线笔试题.pdf 2015年欢聚时代校园招聘C++笔试题目.pdf 2015年欢聚时代(YY)校园招聘Java笔试题目.pdf 2015...