已知rand7()可以产生1~7的7个数(均匀概率),利用r_腾讯笔试题

推荐

流

int rand10()
{
    int n=49;
    while(n>40){
        n=7*(rand7()-1)+rand7();
    }
    return n%10+1;
}

编辑于 2015-02-09 17:28:59 回复(4)

nurnoch

产生指定范围内的随机数就要求指定范围内每个数的产生概率都是相等的。

由于无法直接通过rand7()产生1-10的数，所以就要思考如何组合rand7()生成1~10n之间的数。

为了讨论方便，更符合我们平时使用的习惯，我们将rand7() - 1，就表示生成的是0~6之间的随机数。

i = rand7() - 1, j = rand7() - 1

那么7 * i + j 就可以看出一个7进制的数范围为00~66（转换为十进制就是0~48），而且这些7进制数的产生概率都是一样的，每个数都是1/48，所以我们取0~39的这40个数，它们的概率也是相同的。余10加1就实现了rand10()。

int rand10() {
    int i = rand7() - 1;
    int j = rand7() - 1;
    int num = 7 * i + j;
    if(num >= 40)
         return rand10();
    else
         return num % 10 + 1;

发表于 2015-08-29 11:05:05 回复(7)

霖淼书生

public int rand10(){

int num;

do{

num = (rand7()-1)*7+rand7()-1;

}while(num>39)

return num%10+1;

}

编辑于 2015-08-30 14:54:48 回复(3)

豆瓣酱

记住这道题重点是:均匀概率
//rand7 产生的数概率是一样的,即 1~7 出现概率一样,由于我们对结果做了一定的筛选只能通过 1~5,而 1~5 出现的概率也是一样的,又由于范围为 1~5 所以 temp1 出现 1~5 的概率为 1/5 ,同理后面的出现 temp2 的概率为 1/2 //首先temp1出现在1~5的概率为1/5,而temp2出现 1~2 的概率为1/2,也就是说 5*(temp2-1) 出现 5 或 0 的概率为 1/2,所以假如你要得到 1~5 的数的话那么 5*(temp2-1) 必须 0,所以因为你要保证 5*(temp2-1)=0,这个概率只有 1/2,再加上你前面指定 1~5 的概率为 1/5 ,所以结果为 1/5*1/2=1/10
int rand10() {
int temp1;
int temp2; do
{
temp1 = rand7(); }while(temp1>5);
do {
temp2 = rand7(); }while(temp2>2);
return temp1+5*(temp2-1); }

发表于 2014-10-25 00:26:03 回复(1)

黄小斜

产生指定范围内的随机数就要求指定范围内每个数的产生概率都是相等的。

由于无法直接通过rand7()产生1-10的数，所以就要思考如何组合rand7()生成1~10n之间的数。

为了讨论方便，更符合我们平时使用的习惯，我们将rand7() - 1，就表示生成的是0~6之间的随机数。

i = rand7() - 1, j = rand7() - 1

那么7 * i + j 就可以看出一个7进制的数范围为00~66（转换为十进制就是0~48），而且这些7进制数的产生概率都是一样的，每个数都是1/48，所以我们取0~39的这40个数，它们的概率也是相同的。余10加1就实现了rand10()。

编辑于 2017-04-03 13:52:26 回复(0)

二货磁铁

这里我们利用rand7()来产生1~10的随机数：

int rand7(); 
int rand10() 
{ 
    int _t1 = rand7();//表示7^1位 
    int _t2 = rand7(); 
    int t = _t1 * 7 + _t2; 
    while (t <= 10 || t >= 1) 
    { 
        _t1 = rand7();//表示7^1位 
        _t2 = rand7(); 
        t = (_t1-1) * 7 + _t2; 
    } 
    return t; 
}

上面的代码均匀的先是产生了1~49的值，然后选取的1~10的时候才输出，使得输出值是均匀概率的，但是显然有点浪费，下面改进一下：

int rand7(); 
int rand10() 
{ 
    int _t1 = rand7();//表示7^1位 
    int _t2 = rand7(); 
    int t = _t1 * 7 + _t2; 
    while (t <= 40 || t >= 1) 
    { 
        _t1 = rand7();//表示7^1位 
        _t2 = rand7(); 
        t = (_t1-1) * 7 + _t2; 
    } 
    //产生了1~40 
    return ((t - 1) / 4 + 1); 
}

之前的解答格式不是很好看，改了一下

编辑于 2018-01-09 00:46:45 回复(0)

CloudCastle

等概率的具体做法不外乎插空，删除，取余。首先，
可以由rand7() 产生 0-48 的等概率数，每个数产生的概率都是 1/49;
然后当产生 40 - 48 这几个数时我们重新获取，
这样相当于把 40 - 48 的概率均摊到 0 - 39 上面，
所以不会影响 0 - 39 的等概率产生。然后余10加1即可，代码如下：
int rand7()
{
    int f = rand() % 7 + 1;
    cout << f << endl;
    return f;
}

int rand10()
{
    int i = ( rand7() -1 ) * 7 + rand7(）- 1; // i 是0-48的等概率数
    if ( i >= 40 )
        return rand10();
    else             // 现在 i 是 0 - 39 的等概率数
        return i % 10 + 1;
}

int main()
{
    srand(time(NULL));
    cout << rand10();
    return 0;
}

编辑于 2015-09-04 22:35:31 回复(5)

永不停息的狮子

详细讨论此问题的一篇博客：

http://blog.csdn.net/yiqiangeliyou/article/details/46823595

发表于 2015-08-17 11:55:53 回复(0)

Evac11

public static int rand10(){
    while (true){
         int num = 7 * rand7() + rand7();
         if (num < 41){
            return num % 10;
        }
    }
}

发表于 2017-08-11 10:46:37 回复(0)

牛客3902095号

进制

发表于 2017-05-24 22:56:37 回复(0)

绽放的四叶草

rand7（）-1的集合为{0,1,2,3,4,5,6}，(rand7()-1)*7的集合A为{0,7,14,21,28,35,42}，若集合B为{1,2,3,4,5,6,7}，则A和B任何2个元素可以组合成1~49之间的数，概率为1/49，(rand7()-1)*7+rand7()构造出1~49，将41~49剔除掉，可以得到rand10()之间随机数

发表于 2016-03-03 20:18:17 回复(0)

冰诺

1、r(7)产生1~7；

2、r(7)-1 产生0~6；

3、由于10>r(7)-1 的表示范围，因此需进行（r(7)-1）*7，产生0、7、14、21、28、35、42，再将0~42中间空缺的位置补齐，得到：num=（r(7)-1）*7 + r(7) - 1，就产生0~48范围内的数

4、0~48范围内的数num%10，可以得到4次0~9，而num>=40以上的部分，我们可以通过筛选去掉，从而，使得得到等概率的0~9；

5、再将得到的num+1,就可得到1~10.

C、C++程序如下：

编辑于 2015-09-06 11:19:00 回复(0)

life061522

<div> rand7()产生的随机数为{1,2,3,4,5,6,7},记为序列B； </div> <div> rand7()-1 产生的随机数{0,1,2,3,4,5,6}； </div> <div> (rand7()-1)*7产生的随机数{0,7,14,21,28,35,42};记为序列A； </div> <div> <br /> </div> <div> <br /> </div> <div> 由A+B序列可以得到1-49的随机数，并且概率为1/49， </div> <div> 为了得到1-10的随机数，可以先得出1-40的随机数(只需要在A+B序列中截断即可),计为序列X。 </div> <div> 则1-10的随机数为：X%10+1. </div> <div> <br /> </div> <div> 程序如下： </div> <div>         int rand10()<br /> </div> <div>         {<br /> </div> <div>             int x = 0;<br /> </div> <div>             do<br /> </div> <div>             { </div> <div>                 x = 7*(rand7()-1) + rand7();<br /> </div> <div>             }while(x>40)<br /> </div> <div>             return x%10+1;<br /> </div> <div>         }<br /> </div>

发表于 2015-09-05 23:41:24 回复(0)

好人Zakilo

发一个时间复杂度稳定的算法，供参考。
想法是7和10的最小公倍数是70。（欢迎指正）

int n = 0;
for(int i=0; i<10; ++i) n += rand7();
return n%10;

发表于 2015-09-05 14:49:02 回复(2)

佳佳

<div> //公式为 ((rand7()-1)*7 +&nbsp;rand7()-1) % 10 + 1，过滤掉多余项 </div> <div> <br /> </div> <div> int rand10() </div> <div> { </div> <div> &nbsp; &nbsp; int random = 0; </div> <div> &nbsp; &nbsp; do<br /> </div> <div> &nbsp; &nbsp; {<br /> </div> <div> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;random = ((rand7()-1)*7 +&nbsp;rand7()-1) % 10 + 1; </div> <div> &nbsp; &nbsp; }while(random &gt; 10);<br /> </div> <div> &nbsp; &nbsp; return random;<br /> </div> <div> } </div>

发表于 2015-09-03 00:21:23 回复(0)

寻#

为什么要剔除41到49这几个数，不剔除是否一样？哪位大神给解答一下..

发表于 2015-09-02 16:52:36 回复(2)

quinn

<div> #include <time.h> </div> <div> #include <iostream> </div> <div> #include <stdlib.h> </div> <div> using namespace std; </div> <div> int rand7() { </div> <div>     return rand()%7 + 1; </div> <div> } </div> <div> <br /> </div> <div> int rand10() { </div> <div>     int temp = 0; </div> <div>     do { </div> <div>         temp = 7*(rand7()-1) + rand7(); // 取 1~49 </div> <div>     } while (temp > 40); // 取1~40 </div> <div>     return temp%10+1; </div> <div> } </div> <div> void Count(int count[], int num) { </div> <div>     count[num-1]++; </div> <div> } </div> <div> int main() { </div> <div>     srand(time(0)); </div> <div>     int count[10]; </div> <div>     fill_n(count, 10, 0); </div> <div>     for (int i = 0; i < 100000; i++) </div> <div>         Count(count, rand10()); </div> <div>     for (int j = 0; j < 10; j++) </div> <div>         cout << j+1 << ": " << count[j] << endl; </div> <div> } </div>

发表于 2015-09-02 16:52:08 回复(0)