免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 142562 | 回复: 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楼~~~~~~~~)

论坛徽章:
26
处女座
日期:2016-04-18 14:00:4515-16赛季CBA联赛之深圳
日期:2020-06-02 10:10:5015-16赛季CBA联赛之广夏
日期:2019-07-23 16:59:452016科比退役纪念章
日期:2019-06-26 16:59:1315-16赛季CBA联赛之天津
日期:2019-05-28 14:25:1915-16赛季CBA联赛之青岛
日期:2019-05-16 10:14:082016科比退役纪念章
日期:2019-01-11 14:44:062016科比退役纪念章
日期:2018-07-18 16:17:4015-16赛季CBA联赛之上海
日期:2017-08-22 18:18:5515-16赛季CBA联赛之江苏
日期:2017-08-04 17:00:4715-16赛季CBA联赛之佛山
日期:2017-02-20 18:21:1315-16赛季CBA联赛之天津
日期:2016-12-12 10:44:23
发表于 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楼是正解
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP