共计 1911 个字符,预计需要花费 5 分钟才能阅读完成。
之前群里探讨过一道根底算法题,提到过不止一次了,rand5()产生 rand7(),看起来很简略,其实也有不少小心机,也算是一个很乏味且奇妙的题目了。尽管网上也有很多答案,但有的并不够循序渐进,所以写篇文章,理下思路。
原题是这样的,“Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.”
题目说的很简略,然而蕴含了一些尽管没说,然而大家都默认的一些根本束缚,即你只能使用 rand5 这个已知函数和一些简略的运算符,不能引入一些其它函数或封装非凡运算符。但如果你认为它真的简略,那可能你就要栽了。
我想,应该没有呆头呆脑的人会这样实现吧
int rand7(){return 2+rand5();
}
为什么这样不对,因为很简略,这个函数无奈生成 1,不符合条件。
那如果这样呢?
int rand7()
{
int i;
i = rand5() + rand5() + rand5() + rand5() + rand5() + rand5() + rand5();
return i%7 + 1;
}
看起来如同没问题,利用 5 跟 7 的最小公倍数,7 个 5,再模 7,每个数字概率是 1 /5,不正好就是 1 - 7 嘛。
实际上,这也是错的。
第 4 行代码中,将会产生 5^7 种可能的计算,最终这些可能映射到 [7,35] 的整数区间中,然而 [7,35] 区间内整数的产生的概率并不相等。看起来有点懵,咱们换个更简略的例子来阐明下,如果有一个 rand3 的 () 函数,3 个 rand3()能生成 [3-9] 这个区间的数字,然而 [3-9] 这个区间的数字是不平均的。
# 多个 rand 函数
123
123
123
#生成组合
3,4,5,4,5,6,5,6,7
4,5,6,5,6,7,6,7,8
5,6,7,6,7,8,7,8,9
#每个数字概率
3=1
4=3
5=6
6=7
7=6
8=3
9=1
其实,略微对数字有点敏感的人也能立马判断进去,2+4=6,4+2=6,显然两头的数字有多种组合,呈现的概率就会更高。这就引申出一个高中数学的概率问题了,“一对夫妇生了两个孩子 , 其中一个是男孩, 问另一个是女孩的概率是多少?”。这两个问题实质上是一样的。
那么正确的做法应该是怎么呢?
思路还是那个思路,rand7 的要害不仅是生成 1 - 7 之间的数字,还要保障这个数字是随机的,也就是概率均等。做到概率均等,才算正确。
如果这么写呢?
int rand7()
{int vals[5][5] = {{1,2,3,4,5},
{6,7,1,2,3},
{4,5,6,7,1},
{2,3,4,5,6},
{7,0,0,0,0}
};
int result = 0;
while(result == 0)
{int i = rand5();
int j = rand5();
result = vals[i - 1][j - 1];
}
return result;
}
当时构建一个方阵,外面平均地放着 1 - 7 这七个数,而后 rand5 只用来生成坐标,这样对否?
咱们来看是否满足以下两束缚:
1. 生成 1 - 7 这七个数。
2.1- 7 呈现的概率均等
第一个条件,无疑满足。第二个条件,1- 7 这几个数字,每个数字呈现的概率是 3 /25,尽管这个矩阵里有 0 这个纯正用来填充的数字(是 0 还是 10,都不重要),但不障碍 1 - 7 呈现的概率均等的束缚。
然而这样的写法毕竟太丑,也用了额定的空间,换种形式,其实方阵的做法,转换成更简略的代码,应该是
int rand7()
{
int i;
do{i = 5 * (rand5() - 1) + rand5(); // 产生 [1,25] 的整数区间
}while(i > 21); // 将 [1,25] 整数区间管制于[1,21]
return i%7 + 1; // 将 [1,21] 映射到[1,7]
}
实际上,这个题是算法导论里的一道题,也是互联网大公司的八股文算法题,是有通用模板的。下面的 5 和 7,能够替换成任意的 a,b,只须要满足 (a<b) 即可。
即如果给你 Randa,你能够通过以下形式轻松结构 Randb,生成 1 到 b 的随机数。
Randb = a * (Randa – 1) + Randa
如果已知 rand7, 要生成 rand5 呢?很简略,把 6 和 7 排除掉就是 rand5 了,也就是当随机到大于 5 的时候,就再随机一次,直到小于等于 5。
int rand5(){Rint result = rand7()+1;
while (result > 5){result = rand7()+1;
}
return result;
}
很简略,但也是正确的做法。其实跟下面说的 rand5 生成 rand7 的思路是一样的,先利用 rand5 把范畴放大,而后再排除掉超出的范畴,使这个范畴是 7 的倍数。