算法导论5.1-1
参考博客
http://blog.csdn.net/effenberg11/article/details/5976838
http://qianggezhishen.bokee.com/viewdiary.43964492.html
博客中算法
1、把要生成的数标记为 a, a+1, a+2,..., b-a+1,…,b-1,b
2、取最小的 m,使得 2^m >= n
3、通过随机生成 0,1 的函数生成一个 m 比特整数(随机生成每一位),这样能随机生成 [a, 2^m) 内的整数。
4、随机生成一个 [a,2^m) 中的整数,如果这个数大小在 [a, b] 内,则取这个数为结果。如果这个数在 [a, b] 外,则丢弃它,重新生成一个。
看着有点绕。重写一下。。
1、通过Random(0,1)生成Random(a,b),实际上我们生成random(0,b-a)+a 就可以了,然后问题就转换为了Random(0,1)生成Random(0,n), 这里n=b-a
2、由于n可能不是2的整数幂,要找到最小的m使 2^m >n
int getM(int n)
{
m =0;
while(n>=2)
{
n=n/2;
m++;
}
if(pow(2,m)<n)
m++;
return m;
}
然后生成随机数0~2^m,可以分治法递归也可以二进制按位计算(推荐),如果随机数result落在0~n之间,则随机数生成成功,如果随机数落在n+1~2^m,则重新生成随机数。一次成功生成随即书的概率为n/2^m。令p=n/2^m所以时间复杂度o=p+p(1-p)*2+p(1-p)^2*3+....+np(1-p)^(n-1)=1/(1-p) (等比数列相关问题,高中数学加一点极限问题,不解释)
上述可能计算有误,思想应该是没问题的~~
分享到:
相关推荐
Python中的random模块...random.random()用于生成一个0到1的随机符点数: 0 <= n < 1> b,则生成的随机数n: a <= n <= b。如果 a <b, 则 b <= n <= a。 print random.uniform(10, 20) print rando
Python中的random模块用于生成随机数。 下面具体介绍random模块的功能: 1.random.random() 用于生成一个0到1的 随机浮点数:0 ...如果a > b,则生成的随机数n: b <= n <= a。如果 a <b, 则 a <= n <= b。
random是用于生成随机数的,我们可以...= n < 1 u7528于生成一个指定范围内的随机浮点数,生成的随机整数a于生成一个指定范围内的整数,a为下限,b为上限,生成的随机整数a<=n b;若a=b,则n>b,报错 •random.randran
先给大家介绍下python中random模块 ...2、random.randint(a,b):生产[a,b]之间的随机整数; numpy.random.random(1,5,5):返回一个一维数组,共计5个元素,数据区间为[1,5) numpy.random.random(1,5,(2
Python内置的random模块提供了生成随机数的方法,使用这些方法时需要导入random模块。 import random 下面介绍下Python内置的random模块的几种生成随机数的方法。...2、random.randint(a , b) 随机生成 a
之前的小 游戏中用到过random中的randint: import random num = random.randint(1,100) random.randint(a, b)可以生成一个a到b间的随机整数,包括a和b。 a、b都必须是整数,且必须b a。当等于的时候,比如: random...
char0='\u4eac\u6d25\u6caa\u6e1d\u5180\u8c6b\u4e91\u8fbd\u9ed1\u6e58\u7696\u9c81\u65b0\u82cf\u6d59\u8d63\u9102\u6842\u7518\u664b\u8499\u9655\u5409\u95fd\u8d63\u7ca4\u9752\u85cf\u5ddd\u5b81\u743c' ...
random.randint(a,b)生成一个[a,b]之间的随机整数 C. random.choice(seq)从序列中随机选择一个元素 D. random.uniform(a,b)生成一个[a,b]之间的随机字符 试题编号:20220221-ssn-002 试题类型:单选题 ...
Math.random()函数返回0和1之间的伪随机数,可能为0,但总是小于1,[0,1) 生成n-m,包含n但不包含m的整数: 第一步算出 m-n的值,假设等于w 第二步Math.random()*w 第三步Math.random()*w+n 第四步parseInt(Math....
生成一个0~1之间的随机浮点数,范围 0 <= n < 1.0 random.random() uniform(a,b) 返回a, b之间的随机浮点数,范围[a, b]或[a, b), 取决于四舍五入,a不一定要比b小 random.uniform(1,5) ra
用来生成一个0~1之间的随机浮点数,范围[0,10 >>> import random >>> random.random() 0.5038461831828231 random.uniform(a,b) 返回a,b之间的随机浮点数,范围[a,b]或[a,b),取决于四舍五入,a不一定要比b小。 >...
# random.random()用于生成一个 0 到 1 的随机浮点数: 0 <= n < 1.0 print(random.random()) # 0.18246795790915304 # random.randint(a, b),用于生成一个指定范围内的整数。 # 其中参数a是下限,参数b是...
本文实例讲述了Python3.5内置模块之random模块用法。分享给大家供大家参考,...print(random.randint(1,6)) #随机生成指定范围[a,b]的整数 print(random.randrange(1,3)) #随机生成指定范围[a,b)的整数 print(random.
random模块 random模块提供了一些生成随机数的函数,一些介绍为了简单...randint(a, b):返回在范围大于等于a,且小于等于b的随机整数 # coding=utf-8 #!/usr/bin/python3 import random # 0.0 <= x < 1.0随机数
random随机模块包括返回...random.randint(a, b) — 生成一个范围为 a≤N≤b 的随机数,随机数的类型是整形,注意与random.uniform(a, b)区别; random.randrange(start, stop, step) — 返回从 start 开始到 stop 结束
"\u5b8b\u4f53", "\u65b0\u5b8b\u4f53", "\u9ed1\u4f53", "\u6977\u4f53", "\u96b6\u4e66"}; int fontTypesLength = fontTypes.length; //在图片背景上增加噪点 g.setColor(getRandColor(random, 160, 200)); g...
jsp登陆验证码生成源代码 ,java import java.awt.image.*; import javax.servlet.*; ... import javax.imageio.*;... int b = fc + random.nextInt(bc - fc); return new Color(r, g, b); } 。。。。
int a= Math.round(Integer.parseInt(edit1.getText().toString().trim())); int b= Math.round(Integer.parseInt(edit2.getText().toString().trim())); // long a = Math.round(Math.random() * ...
本文首发于我的个人博客:Sui Xin’s Blog 原文:https://suixinblog.cn/2019/09/python-random.html 作者:Sui Xin Python 的 random 库实现了各种分布的伪...random.randint(a, b):返回一个 [a, b] 中的随机整数。
random.random():生成一个0-1的随机浮点数 import random print(random.random()) #0.495230693625075 random.uniform(a,b):生成一个指定范围内的随机浮点数,a,b是这个范围的上下限,不分大小,自动使得ab中小的数...