2 liuxxoo88 liuxxoo88 于 2016.01.24 18:53 提问

一个编程面试题,只要写出伪代码就可以了

假设有如下两个函数 rand3()可以产生随机的0 1 2,rand5()可以产生随机的0 1 2 3 4,现在请你利用它编写一个函数rand7(),产生0~6的随机数

23个回答

qq_27183003
qq_27183003   Ds   Rxr 2016.01.26 00:02

不是那么完美:

 int rand7()
{
    int sum;
    switch(rand3())
    {
    case 0:
        sum=rand5();//0,1,2,3,4
        break;
    case 1:
        sum=rand5()+5;//5,6,7,8,9
        break;
    case 2:
        do
        {
            sum=rand5()+10;//10,11,12,13,14
        }while(sum!=14);
        break;
    }
    sum%=7;//0,1,2,3,4,5,6
    return sum;
}
qq_27183003
qq_27183003 总结了一下,发在了我的博客上:http://blog.csdn.net/qq_27183003/article/details/50611113
2 年多之前 回复
WinsenJiansbomber
WinsenJiansbomber 回复ysuwood: 这回看到了,要再分析一下。如果while==14,就直接将0的概率截掉一大块了。代码近乎实用,但是还有个问题,大家可能没留意到:case 0 - 2 的概率分布是平均,也就是说,出现0-4和5-9,还有10-14的概率是一样的,那么求模后的结果好像就是概率平均分布的!其实不然,当while条件中把14废了之后,rand5出现14的概率还在,此时只好重新抽,这,就是这里,意味着出现14的概率转接到了10-13这几个数上,所以这几个数不明显地比0-9这几个数的概率要高。之所以说不明显,是因为经过了求模的运算,它有平滑概率的作用。@caozhy 好像也没注意到这个情况。
2 年多之前 回复
qq_27183003
qq_27183003 回复Jimbo: 发贴后就发现逻辑错了:while(sum==14); 在下面,你没看到吗?
2 年多之前 回复
WinsenJiansbomber
WinsenJiansbomber 出现0的概率是50%!50%!50%啊
2 年多之前 回复
WinsenJiansbomber
WinsenJiansbomber 点赞的小伙伴们,你们造这段代码结果是什么吗?
2 年多之前 回复
caoluchao
caoluchao 回复Chely_Yi: 当然不是了,14都已经作废了,还有概率在里面的????
2 年多之前 回复
Chely_Yi
Chely_Yi 回复林深: 应该没有问题 就像从箱子里拿球 每次拿到14就放回再拿一次而已 拿到其他球的概率还是1/5
2 年多之前 回复
leilba
leilba 回复caozhy: 这样的话0~9取到的概率是 1/(3*5),而10~13取到的概率是1/(3*4),取值不等概率了呀
2 年多之前 回复
caozhy
caozhy 回复ysuwood: 这回对了,和我的差不多思路。
2 年多之前 回复
qq_27183003
qq_27183003 逻辑错了:while(sum==14);
2 年多之前 回复
qq_15622913
qq_15622913   2016.01.28 10:03

利用预置数组
int rand7(){
int a[][]={
0,1,2,
3,4,5,
6,0,1,
2,3,4,
5,6,7}
int row=rand5;
int col =rand3 ;
int rand7=7;
while(rand7=7){
rand7=a[row][col];
}
return rand7;
}

zhao_zhi
zhao_zhi 这个方法挺好
2 年多之前 回复
WinsenJiansbomber
WinsenJiansbomber 看到这样的代码,真崩溃。
2 年多之前 回复
leilba
leilba 很赞的方法,思路清晰,效率也非常高
2 年多之前 回复
galiniur0u
galiniur0u   2016.01.28 16:08

int rand7()
{
return rand3() + rand5();
}

WinsenJiansbomber
WinsenJiansbomber 好像很靠谱,但是,概率分布是一座对称的高山。
2 年多之前 回复
ynuCyan
ynuCyan   2016.01.24 19:08

rand7=rand3+rand5
rand7=rand3+rand3+rand3
rand7=rand3*2+rand3
rand7=rand3*3-rand5
应该还有一些,

WinsenJiansbomber
WinsenJiansbomber rand3+rand3+rand3这种,一眼看上去好像很正确,其实它是典型的单峰形,中间的数出现概率最高,两边的就最低。无数据,根本想不到它们有多离谱,我测试了一下999999次统计,出现0、3、6的概率数据:0 -> 36989 3.70% 3 -> 258977 25.90% 6 -> 36865 3.69%
2 年多之前 回复
caozhy
caozhy   Ds   Rxr 2016.01.24 19:13
 int rand7()
{
    int x5 = 7;
        while (x5 > 6)
        {
    int x3 = 2;
        while (x3 > 1)
        {
            x5 = rand(5);
                if (x3 == 1) x5 = x5 + 5;
                if (x5 < 7) return x5;
        }
        }
}
Moluth
Moluth   2016.01.24 20:09

