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币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!