`

创新工厂面试题目

 
阅读更多

题目:
给定一个函数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面试笔试--腾讯/创新工场/淘宝公司笔试面试题目总结及答案

    IT面试笔试环节是求职者进入腾讯、创新工场、淘宝等知名公司的重要步骤,这些公司的面试题目往往涵盖算法、数据结构、操作系统、网络等多个领域。本文将针对给出的部分面试题目进行解析,帮助读者理解其中涉及的知识...

    创新工场2013校园招聘题

    本文将对这一时期的笔试题目进行详细解析,旨在帮助广大求职者了解创新工场的招聘标准,提升自身的竞争力。 一、创新工场招聘的核心价值观 创新工场在2013年的校园招聘中,主要考察的是应聘者的创新能力、技术实力...

    九月腾讯,创新工场,淘宝等公司最新面试三十题(第171-200题)

    - 面试题目常常涉及基础算法,如五只猴子分桃问题,考查对数学问题的理解和解决能力。该问题实际上是一个数论问题,通过建立数学模型来推导桃子的最小数量。 - 使用rand7()函数构造rand10()的问题,考查对概率分布...

    数据结构+算法面试100题全部答案集锦

    但是,作者鼓励不断学习和分享,并持续关注面试题目的最新动态,例如提到整理了九月和十月份的腾讯、创新工场、淘宝、百度、阿里巴巴和迅雷搜狗等公司的最新面试题。这说明面试题目是随着技术发展和市场需求不断更新...

    2012程序员笔经面经题-谷歌,网易有道,网易,创新工场等

    这篇资料汇集了2012年多个知名IT公司的程序员笔试和面试题目,涵盖了Java程序员需要掌握的各种技术知识点。以下是对这些题目所涉及知识点的详细解释: 1. **字符串操作**: - 反转字符串:这涉及到字符串处理,...

    互联网行业面试笔试真题资料BAT谷歌微软等笔试面试真题复习资料合集200MB.zip

    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校园招聘笔试题大合集

    2015创新工场校招研发笔试题.pdf 2015届阿里巴巴校招测试开发工程师在线笔试题.pdf 2015年欢聚时代(YY)校园招聘Java笔试题目.pdf 2015年欢聚时代校园招聘C++笔试题目.pdf 2015网易校招JAVA开发工程师.pdf...

    最新出炉2015届中国顶级IT互联网公司校招笔试题

    2015创新工场校招研发笔试题.pdf 2015小米校招技术类笔试题.pdf 2015届阿里巴巴校招测试开发工程师在线笔试题.pdf 2015年欢聚时代校园招聘C++笔试题目.pdf 2015年欢聚时代(YY)校园招聘Java笔试题目.pdf 2015...

Global site tag (gtag.js) - Google Analytics