聚合国内IT技术精华文章，分享IT技术精华，帮助IT从业人士成长
>> 技术文章 >> 正文
一道随机数题目的求解
浏览: 905 次
有这样一道算法题：
给定一个能够生成均匀1~5随机枚举数的函数，请设计一个能够生成均匀1~7随机枚举数的函数。
就是说，有一个生成随机数的函数rand5，可能返回1、2、3、4、5这5个枚举值，其中每个值被返回的概率都是严格的1/5，现在需要设计一个类似的随机数函数rand7，可能返回1、2、3、4、5、6、7这几个枚举值，每个值被返回的概率都是严格的1/7。
先掩卷思考，脑海中浮现的思路包括：
调用rand5的结果除以5，再乘以7，这样的结果范围为7/5~7，并非所希望的结果；
反复调用rand5函数7次，结果再除以5，这样的结果范围为也为7/5 ~ 7，并非所希望的结果。
如果题目反过来呢，已知rand7，求rand5呢？
那我可以先调用rand7，看看结果，如果结果为1~5，直接返回；如果结果为6、7，继续重试不就得了？
那再回到现实，怎么根据rand5求rand7？
如果rand5 * 2的结果，范围是2~10，用上面类似的办法只能得到2~7的值，无法得到1，不合题意。
但是依然得到了一种启发，调用一次rand5，结果的各种可能性有5种，要映射到rand7的7种结果可能性，是不现实的。但是如果扔两次，在不考虑去重的情况下，结果有5*5=25种可能，用某种方式映射并保留那最终的7种可能性，却是一个值得去尝试的思路。
想到了5*5，于是尝试建立二维数组arr[5][5]，那么数组的每一个元素都可以表示一种结果的可能性，在数组中取前7个元素，分别映射到1~7：
[1, 2, 3, 4, 5]
[6, 7, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
于是调用rand5两次，分别得到横坐标i和纵坐标j，如果arr[i][j]&0，则保留，否则重试。
这样的方法还不完美，因为25个数里面只有7个是有效的，大部分情况下都只能重试了，效率太低。
于是，在这个二维数组里面不止保留前7位，而是尽可能多地保留了所有7的完整倍数：
[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]
这样一来，大部分情况下，都会命中大于0的元素。
那就写出代码：
public class R {
private static Random random = new Random();
private static int[][] arr = new int[][]{
{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}
public static int rand5(){
random.setSeed(System.nanoTime());
return random.nextInt(5) + 1;
public static int rand7() {
int i = rand5() - 1;
int j = rand5() - 1;
if (i == 4 && j &= 1)
return rand7();
return arr[i][j];
再写个main函数测试一下：
Map&Integer, Integer& counter = new HashMap&Integer, Integer&();
for (int i = 0; i & ; i++) {
int key = rand7();
Integer val = counter.get(key);
if (null == val)
counter.put(key, val);
for (Map.Entry&Integer, Integer& entry : counter.entrySet()) {
System.out.println(entry.getKey() + &: & + entry.getValue());
重复测试一千万次，但是从结果看，分布却并不足够随机：
1: 1476605
2: 1764393
3: 1274549
4: 1219960
5: 1454842
6: 1425833
7: 1383818
重复测试了几次，都是输出2的情况居多。就这个数据量而言，我觉得这不是巧合。
为了让这个可能的差异更加明显，我把从rand5求rand7改成了从rand2求rand3：
public class R {
private static Random random = new Random();
private static int[][] arr = new int[2][2];
arr[0][0] = 1;
arr[0][1] = 2;
arr[1][0] = 3;
arr[1][1] = 0;
public static int rand2(){
random.setSeed(System.nanoTime());
return random.nextInt(2) + 1;
public static int rand3() {
int i = rand2() - 1;
int j = rand2() - 1;
if (i == 1 && j == 1)
return rand3();
return arr[i][j];
再同样测试一千万次，结果却大跌眼镜：
One: 5043264
Two: 2472499
Three: 2484237
居然有一倍的差异。
怎么回事呢？我开始怀疑Java的这个伪随机函数得出的结果（在计算机的世界里要实现绝对随机是不可能的）不足够随机，于是写了个程序调用一千万次Java的伪随机函数来看结果：
Map&Integer, Integer& counter = new HashMap&Integer, Integer&();
for (int i = 0; i & ; i++) {
random.setSeed(System.nanoTime());
int key = random.nextInt(7) + 1;
Integer val = counter.get(key);
if (null == val)
counter.put(key, val);
for (Map.Entry&Integer, Integer& entry : counter.entrySet()) {
System.out.println(entry.getKey() + &: & + entry.getValue());
从结果来看分布非常均匀：
1: 1429576
2: 1425422
3: 1427902
4: 1427424
5: 1429457
6: 1430664
7: 1429555
一下子觉得百思不得其解。
于是我重新审视自己的思路，还是觉得没有什么问题。虽然总结果最初有25个，但是前21个的结果每个得到的可能性都是一致的，最后四个丢掉并重来，继续的测试依然是能保证结果概率均等的。本质上这种方式在统计学上面叫做&Reject Sampling&。
我请教了一下数学家，他说思路是没什么问题的，有问题的话，只能是代码的问题。
其实还有一种方法，本质上也是类似的，即根据：
5 * (rand5()-1) + rand5()
上面这个式子的结果可以得到从1到25所有的结果，并且显而易见这25个结果出现时，这两个rand5()都可以被唯一确定返回值，因此他们出现的概率都是彼此相等的。于是可以根据上面的公式，在结果大于3*7=21的时候重新计算，否则则返回除以7的余数即可：
public class R {
private static Random random = new Random();
public static int rand5() {
random.setSeed(System.nanoTime());
return random.nextInt(5) + 1;
public static int rand7() {
int i = rand5();
int j = rand5();
int res = 5 * (i - 1) +
if (res & 21)
return rand7();
return res % 7 + 1;
同样跑了几次测试，每次测试一千万条数据，这次发现这个偏大的数跑到3上面去了：
1: 1383566
2: 1486463
3: 1748051
4: 1275854
5: 1219712
6: 1451438
7: 1434916
这么一来反而有点开窍的感觉了，我觉得是不是因为Java的伪随机数生成的方法，生成的数不足够随机呢？虽然看起来是随机的，但是那也只是看起来而已。当用&小随机&去生成&大随机&的时候，那些不随机的缺陷被放大了。而比较rand2生成rand3，和rand5生成rand7，明显是前者&放大&的倍数更大，因此最后得出的结果中，&随机性&显得差。
为了进一步检验这种猜想，我开始考虑能否让随机数的种子变化更大。因为目前使用的随机数种子是System.nanoTime()，这个方法看似纳秒，其实也只是：
Returns the current value of the most precise available system timer, in nanoseconds.
我想在我的实验中它远比毫秒精确，但是也只是保证了尽可能精确而已。
那好，要验证或者说部分验证这样的猜想，现在假设这样的猜想是正确的，那么可以得出这样的推论：
如果随机数种子换成System.currentTimeMillis()，也就是说，换成毫秒，那么最后的结果应该是更不随机；
如果我在每次取随机数之前休息几毫秒，使得每两次之间的时间种子差异增大，应该能够看到最终的结果随机性增加。
（注，我测试的版本下JDK对于设置的种子的处理方式是：seed = (seed ^ 0x5DEECE66DL) & ((1L && 48) -1)。）
好吧，现在来验证第一条，为了尽可能使得结果明显，使用rand2生成rand3的那个方案。把使用纳秒作为随机数种子改成使用毫秒作为随机数种子，结果居然是：
换言之，二维数组中横坐标和纵坐标居然在一千万次测试当中，得到的都是一样的结果，即绝大多数情况下求i和j的操作都在同一个毫秒量级内完成。
现在来验证第二条，在每次取随机数前，休眠3毫秒，当然，这个3毫秒肯定也是不精确的3毫秒。为了在增加休眠时间的情况下，能够在我的耐心时间范围内得到最终结果，我没法测试一千万次了，我的测试用例改成了测试一万次，结果为：
Three: 3206
果然，分布的均匀性要好了很多。
还蛮好玩的。
文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接
本页关键字您的举报已经提交成功，我们将尽快处理，谢谢！
C(2,4)*A(4,4)/2=72
12人共两个正组长，任何人被指定为正组长概率一样，都是
四人分两组，每组2人共有三种分法：
（甲乙，丙丁）；（甲丙，...
大家还关注
(window.slotbydup=window.slotbydup || []).push({
id: '2081942',
container: s,
size: '1000,60',
display: 'inlay-fix'一道六年级的数学题,不要太麻烦的做法,求解~计算:3/2+3/4+3/8+3/16+...
原式=（3/2)*(1+1/2+1/4+1/8+……）=（3/2)/(1-1/2)=3原本第二步3/2按照等比数列的公式要乘上1-（1/2)^n,但是这里n趋向于正无穷,就直接写作1了
为您推荐：
其他类似问题
扫描下载二维码一道数学题求解!~下列用科学计数法表示的数正确的是（）A.10000=10的五次方
B..9×10四次方C.×10的六次方
D.×10的二次方
下列用科学计数法表示的数正确的是（C）
为您推荐：
其他类似问题
答案为C。望采纳，谢谢。
扫描下载二维码从一道数学竞赛题看如何求解数学问题--《数学教学》1983年02期
从一道数学竞赛题看如何求解数学问题
【摘要】：正 一九八一年上海市数学竞赛决赛试卷中,有一道立体几何题:已知边长为1的正方体ABCD-A′B′C′D′,AC′是对角线,M、N分别是BB′、B′C′的中点,P是线段MN的中点,求DP与AC′的距离。〈见图一〉一般说来,求两条异面直线的距离,是立体几何中非封闭体部分的难
【作者单位】：
【关键词】：
【正文快照】：
一九八一年上海市数学竞赛(决赛试卷中,有一道立体几何题:已知边长为1的正方体ABCDesA,B,C,D,,Ao,是对角线,万、N分别是BB,、B,C,的中点,P是线段几f万的中点,求 DP与AC,的距离.见图一) 冉l, z/1丁一石少门”蔗并}门「‘}//、卞、} 卜分一}多户刀 乃e (1)离h二0. (2 (3)(图
欢迎：、、)
支持CAJ、PDF文件格式，仅支持PDF格式
【相似文献】
中国期刊全文数据库
常庚哲;[J];安徽教育;1980年02期
黑利洲;[J];大理学院学报;1980年01期
约翰·赫西
,徐锡龄;[J];比较教育研究;1980年05期
娄志渊;[J];数学通报;1980年01期
梁彬;[J];数学通报;1980年03期
杨贤其;[J];数学通报;1980年05期
,程龙;[J];数学通报;1980年07期
徐国章;[J];中国劳动;1980年03期
;[J];徐州师范大学学报(哲学社会科学版);1980年01期
;[J];人民教育;1980年10期
中国重要会议论文全文数据库
杨广才;;[A];教研撷华——青海师大附中建校45周年论文集[C];1999年
范伟伟;;[A];教研撷华——青海师大附中建校45周年论文集[C];1999年
钱若军;;[A];第四届空间结构学术交流会论文集（第二卷）[C];1988年
王世强;;[A];1993年逻辑研究专辑[C];1993年
李娜;;[A];逻辑今探——中国逻辑学会第五次代表大会暨学术讨论会论文集[C];1996年
许忠淮;汪素云;俞言祥;;[A];1991年中国地球物理学会第七届学术年会论文集[C];1991年
钱宝琮;杜石然;;[A];中国逻辑思想论文选（）[C];1980年
周兵;渠刚荣;邱佩璋;;[A];计算机在地学中的应用国际讨论会论文摘要集[C];1991年
余嘉顺;包吉山;;[A];勘探地球物理北京（89）国际讨论会论文摘要集[C];1989年
许报力;;[A];第四届空间结构学术交流会论文集[C];1988年
中国重要报纸全文数据库
林静;[N];中国妇女报;2000年
刘春香;[N];大众科技报;2000年
王卉;[N];科学时报;2000年
杨荔雯;[N];文汇报;2000年
吉林省榆树市五棵树一中
崔彪;[N];中国教育报;2001年
安徽省灵璧县教委
王居正;[N];中国教育报;2001年
;[N];科技日报;2001年
杨芳;[N];中国教育报;2002年
成尚荣;[N];中国教育资讯报;2002年
蒯红良;[N];中国教育资讯报;2002年
中国博士学位论文全文数据库
赵孝武;[D];中国科学院软件研究所;2001年
喻平;[D];南京师范大学;2002年
聂必凯;[D];华东师范大学;2004年
杨玉东;[D];华东师范大学;2004年
向晓林;[D];四川大学;2003年
崔利宏;[D];吉林大学;2003年
单而芳;[D];上海大学;2005年
唐亚勇;[D];四川大学;2005年
原保全;[D];中国工程物理研究院;2005年
朱华伟;[D];华中科技大学;2005年
中国硕士学位论文全文数据库
朱晓;[D];华中师范大学;2000年
聂必凯;[D];贵州师范大学;2001年
王岩;[D];河北工业大学;2002年
唐剑岚;[D];广西师范大学;2002年
郑巧云;[D];福建师范大学;2002年
吕宝珠;[D];首都师范大学;2002年
尚仁双;[D];重庆大学;2002年
苏洪雨;[D];华南师范大学;2003年
白春元;[D];首都师范大学;2003年
童莉;[D];重庆师范大学;2003年
&快捷付款方式
&订购知网充值卡
400-819-9993
《中国学术期刊（光盘版）》电子杂志社有限公司
同方知网数字出版技术股份有限公司
地址：北京清华大学 84-48信箱 知识超市公司
出版物经营许可证 新出发京批字第直0595号
订购热线：400-819-82499
服务热线：010--
在线咨询：
传真：010-
京公网安备75号