免费注册 查看新帖 |

Chinaunix

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

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

论坛徽章:
0
发表于 2010-07-08 19:58 |显示全部楼层
本帖最后由 jerryz920 于 2010-07-08 20:34 编辑

这个其实和算法导论上的一个题很像么:已知random等概率返回0或者1,那么试写一个函数等概率返回[a,b]之间的整数。思路就是2进制表示[0, b-a]之间的数,先计算出至少需要多少位,按位生成一个二进制数,一旦大于b-a就重新生成。放到这里的话,表示成5进制就可以了~

推广一下:对于等概率可以生成k个连续整数函数的函数randomk,设计生成[a,b]之间的整数的算法:
令n = b - a;则等概率生成[0,n]上的一个整数即可。于是用k进制表示生成的整数,设m=ceiling(logk(n)),
  1. int randN() {
  2.   while (res > n) {
  3.      for (i = 0; i < m; i++)  
  4.          gen bit i for res with randomk
  5.   }
  6.   return res;
  7. }
复制代码
期望的运行时间为t*m* i * (1 - (n+1)/k^m)^(i-1) * ((n+1)/k^m),i从1加到无穷,t表示randomk的运行时间,那么计算这个级数的值为t*m*k^m/(n+1).
带入到这个题目,期望运行时间为50*t/7,还是很快的。

论坛徽章:
1
2015年辞旧岁徽章
日期:2015-03-03 16:54:15
发表于 2010-07-09 09:34 |显示全部楼层
讨厌讨论  各种 面试题, 这些题目 在某国 好象 都是 类似 于  唐 jun  ,这些能吹会拍的 人出的,能有什么水平。  可惜呀, 好资源一半让狗占了。

论坛徽章:
0
发表于 2010-07-09 10:46 |显示全部楼层
回复 42# jerryz920


    高论

