免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
楼主: glq2000

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

论坛徽章:
0
发表于 2010-07-26 21:44 |显示全部楼层
想想

论坛徽章:
0
发表于 2010-07-30 17:37 |显示全部楼层
回复 63# bruceteen


    你好,我也应该收回一下……其实当时我只是大致的在集合的cardinality上考虑了一下,觉得两个集合应该相同才有可能,如果是实数范围内,那么[0,5]和[0,7]是相同的,但是{0,1,2,3,4,5}和{0,1,2,3,4,5,6,7}肯定是不同的,所以应该不存在一个满单射(1-1 & onto),那么,如果原像集是等概率随机的,则象集无法做到等概率随机
从映射关系上,5元集合A到7元集合B的映射,根据鸽笼原理,必然存在至少1个原象映射到至少2个象上……这句话说的比较13,简单点就是说,A里至少有一个数要和B里的两个数对应起来,那么如果A是等概率随机,A中的a1对应到B中的b1和b2,其他都是1对1,那么b1和b2的概率必然比其他几个bi要低
大致是这么个思路,但是严谨的证明……我还得再想想

论坛徽章:
0
发表于 2010-07-30 17:38 |显示全部楼层
回复 72# davelv


    您和我出的是一个错,人家要整数

论坛徽章:
0
发表于 2010-07-30 17:42 |显示全部楼层
回复 67# bigCiCi


    哦,您这个说法有理,但是所谓的舍弃,如果中间有值落下去怎么办

论坛徽章:
0
发表于 2010-07-30 19:02 |显示全部楼层
回复  davelv


    您和我出的是一个错,人家要整数
gcd0318 发表于 2010-07-30 17:38

那么只需在最后结果上int取整即可。

论坛徽章:
0
发表于 2010-08-01 12:48 |显示全部楼层
回复 77# davelv


    直接取整的话,应该不是等概率的,您再想想看对不对?

论坛徽章:
0
发表于 2010-08-01 17:53 |显示全部楼层
本帖最后由 davelv 于 2010-08-01 18:00 编辑

回复 78# gcd0318

不会的,我的[N,M)是半开半闭区间。
一个强制取整就是把 小数的[0,1),[1,2),...,[M-1,M)这M个分区间之顺序集合 变成了 自然数顺序集(0,1,2,...,M-1),也就是[0,M)整数区间。由于[0,M)是均匀的的,所以每个分区间是均匀的,所以取整后的区间也是是均匀的。

论坛徽章:
0
发表于 2010-08-01 23:48 |显示全部楼层
本帖最后由 gcd0318 于 2010-08-01 23:50 编辑

回复 79# davelv


    我明白你的意思,但是区别在于,原题中的f如果只能等概率的在5个整数之间取随机数,那么最后映射到子区间,也只能落在5个区间内,所以要把[1,7)分成5个子区间,必然有至少一个子区间内的整数多于1个,或者把5个点变成7个区间,那么也就必然至少有一个区间里没有整点
当然了,如果改造f,那确实可以达到目的

论坛徽章:
0
发表于 2010-08-02 09:17 |显示全部楼层
回复  davelv


    我明白你的意思,但是区别在于,原题中的f如果只能等概率的在5个整数之间取随机数, ...
gcd0318 发表于 2010-08-01 23:48

回复  davelv


    我明白你的意思,但是区别在于,原题中的f如果只能等概率的在5个整数之间取随机数, ...
gcd0318 发表于 2010-08-01 23:48

原来它1-5区间也是整型阿,这样子的确会有问题呢。看来我犯错误了,认真看看前人回帖吧!谢谢指点

论坛徽章:
0
发表于 2010-08-02 12:42 |显示全部楼层
原来它1-5区间也是整型阿,这样子的确会有问题呢。看来我犯错误了,认真看看前人回帖吧!谢谢指点
davelv 发表于 2010-08-02 09:17



    应该是,所以我觉得您和我犯的是一个错,我现在开始倾向于无解了
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

DTCC2020中国数据库技术大会

【架构革新 高效可控】2020年12月21日-23日第十一届中国数据库技术大会将在北京隆重召开。

大会设置2大主会场,20+技术专场,将邀请超百位行业专家,重点围绕数据架构、AI与大数据、传统企业数据库实践和国产开源数据库等内容展开分享和探讨,为广大数据领域从业人士提供一场年度盛会和交流平台。

http://dtcc.it168.com


大会官网>>
  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP