67. 總結篇：面試中隨機數"等概率"vs"不等概率"生成相關問題[random generator with equal or unequal probability]

【本文鏈接】

http://www.cnblogs.com/hellogiser/p/random-generator-with-equal-or-unequal-probability.html

1. 等概率生成

(1) rand5生成rand3

現在有一個Rand5函數，可以生成等概率的[0, 5)范圍內的隨機整數，要求利用此函數寫一個Rand3函數（除此之外，不能再使用任何能產生隨機數的函數或數據源），生成等概率的[0, 3)范圍內的隨機整數。

 C++ Code  1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18   /*
    version: 1.0
    author: hellogiser
    blog: http://www.cnblogs.com/hellogiser
    date: 2014/6/3
*/
// use rand5 to generate rand3
int Rand3()
{
    int x;
    do
    {
        x = Rand5();
    }
    while (x >= 3);
    return x;
}

(2) rand3生成rand5

 C++ Code  1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17   /*
    version: 1.0
    author: hellogiser
    blog: http://www.cnblogs.com/hellogiser
    date: 2014/6/3
*/
// use rand3 to generate rand5
int Rand5()
{
    int x;
    do
    {
        x = Rand3() * 3 + Rand3();
    }
    while (x >= 5);
    return x;
}

(3) rand5生成rand7

 C++ Code  1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17   /*
    version: 1.0
    author: hellogiser
    blog: http://www.cnblogs.com/hellogiser
    date: 2014/6/3
*/
// use rand5 to generate rand7
int Rand7()
{
    int x;
    do
    {
        x = Rand5() * 5 + Rand5();
    }
    while (x >= 21);
    return x % 7;
}

(4) rand7生成rand10

 C++ Code  1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17   /*
    version: 1.0
    author: hellogiser
    blog: http://www.cnblogs.com/hellogiser
    date: 2014/6/3
*/
// use rand7 to generate rand10
int Rand10()
{
    int x;
    do
    {
        x = Rand7() * 7 + Rand7();
    }
    while (x >= 40);
    return x % 10;
}

(5) rand_m生成rand_n

 歸納總結：將這個問題進一步抽象，已知random_m()隨機數生成器的范圍是[0, m） 求random_n()生成[0, n）范圍的函數，m < n && n <= m *m。