产生1-5的随机函数，生成随机数1-7
2013-08-20 00:34阅读：
需求：已知函数f()生成1-5的随机数，求用f()生成1-7的随机数。
先上代码，再说思路。
#include <iostream>
#include
<cstdlib> //rand
#include
<vector> //vector<int>
#include <algorithm>
//count
#include <cmath>
//pow
using
namespace
std;
//generate 1~5
int
rand15()
{
return
1 + rand() % 5;
}
//generate 0~1
int
rand01()
{
int r
= rand15();
if
(r
== 3)
return
rand01();
if (r
< 3)
return 0;
else
return 1;
};
//algorithm 1 of generating 1~7
int
rand17_1()
{
int r
= 0;
r += rand01();
r += rand01() << 1;
r += rand01() << 2;
if (r
== 0)
return
rand17_1();
else
return r;
}
//algorithm 2 of generating 1~7
int
rand17_2()
{
int
a;
while
((a = rand15() * 5 + rand15()) > 26) ;
return
(a - 3) / 3;
}
//algorithm 3 of generating 1~7
int
rand17_3()
{
int
sum = 0;
for
(int i = 0; i < 7;
i++)
{
sum += (rand15() - 1) *
pow(5, i);
}
return
(sum % 7 + 1);
}
int main()
{
vector
< int
>ivec;
ivec.resize(100000);
cout << 'algorithm
1:' << endl;
for
(int i = 0; i <
100000; ++i)
ivec[i] =
rand17_1();
for
(int i = 1; i <=
7; ++i)
cout << i <<
' counts: ' <<
count(ivec.begin(), ivec.end(), i) << endl;
cout << 'algorithm
2:' << endl;
for
(int i = 0; i <
100000; ++i)
ivec[i] =
rand17_2();
for
(int i = 1; i <=
7; ++i)
cout << i <<
' counts: ' <<
count(ivec.begin(), ivec.end(), i) << endl;
cout << 'algorithm
3:' << endl;
for
(int i = 0; i <
100000; ++i)
ivec[i] =
rand17_2();
for
(int i = 1; i <=
7; ++i)
cout << i <<
' counts: ' <<
count(ivec.begin(), ivec.end(), i) << endl;
return
0;
}
算法1的思路
比如产生7的过程如下：
r = 1;
r = 1+2;
r = 3+4;
该算法来自：
http://blog.sina.cn/dpool/blog/s/blog_9ce5a1b50101ae1z.html?vt=4
算法二的思路
1. 通过 rand5()*5+rand5() 产生 6 7 8 9 10 11 …… 26，27 28 29 30
这25个数，每个数的出现机率相等；
2. 只需要前面 3*7 个数，所以舍弃后面的4个数；
3. 将 6 7 8 转化为 1，9 10 11 转化为 2，……，24 25 26 转化为 7。公式是 (a-3)/3；
该算法来自：
http://bbs.chinaunix.net/archiver/tid-1740087.html?page=1
另外，关于该算法的延伸思考：
这种思想是基于，rand()产生[0,N-1]，把rand()视为N进制的一位数产生器，那么可以使用rand()*N+rand()来产生2位的N进制数，以此类推，可以产生3位，4位，5位...的N进制数。这种按构造N进制数的方式生成的随机数，必定能保证随机，而相反，借助其他方式来使用rand()产生随机数(如
rand5() + rand()%3 )都是不能保证概率平均的。
此题中N为5，因此可以使用rand5()*5+rand5()来产生2位的5进制数，范围就是6到30。再去掉27-30，剩余的除3，以此作为rand7()的产生器。
该段思考来自于：
http://blog.csdn.net/xwdpepsi/article/details/8092860
算法三的思路
不明思路，看代码去吧。
来自：和算法二同一出处。
三种算法的随机效果PK
100000 / 7 = 14285.7
可见算法3的波动范围最小。
