免费注册 查看新帖 |

Chinaunix

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

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

论坛徽章:
0
发表于 2010-07-11 15:54 |显示全部楼层
回复 60# bruceteen


    你的意思是说必须整数?那么此题无解
我可以给出数学证明

论坛徽章:
14
巨蟹座
日期:2013-11-19 14:09:4615-16赛季CBA联赛之青岛
日期:2016-07-05 12:36:0515-16赛季CBA联赛之广东
日期:2016-06-29 11:45:542015亚冠之全北现代
日期:2015-07-22 08:09:472015年辞旧岁徽章
日期:2015-03-03 16:54:15巨蟹座
日期:2014-12-29 08:22:29射手座
日期:2014-12-05 08:20:39狮子座
日期:2014-11-05 12:33:52寅虎
日期:2014-08-13 09:01:31巳蛇
日期:2014-06-16 16:29:52技术图书徽章
日期:2014-04-15 08:44:01天蝎座
日期:2014-03-11 13:06:45
发表于 2010-07-11 16:11 |显示全部楼层
回复 62# gcd0318
你是怎么证明的?如果不介意的话,教教我吧

我原先的证明方法是:
立出所有可能的运算符,比如+ - *等,因为rand5的几率为1/5,所以+ - * 等的几率“最小粒度”为1/5^n
当然运算符还有/等等,但用/等时需要有限制,不能产生小数。这样的话就可以将/变形为*a*1/5,根号等操作亦然。
即无论给出的公式是如何的复杂,其结果都应该是1/5^n的整数倍。(n可以取任意整数)
m / 5^n = 1/7 在整数范围内无解

昨天想出了一个更直观的证明方法,直接用几率参与运算
因为几率的运算符,只有+ - * max min等有限的几个,而且都可以转化为*操作。另外100%可以转化为1/5+1/5+1/5+1/5+1/5,200%可以转化为2*1
所以1/5^n粒度的几率无论怎么参与计算,其结果都可以化简为m / 5^n
m / 5^n = 1/7 在整数范围内无解

假如可以引入极限的话,要想使得 m / 5^n = 1/7 有解,只有当n是无穷大时

论坛徽章:
14
巨蟹座
日期:2013-11-19 14:09:4615-16赛季CBA联赛之青岛
日期:2016-07-05 12:36:0515-16赛季CBA联赛之广东
日期:2016-06-29 11:45:542015亚冠之全北现代
日期:2015-07-22 08:09:472015年辞旧岁徽章
日期:2015-03-03 16:54:15巨蟹座
日期:2014-12-29 08:22:29射手座
日期:2014-12-05 08:20:39狮子座
日期:2014-11-05 12:33:52寅虎
日期:2014-08-13 09:01:31巳蛇
日期:2014-06-16 16:29:52技术图书徽章
日期:2014-04-15 08:44:01天蝎座
日期:2014-03-11 13:06:45
发表于 2010-07-11 18:02 |显示全部楼层
本帖最后由 bruceteen 于 2010-07-11 18:10 编辑

我收回上面的证明方法,不但繁杂,而且还有一个画蛇添足引出的bug

我现在的证明方式是:
任意一个含有n个自由度为5的自变量的公式,无论多么稀奇古怪,都将产生5^n个值,虽然某些值可能相同。
5^n 不可能是 7 的倍数。(前者个位数为5,后者个位数不可能是5)

论坛徽章:
0
发表于 2010-07-11 22:05 |显示全部楼层
1.5*f()-0.5

大家觉得这样对不对?
出来的是1~7之间的随机数,且为均匀分布(因为f()为均匀分布)

论坛徽章:
0
发表于 2010-07-11 22:11 |显示全部楼层
回复 2# evaspring

如果是随机整数的话算法比较麻烦,近似的可以有取整整函数:

(f()+f()+f()+f()+f()+f()+f())/5

论坛徽章:
0
发表于 2010-07-13 14:03 |显示全部楼层
本帖最后由 深蓝苹果 于 2010-07-13 14:24 编辑

回复 1# glq2000


    做一个区间映射不就行了。。。
   
    (f() - 3) * 3/2 + 3

   不过这样做离散度肯定会加大

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


    恩 在看 多谢~~~~

论坛徽章:
0
发表于 2010-07-14 14:18 |显示全部楼层


高手,学习了

论坛徽章:
0
发表于 2010-07-23 20:07 |显示全部楼层
生成随机数一到七,实际就是随机生成一个数,由三个bit组成,能从1-5随机生成0-1就可以的了,(这个可以随机生成0-7----如果为0继续生成一次,直到非零就生成1-7的随机数了)
函数随机值缩小,
func_1_7()
{
    i = func_0_7();
    while(i==0) {i= func_0_7();}
    return i;
}

func_0_7()
{
    i = 0;
    i |= func_0_1();
    i |= func_0_1()<<1;
    i |= func_0_1()<<2;
    return i;
}

func_0_1()
{
   do{
         i=func_1_5();
       }while (i==5)
    return i%2 - 1;
}

论坛徽章:
0
发表于 2010-07-23 20:42 |显示全部楼层
这种等概率随机问题在算法导论上有讲到

设一个随机函数rand()可以生成[0,MAX)的等概率随机数,求[N,M)的等概率随机数公式如下
( rand() / ((double)(MAX)) ) * (M-N) + N
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

DTCC2020中国数据库技术大会

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

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

http://dtcc.it168.com


大会官网>>
  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP