忘记密码   免费注册 查看新帖 | 论坛精华区

ChinaUnix.net

  平台 论坛 博客 认证专区 大话IT HPC论坛 徽章 文库 沙龙 自测 下载 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
最近访问板块 发新帖
查看: 101013 | 回复: 126

[算法] 已知一个函数f可以得到1-5间的随机数,问怎么得到1-7的随机数 [复制链接]

论坛徽章:
1
数据库技术版块每日发帖之星
日期:2016-05-27 06:20:00
发表于 2010-07-06 18:36 |显示全部楼层
本帖最后由 glq2000 于 2010-07-06 20:18 编辑

http://blog.csdn.net/DKarthas/archive/2007/11/05/1868212.aspx看到一个面试题,博主只是提出了问题,没有给出解答,所以在这发一下,希望知道解的tx解答下  :)

问题:

已知一个函数f可以等概率的得到1-5间的随机数,问怎么等概率的得到1-7的随机数,

这个问题是有解的么? 若无解,说明原因,若有解,那解是什么?

(该问题已解决,剧透一下,正解在17楼~~~~~~~~)

论坛徽章:
18
处女座
日期:2016-04-18 14:00:45牛市纪念徽章
日期:2015-07-07 14:25:2615-16赛季CBA联赛之北京
日期:2016-06-03 17:11:5815-16赛季CBA联赛之天津
日期:2016-12-12 10:44:2315-16赛季CBA联赛之佛山
日期:2017-02-20 18:21:1315-16赛季CBA联赛之江苏
日期:2017-08-04 17:00:4715-16赛季CBA联赛之上海
日期:2017-08-22 18:18:55
发表于 2010-07-06 18:41 |显示全部楼层
本帖最后由 evaspring 于 2011-02-19 23:49 编辑

占着沙发这样好的位置当然要作点贡献,公布下比较接近标准的答案:

算法思路是:
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
  1. int rand7()
  2. {
  3. int a;
  4. while( (a=rand5()*5+rand5()) > 26 );
  5. return (a-3)/3;
  6. }
复制代码
或者
  1. int rand7()
  2. {
  3.         int sum = 0;
  4.         for(int i=0; i<7; i++)
  5.         {
  6.                   sum += ( rand5() - 1 ) * pow(5,i) ;
  7.         }
  8.         return (sum%7+1);
  9. }
复制代码

论坛徽章:
0
发表于 2010-07-06 18:53 |显示全部楼层
本帖最后由 iamxmz 于 2010-07-06 19:18 编辑

运行7次f()加起来除5

写完之后想了一下,7只会出现一次,前边的数都会出现很多次,这个不对.

论坛徽章:
1
数据库技术版块每日发帖之星
日期:2016-05-27 06:20:00
发表于 2010-07-06 18:55 |显示全部楼层
回复 2# evaspring


    f()+f()%2 的取值范围是 1到6啊
   
后来我改为    f()+f()%3, 这样取值范围倒是1到7了,但取七的概率是

前面需要为5, 后面需要为2或者5, 所以 1/5 * 2/5 = 2/25, 也不是1/7, 满足不了等概率的条件。。。。。。。。。

论坛徽章:
1
射手座
日期:2013-08-21 13:11:46
发表于 2010-07-06 18:55 |显示全部楼层
f() + f() % 2
evaspring 发表于 2010-07-06 18:41


这个好像不是平均分布的把

论坛徽章:
1
数据库技术版块每日发帖之星
日期:2016-05-27 06:20:00
发表于 2010-07-06 19:01 |显示全部楼层
回复 2# evaspring


    f()随机返回1-5, 那f()运行7次相加的话,再除以7的话,最大也就是 5*7/7 = 5, 根本取不到6和7啊。
   如果你的意思是对7取余,即使先不考虑等概率,取余的结果中包含0,而要求是对1-7返回等概率,不包括0。

   我感觉这个题是个数学题。。。。。。

论坛徽章:
1
数据库技术版块每日发帖之星
日期:2016-05-27 06:20:00
发表于 2010-07-06 19:03 |显示全部楼层
对,有两点要特别注意,  一是等概率等返回1-7中的某个数,而是f()的取值是1-5,他可以等概率的返回一到五,现在要等概率的返回1-7,不包括0

这个题目是有解的么? 解是什么? 无解的话,原因是?

论坛徽章:
0
发表于 2010-07-06 19:10 |显示全部楼层
回复 6# glq2000


仔细看,人家是除以5

论坛徽章:
0
发表于 2010-07-06 19:12 |显示全部楼层
我改了,写错了,先写的除7.不过除5也不对,这样7只会出现1次.

论坛徽章:
1
射手座
日期:2013-08-21 13:11:46
发表于 2010-07-06 19:12 |显示全部楼层
3楼是正解
您需要登录后才可以回帖 登录 | 注册

本版积分规则

SACC2017购票8.8折优惠进行时

2017中国系统架构师大会(SACC2017)将于10月19-21日在北京新云南皇冠假日酒店震撼来袭。今年,大会以“云智未来”为主题,云集国内外顶级专家,围绕云计算、人工智能、大数据、移动互联网、产业应用等热点领域展开技术探讨与交流。本届大会共设置2大主会场,18个技术专场;邀请来自互联网、金融、制造业、电商等多个领域,100余位技术专家及行业领袖来分享他们的经验;并将吸引4000+人次的系统运维、架构师及IT决策人士参会,为他们提供最具价值的交流平台。
----------------------------------------
优惠时间:2017年8月2日前

活动链接>>
  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号 北京市公安局海淀分局网监中心备案编号:11010802020122
广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员  联系我们:
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP