收藏
回答

违规判断错误?

文章内容如下:

 最基本可以使用两次rand5(),如果得到的数字大于7继续rand5即可,但是这样调用会出现的问题是最小的数字就是2了,没有1,那么很简单加入我们将结果-1,这种是有问题的,因为1只有0和1一种组合方式,而3就有1和2以及2和1两种组合方式,因此得到的概率是不等的,因此需要用乘法来做,比如(rand5()-1)*5 + rand5(),为什么这里是*5这里是因为乘以其他的数值得到的1-25之间的数值不是等概率的。 代码如下:

int rand7(){
    int ret = 0;
    do{
        ret = (rand5()-1)*5 + rand5();
    }while(ret > 7);
    return ret;
}

 这里我们接受了1-7的数值,拒绝了8-25的值,后面8-25的值有点被拒绝掉浪费。因此我们可以这样写,利用倍数。

int rand7(){
    int ret = 0;
    do{
        ret = (rand5()-1)*5 + rand5();
    }while(ret > 21);
    return 1 + ret%7;
}

 这样写,我们就接受了1-21的值,拒绝了22-25的值,相当于拒绝了16%的值。那再优化下,利用刚才的22-25被拒绝的值(利用的方式同上):

int rand7(){
    int ret = 0;
    do{
        ret = (rand5()-1)*5 + rand5();
        // 上面生成1-25的值
        if(ret <= 21return 1+ret%7;
        // 上面得到22-25之间的值。
        ret = (ret - 21 - 1)*5 + rand5();
        if(ret <= 14return 1+ret%7;
        //上面得到的是15-20之间的值
        ret = (ret - 14 - 1)*5 + rand5();
        if(ret <= 28return 1+ret%7;
        // 上面得到的是29-30之间的值
        ret = (ret - 28 - 1)*5 + rand5();
        if(ret <= 7return 1+ret%7;
        // 上面得到的是8-10的值
        ret = (ret - 7 - 1)*5 + rand5();
        if(ret <= 14return 1+ret%7;
        // 上面得到的是15-15的值
        ret = (ret - 7 - 1)*5 + rand5();
        return ret;
    }while(true);
}

 其实,理论上来讲,按照第三种写法,给randX实现randY (X<Y),始终都能在一次循环里面都不被拒绝。因为只要找到最终:上一次的余数*X=Y的倍数,找到那个余数就可以了。无非就是多写几行,只要X和Y不是太大都行。 最终如果拒绝值为1个的时候就可以在下一次肯定可以返回了,也就是肯定在一次循环里面得到对应的rand值。

 要理解此题目的做法可以参考leetcode题解:https://leetcode-cn.com/problems/implement-rand10-using-rand7/solution/xiang-xi-si-lu-ji-you-hua-si-lu-fen-xi-zhu-xing-ji/

 leetcode上rand7生成rand10的题目是这个:https://leetcode-cn.com/problems/implement-rand10-using-rand7/


请问哪里有违规呢?




回答关注问题邀请回答
收藏
登录 后发表内容
问题标签