int a=rand5+rand5+…+rand5 + rand3+…+rand3
return a%8;

个数自己决定。

WinsenJiansbomber
WinsenJiansbomber 肯定是没花脑子写的
2 年多之前 回复
leilba
leilba   Rxr 2016.01.26 09:07

优化了的方法

 //从均匀的0~20里面取mod
int rand7() {

    int sum = 0;
    for (int i=0;i<7;i++) {
        sum+= rand3()+i*3;
    }
    return sum%7;
}

//从均匀的0~34里面取mod
int rand7() {

    int sum = 0;
    for(int i=0;i<7;i++) {
        sum += rand5()+i*5;
    }
    return sum%7;
}
leilba
leilba 回复Jimbo: 第一个完全是错的,第二个从概率上讲的话分别是:0:0.143066 1:0.143002 2:0.142822 3:0.142643 4:0.142643 5:0.142822 6:0.143002 只能说是近似,但是也不正确
2 年多之前 回复
leilba
leilba 回复Jimbo: 确实是错的
2 年多之前 回复
WinsenJiansbomber
WinsenJiansbomber 第一例就是一个双峰形结果,倒是后面这一例概率上还算得上平均,因为0~34共35个数是平均分布且可以取7的模。
2 年多之前 回复
WinsenJiansbomber
WinsenJiansbomber 这个思路会领人到泥潭
2 年多之前 回复
WinsenJiansbomber
WinsenJiansbomber 这个思路不对吧!
2 年多之前 回复
WinsenJiansbomber
WinsenJiansbomber 这个思路不对吧!
2 年多之前 回复
leilba
leilba 回复caoluchao: 感谢指正
2 年多之前 回复
caoluchao
caoluchao sum有2187种不同的值,如果这2187不是7的倍数,因此也不是在0~6之间均匀出现概率
2 年多之前 回复
u012414995
u012414995 正解,叼炸天的代码,好简洁的说。
2 年多之前 回复
leilba
leilba 二选一
2 年多之前 回复
qq_27183003
qq_27183003   Ds   Rxr 2016.01.28 23:24

看了各位算法经测试,楼上预置数组的方法是正确的:

 #include<stdlib.h>
#include<stdio.h>
#include <time.h>
int rand5()
{
    return rand()%5;
}

int rand3()
{
    return rand()%3;
}
int rand7()
{
    int a[5][3]={
        0,1,2,
        3,4,5,
        6,0,1,
        2,3,4,
        5,6,7};
    int row,col;
    do 
    {
        row = rand5();
        col = rand3();
    } while(a[row][col]==7);

    return a[row][col];
}

int main()
{ 
    int re[7]={0};
    srand( (unsigned)time( NULL ) );
    for(int i=0;i<100000;i++)
    {
        re[rand7()]++;
    }

    for(int i=0;i<7;i++)
    printf("re[%d]=%d, %2d%%\n",i,re[i],int(re[i]/1000.0+0.5));
    return 0; 
}

leilba
leilba   Rxr 2016.01.28 23:28

 int rand7() {

    while (true) {
        switch (rand3()) {
            case 0:
                return rand3();     //0,1,2
            case 1:
                return rand3()+3;   //3,4,5
            case 2:
                if (rand3()) {      // 取到7,8重新取
                    continue;
                }
                return 6;           // 6
        }
    }
}
leilba
leilba 回复Jimbo: 可以用数学极限法证明,第一轮,取到0~6视为有效,为7/9,针对其中一个有效数,概率为(7/9)*(1/7)=1/9,但是取到7、8无效,继续重取,也就是本轮需要重取的概率为2/9。第二轮也是同样道理,在第二轮中,在本轮中针对一个有效数取到的概率为1/9,所以一二两轮,总计针对某一个有效数取到的概率为1/9 + (1/9)(2/9),如果第二轮还是没有落在有效区间,继续下一轮,这样下去的话,针对某一个有效数取到的概率将会是: 1/9 + (1/9)(2/9) + (1/9)(2/9)^2 + ... (1/9)(2/9)^n .... 也就是 1/9 * (1+2/9 + (2/9)^2+...(2/9)^n+....) ,公比为2/9的等比数列求和,当n趋于无穷的时候,值为1/7,也就是说,最后取到0~6的概率都为1/7。。
2 年多之前 回复
leilba
leilba 回复Jimbo: 哪个数的概率不一样?
2 年多之前 回复
WinsenJiansbomber
WinsenJiansbomber 这个有问题,概率分布不平均,参考我的博文《一个随机数引发的血案》http://blog.csdn.net/WinsenJiansbomber/article/details/50604653
2 年多之前 回复
leilba
leilba 用rand5()也是同样的思路
2 年多之前 回复
qq_27183003
qq_27183003   Ds   Rxr 2016.01.29 00:39