论坛徽章:
0
发表于 2010-07-09 11:10 |显示全部楼层
回复 40# churchmice


    照这种理论 我是不是可以认为 如果一个函数能随机生成[1,N] 那这个函数不用改变只要舍弃某些值也就能随机生成[1,M] (其中M < 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-09 14:45 |显示全部楼层
题目是从CU上看到的,我的算法是:
int rand7()
{
    int a;
    while( (a=rand5()*5+rand5()) > 26 );
    return (a-3)/3;
}
可惜没办法验证,不知道这个算法是否正确?(问题一)。
(验证方法是通过双循环将两个rand5()分别换成1 2 3 4 5,但剔除掉(5,2)(5,3)(5,4)(5,5)这四个组合)

算法思路是:
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

注:
我觉得不能将 while( (a=rand5()*5+rand5()) > 26 ) 其中一个rand5()移到while之外,即不能写成
int b = rand5();
int a;
while( (a=b*5+rand5()) > 26 ); 或 while( (a=rand5()*5+b) > 26 );
因为出现 >26 的情况,说明 b 有很大机率很大,从而又导致while之后的a有很大机率很大,破坏了平衡性。
这个备注中的看法对么?(问题二)

但,令人惋惜的是,这不是一个严格意义上的算法,因为“计算机算法”比“数学上的算法”多两个限定,是“有限时间有限步骤内……”,而while( (a=rand5()*5+rand5()) > 26 )可能会循环超过可忍耐次数,即某次运行这段代码可能到地球灭亡时还没结束,虽然几率很低,但有可能发生。

------------------------------------------------------------------------------------

google了一下,找到另一种方法:(本质和上面的算法相同,但要使得第二步不产生多余的数)
找到一个五进制的数 444…4,这个数正好能被7整除
于是他找到444444(五进制)这个数,也就是15624
产生nnnnnn(五进制)的方法很简单,就是每位都通过rand5-1来产生
然后将nnnnnn%7+1就得到了均匀分布于1到7的算法。

这个算法是错误的,因为 444444(五进制)内包含有15625个数,不是15624个数,前者不是7的整数倍。
用我的变形算法来描述就是:
通过 r*5^0 + r*5^1 + r*5^2 + r*5^3 + r*5^4 + r*5^5 产生 3906 到 19530 共15625个数的均匀分布,可惜15625不是7的整数倍,还是需要舍弃掉最后一位。作者错误在于马虎的认为 0至n 内有n个数,其实是n+1个数。

虽然作者的结果是错误的,但思路是正确的,只要能找到一个数n,使得 4 + 4*5 + 4*25 + 4*125 + 4*625 + 4*3125 + …… 的结果加一后是7的整数倍。
我用代码暴力求解,在数据溢出之前都没找到这个数。于是从理论上分析,444…4(五进制)+1 也就是 5的x次方,永远不可能是7的倍数。

还google到其它一些巧妙的算法,但可惜作者并没有真正理解“随机”的概念。

------------------------------------------------------------------------------------

思考一下 rand5()+rand5(),将产生 1/25个2,2/25个3,3/25个4,4/25个5,5/25个6,4/25个7,3/25个8,2/25个9,1/25个10。
如果能找到一个公式,使之产生一系列不同几率的数,将这些数分成7组,使得每组数的几率总和为1/7就可以了。
假设这个公式f需要n个rand5()为自变量,则最多产生5^n个数,不是“最多”的情况说明不同参数组合产生了相同的数,无论是不是“最多”的情况,都可以证明每个数的几率都必然是 1/(5^n) 的整数倍。
那么无论怎么分组,每组数的几率总和都应该是 m * 1/(5^n)。
求 m/(5^n) = 1/7 的整数解,即求 5^n = 7m 的整数解,很显然是无解的。(前者的个位数不是0就是5,而后者的个位数不可能是0或5)
因此自此证明这个问题是无解的

论坛徽章:
0
发表于 2010-07-09 19:11 |显示全部楼层
回复 45# goubao198562

当然可以

论坛徽章:
0
发表于 2010-07-10 09:25 |显示全部楼层
17楼:
是不是可以这样理解呢:随便从这25个二元组中选出七个,这七个每个出现的概率是1/25,将这七个数字分别对应到1-7,然后重复的执行(rand(), rand()),直到出现前面7个二元组中的一个,这时就产生了一个1-7之间的随机数,这些随机数是等概率的

论坛徽章:
0
发表于 2010-07-10 09:30 |显示全部楼层
回复 48# klyh305

是的,只要是7的倍数个就可以了,所以要舍弃掉一些值

但是从效率方面来考虑的话还是舍弃尽可能少的值

论坛徽章:
0
发表于 2010-07-10 09:54 |显示全部楼层
本帖最后由 guoruimin 于 2010-07-11 16:11 编辑

回复 17# churchmice
17楼的算法,确实是真正随机的,却不是严格的算法。
致命的漏洞是当出现的组合不符合条件时,重新生成!
从概率上来讲:重新生成符合条件的组合需要一万年,也是可能的。
所以是不可靠的算法!

有 1 - 5 之间的随机数 n1, n2, ... n7
则有 7 - 35 之间的随机数 m = n1 + n2 + ... + n7
则有 1 - 7 之间的随机数 k = m / 5

该算法始终稳定在 rand 7 次!

但该算法似乎不是真正随机的。
中间的几个数出现的概率比较高吧?

论坛徽章:
0
发表于 2010-07-10 10:40 |显示全部楼层
本帖最后由 churchmice 于 2010-07-10 10:45 编辑

回复 50# guoruimin

侬说的对,凡事讲概率,那你可以计算一下,由于是25种情况种舍弃了4种,所以舍弃的概率是4/25

那么我连续舍弃100次的概率是多少? (4/25)^100
连续舍弃1000次呢?这概率是多么的小啊, 舍弃这么多次对于现代的计算机来说只是瞬间的事情,所以不存在性能的问题
如果恰如你所说,这个算法不幸的连续舍弃了n次,导致需要运行个1万年才能出结果,你可以去算算这个时候的n值是多大,对应的概率是多小?
这世界上没有100%会发生的事情,计算机中硬盘挂掉,cpu计算出现错误都有一个概率,就连寄存器(硬件)也会有一个meantime to work,也就是能够正常工作的概率。

照你这么说密码学都不用搞了,比如密钥是128位,那我随便猜一个也有1/(2^12的概率命中
但实际中的情况时,如果一个事件发生的概率很小(究竟多小算小要根据实际应用场景确定),我们就认为它不会发生,就可以放心的去用


反观你这个算法
有 1 - 5 之间的随机数 n1, n2, ... n7
则有 1 - 35 之间的随机数 m = n1 + n2 + ... + n7
则有 1 - 7 之间的随机数 k = m % 7 + 1


要证明k是等概率的有两种情况:
1. m是等概率分布在1-35之间,这个是不可能的
   因为根本没有任何可能使得m=1
2.m在1-35之间的分布不是等概率的,但是经过m%7 + 1的操作后成为了等概率,那可以算一下
   k=1要求: m=0,7,14,21,18,35
   m=0 的概率为0
   m=35的概率为 (1/5)^7
   其余几种我没算过,但是你要这玩意加起来等于1/7,我认为很悬
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

DTCC2020中国数据库技术大会

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

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

http://dtcc.it168.com


大会官网>>
  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP