下载文档原格式
均匀随机数的产生算法在计算机科学领域，均匀随机数的生成是一个重要的问题，因为许多应用程序和算法都需要使用随机数。
在下面的文章中，我们将讨论一些常见的均匀随机数生成算法。
1. 线性同余算法（Linear Congruential Algorithm，LCA）：线性同余算法是最常见和简单的随机数生成算法之一、它的基本思想是通过对当前随机数进行线性变换和模运算，得到下一个随机数。
具体的公式为：Xn+1 = (a * Xn + b) mod m其中，Xn是当前随机数，Xn+1是下一个随机数，a、b和m是参数，mod是取余运算符。
这种算法主要依靠选择适当的参数来产生随机数序列。
2. 排列算法（Permuting Algorithm，PA）：排列算法是一种将给定数字进行随机排列的算法。
它的基本思想是通过交换数字的位置来生成随机排列。
具体的步骤如下：1)首先，将数字按照正常顺序排列。
2)然后，开始从第一个数字开始，随机选择一个位置，并将该数字与选定位置的数字交换。
3)重复第2步，直到所有数字都被交换过。
4)最后得到的序列即为随机排列。
3. 梅森旋转算法（Mersenne Twister Algorithm，MTA）：梅森旋转算法是一种广泛使用的随机数生成算法，它具有较长的周期和良好的统计特性。
该算法的基本思想是使用一个巨大的状态空间，并通过一系列复杂的运算来生成随机数。
梅森旋转算法是一种伪随机数生成算法，它使用有限的状态空间来产生伪随机序列。
4. 线性同余器方法（Linear Congruential Generator Method，LCG）：线性同余器方法是一种简单但有效的随机数生成算法。
它基于线性同余算法，但加入了更多的操作，以改进随机数的质量和周期。
具体的步骤如下：1)首先，选择合适的参数a、c和m。
2)赋予一个初始值X0。
3) 计算下一个随机数Xn+1 = (a * Xn + c) mod m。
4)重复第3步，即可得到一个均匀分布的随机数序列。
均匀随机数的产生算法下面将介绍几种常见的均匀随机数产生算法：1. 线性同余法算法（Linear congruential generator, LCG）：线性同余法算法是最常见的随机数产生算法之一、它的基本原理是通过以下递推公式得到随机数：Xn+1 = (a * Xn + c) mod m其中，Xn是当前的随机数，Xn+1是下一个随机数，a、c、m是常数，通常选择合适的a、c、m可以产生具有良好均匀性的随机数序列。
2. 递推式产生器（Recursive generator）：递推式产生器是一种基于数学递推公式的随机数产生算法。
其基本原理是通过递推公式不断更新随机数的值，从而产生一系列随机数。
递推式产生器的一个常见例子是Fibonacci递推式：Xn+2 = (Xn+1 + Xn) mod m其中，Xn是当前的随机数，Xn+2是下一个随机数。
3. 平方取中法（Middle-square method）：平方取中法是一种简单的随机数产生算法。
它的基本原理是通过将当前的随机数平方并取中间的几位数字作为下一个随机数。
具体步骤如下：-将当前的随机数平方，得到一个更大的数。
-取平方结果的中间几位作为下一个随机数。
-若需要较大的随机数，再次对下一个随机数进行平方取中操作。
4. 梅森旋转算法（Mersenne Twister）：梅森旋转算法是一种基于梅森素数（Mersenne prime）的随机数产生算法。
它具有周期长、随机性好等特点，广泛应用于模拟、统计等领域。
该算法基于以下递归公式生成随机数：Xn=Xn-M^(Xn-M+1，u)其中，Xn是当前的随机数，Xn-M和Xn-M+1是前面两个随机数，u是一系列位操作（如或运算、异或运算等）。
通过选择不同的Xn-M和Xn-M+1，可以生成不同的随机数序列。
混合线性同余法是一种多元随机数产生算法。
它的基本原理是将多个线性同余法的结果进行线性组合，从而产生更高质量的随机数。
第二章补充一随机数的产生方法1.均匀分布随机数的产生产生(0, 1)均匀分布随机数的方法很多,大致可归纳为三大类:1）利用专门的随机数表。
这种随机数随机性和均匀性较好，但是很难产生和存储足够大的随机数表，而仿真有时需要大量的随机数。
2）物理方法产生随机数例如放射粒子计数器，电子管或晶体管噪声发生器等。
这种随机数随机性和均匀性都很好，而且可以产生任意多个随机数。
缺点是没有可重复性，难以对程序和仿真的正确性作检查。
3）数学方法产生随机数常用的方法有：平方取中法和线性同余法。
i.平方取中法：平方取中法是四十年代由冯·诺依曼和梅特罗波利斯(V on Neuman and Metropolis)提出的。
其基本思想是任取一个N位整数作为初值，将初值平方，得到一个2N位的整数，如果初值的平方不是2N位时，高位用0补齐，取中间N 位作第一个随机数。
将第一个随机数平方取中间N位即得第二个随机数，以此类推可得到一系列随机数。
平方取中法虽然简单，但周期较短，产生的随机数的统计性质不好，若初值取得不恰当，还会发生退化现象。
所以必须注意初值的选取。
ii.线性同余法当今应用的大多数随机数发生器是采用线性同余法。
使用线性同余法必须事先提供三个参数；l，u，m．其迭代公式为：x i+1＝(λxi+μ)(mod m)其中，i＝1，2，…λ≠0 。
这里A称为乘子，μ为增量，m为模。
在式中，若给定初值x0(称为种子)，就可迭代算出均匀随机数序列x1、x2、……，将它们除以m，即可得到(0，1)区间均匀分布的随机数xi 。
当μ≠0、λ=1时称为加同余法；当μ=0且λ≠1时，称为乘同余法；当λ≠1且μ≠0时称为混合同余法。
乘同余法的迭代公式为：xi+1=λxi(mod m)例如用乘同余法产生随机数，其中λ=19，m=100，x。
＝11，按下面步骤计算：第i步x i-1λx i-1λx i-1(mod m)1 11 209 92 9 171 713 71 1349 494 49 931 315 31 589 89由于模数m的位数有限，这使得产生的随机数序列到了一定长度后，总会出现重复循环序列的现象。
备课资料赌棍“考验”数学家对概率的兴趣,是由保险事业的发展而产生的,但刺激数学家思考概率论问题的却来自赌博者的请求.传说,17世纪中叶,法国贵族公子梅累参加赌博,和赌友掷骰子,各押赌注32个金币.双方约定,梅累如果先掷出三次6点,或者赌友先掷出三次4点,就算赢了对方.赌博进行了一段时间,梅累已经两次掷出6点,赌友已经一次掷出4点.这时候梅累接到通知,要他马上陪国王接见外宾,赌博只好中断了.这就碰到一个问题：两个人应该怎样分这64个金币才算合理呢?赌友说,他要再碰上两次4点,或梅累要再碰上一次6点就算赢,所以梅累分64个金币的32,自己分64个金币的31.梅累急辩说,不是,即使下一次赌友掷出了4点,他还可以得21,即32个金币；再加上下一次还有一半希望得16个金币,所以他应该分64个金币的43,赌友只能分得64个金币的41.两人到底谁说得对呢？ 梅累为这问题苦恼好久,最后他不得不向法国数学家、物理学家帕斯卡请教,请求他帮助作出公正的裁判,这就成为有趣的“分赌注”问题.帕斯卡是17世纪有名的“神童”数学家.可是,梅累提出的“分赌注”的问题,却把他难住了.他苦苦思考了近三年,到1654年才算有了点眉目,于是写信给他的好友费马,两人讨论结果,并取得了一致的意见：梅累的分法是对的,他应得64个金币的43,赌友应得64个金币的41.这时有位荷兰的数学家惠更斯,在巴黎听到这件新闻,也参加了他们的讨论.惠更斯把讨论的结果写成一本书叫做《论赌博中的计算》（1657年）,这就是概率论的最早一部著作.除保险事业之外,各行各业都经常会碰到“某事件发生的可能性大小”的问题.因此,概率论问世后,在各方面得到了广泛的应用.可是,到了19世纪末,法国数学家贝特朗奇发现了一个非常有趣的怪论.他研究了下面一个问题：“设圆内接等边三角形的边长为a,在圆上任作一弦,问其长度超过a 的概率是多少？” 贝特朗奇算出了三种不同的答案,三种解法似乎又都有道理.人们把这种怪论称为概率怪论,或贝特朗奇怪论.贝特朗奇的解法如下：解法一：任取一弦AB,过点A 作圆的内接等边三角形（如右图）.因为三角形内角A 所对的弧占整个圆周的31.显然,只有点B 落在这段弧上时,AB 弦的长度才能超过正三角形的边长a,故所求概率是31.解法二：任取一弦AB,作垂直于AB 的直径PQ.过点P 作等边三角形,交直径于N,并取OP 的中点M （如下图）.容易证明QN=NO=OM=MP.我们知道,弦长与弦心距有关.一切与PQ 垂直的弦,如果通过MN 线段的,其弦心距均小于ON,则该弦长度就大于等边三角形边长,故所求概率是21.解法三：任取一弦AB.作圆内接等边三角形的内切圆（如右图）,这个圆是大圆的同心圆,而且它的半径是大圆的21,它的面积是大圆的41,设M 是弦AB 的中点,显然,只有中点落在小圆内时,AB 弦才能大于正三角形的边长.因此所求的概率是41.细细推敲一下,三种解法的前提条件各不相同：第一种假设了弦的端点在四周上均匀分布；第二种假设弦的中点在直径上均匀分布；第三种假设弦的中点在小圆内均匀分布.由于前提条件不同,就导致三种不同的答案.这是因为在那时候概率论的一些基本概念（如事件、概率及可能性等）还没有明确的定义,作为一个数学分支来说,它还缺乏严格的理论基础,这样,对同一问题可以有不同的看法,以致产生一些奇谈怪论.概率怪论的出现,迫使数学家们注意概率基础理论的研究.1933年,苏联数学家柯尔莫哥洛夫提出了概率论公理化结构,明确了概率的各种基本概念,使概率论成为严谨的数学分支.（设计者：邓新国）。