修正:

 int rand7()
{
    int sum;
    do
    {
        switch(rand3())
        {
        case 0:
            sum=rand5();//0,1,2,3,4
            break;
        case 1:
            sum=rand5()+5;//5,6,7,8,9
            break;
        case 2:
            sum=rand5()+10;//10,11,12,13,14
            break;
        }
    }while(sum==14);
    sum%=7;//0,1,2,3,4,5,6
    return sum;
}
共23条数据 1 3 尾页
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
面试题之用伪代码设计缓存
package com.ThreadLearn.test; import java.util.*; import java.util.concurrent.locks.ReadWriteLock; import java.util.concurrent.locks.ReentrantReadWriteLock; //面试题,设计一个缓存系统;用伪代码实现 public class Cac
百度2014校园招聘笔试题 ——深度学习算法研发工程师.
一、简答题 1.深度神经网络目前有哪些成功的应用?简述原因。(10分)   2.列举不同进程共享数据的方式(至少三种)。(10分)   3.对于N个样本,每个样本为D维向量,采用欧式距离使用KMN做类预测。(10分) 1).给出预测时间复杂度。 2).当N很大时,有哪些方法可以降低复杂度? 3).k取值的大小对预测方差和偏差有何影响?
面试题编程题写一个singleton(单例)出来
步骤是这样的,    1、定义类里面的无参构造为私有的,在类创建一个静态的实例    2、定义一个静态的方法,使用类名直接调用的,返回这个实例即可    pbulic class Singleton{        private singletion (){};        private static singleton =new singleton();        public sta...
Java学习笔记——面试常客:写出一个死锁的例子
现在的面试挺蛋疼,为了考察大家的语言掌握水平,类似这样的题特别多,不过在某个角度来说确实能看出一个人对某个知识点的理解,就比如今天这个死锁的小例子,主要考察大家对线程死锁概念的理解程度,也考察大家对java语言的敲代码水平,下面是一个死锁的简单例子:
伪代码描述归并排序算法
从今天开始,我就要学习写伪代码了。都说实践是最好的老师,所以我希望通过对算法的描述来学习伪代码。百度百科上介绍,伪码(Pseudocode)是一种算法描述语言。使用伪码的目的是使被描述的算法可以容易地以任何一种编程语言(Pascal,C,Java等)实现。归并排序是分治法(Divide and conquer)一个非常典型的应用,时间复杂度为O(nlogn),是一种稳定排序的算法。 它的主要思想是
ssm面试题 最新
1.很新的面试题2.很全的面试题3.很重点的面试题 框架Struts2与Struts1的面试题###1.Struts2与Struts1的联系与区别?为什么要用Struts2?struts1与struts2都是mvc框架的经典实现模式。Struts2不是从Struts1升级而来,而是由WebWork改名而来,而WebWork只是Xwork加了很多WEB拦截器而已区别:1.核心控制器改成了过滤器(过滤器
java 包
在生活中,我们保存文档时会经常使用文件夹,把不同类型的文档归类,然后分放到不同的文 件夹中,易于管理和查找。 包主要有以下三个方面的作用。 1.包允许将类组合成较小的单元(类似文件夹),易于找到和使用相应的类文件。 2.防止命名冲突:Java 中只有在不同包中的类才能重名。世界上有千千万万的程序员,命 名冲突的类几乎是难免的。有了包,类名就好管理多了。A 定义了一个类 Sort,封装
牛人面试经历(一)
牛人面试经历(一) 应届生上泡了两年,一直都是下资料,下笔试题,面试题。一直都在感谢那些默默付出的人。写这个帖子花了我两个夜晚的时间,不是为了炫耀,只是为了能给那些“迷惘”的学弟学妹,一点点建议而已。大家何必那么认真,更没必要说脏话。我不在乎你们怎么评价我。只要有人觉得帖子有用,我就欣慰了。谢谢大家,别说脏话,以和为贵。饮水思源,谢谢应届生上默默付出的师兄师姐,谢谢那么多份笔试题,面试题
用伪代码写出生产者消费者
#include #include #include #include #include #include #include #include #define ERR_EXIT(m) \ do \ { \ perror(m); \ exit(EXIT_FAILURE); \
跨域请求方式一:jsonp跨域请求的实现原理
jsonp跨域方法实现原理