rand5()生成rand7()

最新推荐文章于 2024-10-28 22:50:59 发布

罗古洞的女婿

最新推荐文章于 2024-10-28 22:50:59 发布

阅读量3k

点赞数 4

分类专栏：笔试与面试题目

本文链接：https://blog.csdn.net/chk_plusplus/article/details/118099852

版权

笔试与面试题目专栏收录该内容

14 篇文章

订阅专栏

本文详细介绍了如何通过已有的rand5()函数等概率地生成1到7的整数，即rand7()。核心思路是利用rand5()生成1到25之间的数，然后通过取模和加1操作确保结果落在1到7的范围内。这种方法通过多次调用rand5()并进行条件判断，实现了概率均衡。同时，文中也讨论了如何优化算法，以提高效率并最大化利用生成的数字。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目描述

给定一个函数rand5()，它可以等概率生成1到5的5个整数，用这个函数来生成rand7()？

思路分析

反向思维，如果用rand7()来实现rand5()呢？

因为rand7()可以等概率生成1，2，3，4，5，6，7

所以生成1，2，3，4，5的概率都是相同的，我们只需要在函数生成6和7的时候直接返回就行了。

int rand5(){
    int ans = rand7();
    while(ans > 5){
        ans = rand7();
    }
    return ans;
}

所以我们的思路也就是，如果用rand5()来生成一个能等概率产生1，2，3......t（t >= 7）的函数。

基本公式 randa2() = a*(randa() - 1) + randa，

当a=5的时候，

randa() 产生1，2，3，4，5

则randa() - 1就等概率产生 0，1，2，3，4

那么5*(rand5() - 1)就等概率产生 0，5，10，15，20

则5*（rand5() - 1） + rand5() 就相当于我们用了两个rand5()函数

一个用于等概率生成 1 2 3 4 5

一个用于等概率生成 0 5 10 15 20

则5*（rand5() - 1） + rand5()可以等概率生成1 2 3 ...... 25

则rand7()的功能可以实现如下：

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

因为我们7以上的数字都丢弃了，其实是不太高效的，因为我们要生成rand7，

为了最大利用生成的1到25这25个数，

我们只需要让1到7中每个数字对应25个数中相同数目的数字即可，

所以 7 * x < 25，x最大为3，7*x最大为21，在21以上我们才舍弃，

21以下可以通过对7取余，

使得1到7，8 到14，15到21都这两个区间都对应到1到7

这里注意不能直接对7取余，因为7 14 21这种对7取余都是0，这是不合适的

int rand7(){
    int ans = 5*(rand5() - 1) + rand5();
    while(ans > 7){
        ans = 5*(rand5() - 1) + rand5();
    }
    return ans % 7 + 1;
}