1. 给定rand3()能随机生成整数1到3的函数,写出能随机生成整数1到7的函数rand7()；
用3*(rand3() - 1) + rand3()生成1-9的数。然后再从1-9中生成1到7.
这种思想是基于，rand()产生[0,N-1]，把rand()视为N进制的一位数产生器，那么可以使用rand()*N+rand()来产生2位的N进制数，以此类推，可以产生3位，4位，5位...的N进制数。这种按构造N进制数的方式生成的随机数，必定能保证随机。
1
int
x =
0
;
2
do
{
3
x =
3
* (rand3() -
1
) +
rand3();
4
}
while
(x >
7
);
5
return
x;
如果已经randm()能随机生成1到m的整数，写出生成整数1到n的函数randn()，也就是
用m * (randm() - 1) + randm()生成1-m^2，然后再踢掉n+1-m^2这些数。
1
int
x =
0
, max = m * m / n *
n;
2
do
{
3
x = m * (randm() -
1
) +
randm();
4
}
while
(x >
max);
5
return
1
+ (x % n);
2. 已知随机函数rand(),以p的概率产生0，以1-p的概率产生1，现在要求设计一个新的随机函数newRand(), 使其以1/n的等概率产生1~n之间的任意一个数。
先构造一个函数，使得等概率生成0和1。然后用它，以二进制的方式构造出0~n-1。然后加1就成了1~n。
1
int
rand01() {
2
while
(
true
) {
3
int
a = rand(), b =
rand();
4
if
(a ==
0
&& b ==
1
)
return
0
;
5
if
(a ==
1
&& b ==
0
)
return
1
;
6
}
7
}
8
int
randn() {
9
int
ans =
0
;
10
do
{
11
for
(
int
i =
0
; n; n >>=
1
, i++
) {
12
if
(rand01() ==
1
) {
13
ans |= (
1
<<
i);
14
}
15
}
16
}
while
(ans >=
n);
17
return
ans +
1
;
18
}
3. 帽子问题：有n位顾客，他们每个人给餐厅的服务生一顶帽子，服务生以随机的顺序归还给顾客，请问拿到自己帽子的顾客的期望数是多少？
答案：使用指示随机变量来求解这个问题会简单些。定义一个随机变量X等于能够拿到自己帽子的顾客数目，我们要计算的是E[X]。对于i=1, 2 ... n，定义Xi =I {顾客i拿到自己的帽子}，则X=X1+X2+...Xn。由于归还帽子的顺序是随机的，所以每个顾客拿到自己帽子的概率为1/n，即Pr(Xi=1)=1/n，从而E(Xi)=1/n，所以E(X)=E(X1+X2+...Xn)=E(X1)+E(X2)+...E(Xn)=n*1/n = 1。即大约有1个顾客可以拿到自己的帽子。
4. 如果在高速公路上30分钟内看到一辆车开过的几率是0.95，那么在10分钟内看到一辆车开过的几率是多少？(假设常概率条件下)
答案：假设10分钟内看到一辆车开过的概率是x，那么没有看到车开过的概率就是1-x，30分钟没有看到车开过的概率是(1-x)^3，也就是0.05。所以得到方程(1-x)^3 = 0.05 ，解方程得到x大约是0.63。
5. 生日悖论：一个房间至少要有多少人，才能使得有两个人的生日在同一天？
答案：对房间k个人中的每一对(i, j)定义指示器变量Xij = {i与j生日在同一天} ，则i与j生日相同时，Xij=1，否则Xij=0。两个人在同一天生日的概率Pr(Xij=1)=1/n。则用X表示同一天生日的两人对的数目，则E(X)=E(∑ki=1 ∑kj=i+1 Xij) = C(k,2)*1/n = k(k-1)/2n，令k(k-1)/2n >=1， 可得到k>=28，即至少要有28个人，才能期望两个人的生日在同一天。
转自：http://blog.csdn.net/hxz_qlh/article/details/1297877
6. 如果只是想要随机生成一定概率的数。比如20%生成0，20%生成1，60%生成2.
1
int
rand(
int
num[],
float
prob[],
int
n) {
2
srand(time(NULL));
3
int
random = rand() %
100
+
1
;
4
5
int
range =
0
, pre =
0
;
6
for
(
int
i =
0
; i < n; ++
i) {
7
range += static_case<
int
>(prob[i] *
100
);
8
if
(random > pre && random <=
range) {
9
return
num[i];
10
}
11
pre =
range;
12
}
13
return
-
1
;
//
error
14
}
