随机数生成算法的研究
随机数生成算法的研究在数据结构、算法分析与设计、科学模拟等方面都需要用到随机数由于在数学上，整数是离散型的，实数是连续型的，而在某一具体的工程技术应用中，可能还有数据值的范围性和是否可重复性的要求因此，我们就整数随机数和实数随机数，以及它们的数据值的范围性和是否可重复性，分别对其算法加以分析和设计以下以Visual Basic 语言为工具，对整数随机数生成问题加以阐述，而对于实数随机数生成问题，只要稍加修改就可转化为整数随机数生成问题根据整数随机数范围性和是否可重复性，可分为：1 某范围内可重复2 某范围内不可重复3 枚举可重复4 枚举不可重复所谓范围，是指在两个数n1和n2之间例如，在100和200之间这个范围，那么，只要产生的整数随机数n满足100≤n≤200，都符合要求所谓枚举，是指有限的、已知的、若干个不连续的整数例如，34、20、123、5、800这5个整数就是一种枚举数，也就是单独可以一个个确定下来某范围内可重复在Visual Basic 语言中，有一个随机数函数Rnd语法：Rnd[(number)]参数number 可选，number 的值决定了 Rnd 生成随机数的方式。
Rnd 函数返回小于 1 但大于或等于 0 的值如果 number 为Rnd 生成小于零每次都相同的数字，并将 number 用作种子大于零序列中的下一个随机数等于零最近生成的数字未提供序列中的下一个随机数在调用 Rnd 之前，先使用无参数的 Randomize 语句初始化随机数生成器，该生成器具有一个基于系统计时器的种子若要生成某给定范围内的随机整数，可使用以下公式：Int((upperbound - lowerbound + 1) * Rnd + lowerbound)这里，upperbound 是此范围的上限，而 lowerbound 是范围的下限程序流程图：程序例程：下面是一个生成10个10~20之间随机数的例子Private Sub Command1_Click() lowerbound = 10 upperbound = 20 Randomize For i = 1 To 10 random = Int((upperbound - lowerbound + 1) * Rnd + lowerbound) Debug.Print random; Next Debug.PrintEnd Sub运行结果：12 10 20 20 17 17 18 14 12 20某范围内不可重复要产生一定范围内不可重复的随机数，按通常的设计是把曾经生成的随机数保存起来作为历史数据。
产生一个新的随机数后在历史数据搜索，若找到就重新产生一个新的再重复数据搜索；否则就认为已经找到了一个新的不同随机数例如，要由计算机随机产生10个101～200之间互不相同的数程序： Private Sub Command2_Click() Dim random(10) As Integer lowerbound = 101 upperbound = 200 Randomize For i = 1 To 10 Do r = Int((upperbound - lowerbound + 1) * Rnd + lowerbound) yes = 0 For j = 1 To i - 1 If r = random(j) Then yes = 1: Exit For Next Loop While yes = 1 random(i) = r Debug.Print r; Next Debug.PrintEnd Sub运行结果：199 174 147 126 120 190 192 146 122 111粗看起来，上面的程序似乎没有什么问题，在执行过程中程序也能够通过。
但，仔细分析我们就会发现问题出在一个新产生的随机数是否已经存在的判定上既然是随机数，那么从数学的角度来说在概率上，每次产生的随机数 r就有可能相同，尽管这种可能性很小，但确是一个逻辑性与正确性的问题因此，每次产生的新的随机数r都有可能是数组random的前i-1个数中的某一个，也就是说程序在运行过程中由此可能会导致死循环，那么，能否找到一个不在数组random中的随机数r的工作就变得不确定了从算法的角度来讲，在理论上，程序失去了有穷性、有效性和确定性什么是算法？通常人们将算法定义为一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列一个算法应当具有以下特征：5 输入：一个算法必须有0个或多个输入它们是算法开始运算前给予算法的量这些输入取自于特定的对象的集合它们可以使用输入语句由外部提供，也可以使用置初值语句或赋值语句在算法内提供6 输出：一个算法应有1个或多个输出，输出的量是算法计算的结果7 确定性：算法的每一步都应确切地、无歧义地定义对于每一种情况，需要执行的动作都应严格地、清晰地规定8 有穷性：一个算法无论在什么情况下，都应在执行有穷步后结束9 有效性：算法中每一条运算都必须是足够基本的。
就是说，它们原则上都能精确地执行，甚至人们只用纸和笔做有限次运算就能完成一般来说，我们所编写的程序都是在特定算法基础上设计出来的，程序常常与算法是相互对应的，在没有特殊的情况下，程序也应当具有以上五个特征但，也有一些程序在设计中，人们由于疏忽会想当然地认为，程序只要编写出来一般都会自然地符合算法的五个特征，这是应当引为注意的那么，应该如何对其进行改进，使其符合算法的五个特征呢？仍然以上述由计算机随机产生10个101～200之间互不相同的数为例进行阐述首先，把要产生的所有数放到一个数组a中令upperbound 是此范围的上限，而 lowerbound 是范围的下限第二，每次随机生成数组a的一个下标subscript，然后取出它所对应的数据，将数组a的最后一个数放到下标subscript的位置，同时将数组a长度减1尽管前若干次生成的下标subscript随机数有可能相同，但，因为每一次都把最后一个数填到取出的位置，因此，相同下标subscript对应的数却绝不会相同，每一次取出的数都不会一样，这样，就保证了算法的确定性、有效性、有穷性程序流程图：程序：Private Sub Command3_Click() Dim a(10), b(100) As Integer lowerbound = 101 upperbound = 200 For i = 1 To upperbound - lowerbound + 1 b(i) = lowerbound + i - 1 Next Randomize length = upperbound - lowerbound + 1 For i = 1 To 10 subscript = Int(length * Rnd + 1) r = b(subscript) b(script) = b(length) length = length - i a(i) = r Debug.Print a(i); Next Debug.PrintEnd Sub运行结果：195 153 148 183 149 101 137 172 126 110枚举可重复这种随机数的生成比较简单，只要把各个枚举数放入一个数组中保存起来，然后随机生成数组的下标，最后取出对应下标下的数组的值即可。
流程图和程序可参考前面的论述枚举不可重复首先把各个枚举数放入一个数组中保存起来，其它的处理方法完全类似于某范围内不可重复随机数的方法结束语上述算法具有很高的应用价值与理论价值在计算机数据结构、算法分析与设计、科学模拟等方面需要随机数的应用中，都可使用该算法参考文献：［1］ 《Visual Basic程序设计教程》北京：机械工业出版社，2002.2.1［2］ 严蔚敏《数据结构》(第二版)北京：清华大学出版社，1999 关于一定范围内不重复随机数的讨论：1）问题：在1~1000产生N个随机数(N为用户指定, N大于0,不大于1000)，产生出来的数，不能重复，如N＝3时，结果可以是1，202，454；但不能为34，43，43 我现在的实现是,如果N＝1000时，顺序产生全部的1～1000 如果N <1000，则随机产生数，同时进行重复数过滤 现在问题是当900 3）讨论：给你写了个，速度还可以，一秒钟不到，就出来了 #include 最后扫描整个数组a,把值为1的元素位置输出即可4）讨论：用洗牌算法 定义一个数组，里面是顺序排好的自然数 把随机一个数组元素和第一个元素交换 把随机一个数组元素和第二个元素交换 把随机一个数组元素和第三个元素交换 …… 把随机一个数组元素和第N个元素交换 这里N为需要生成的不重复随机数个数5）讨论：随机洗牌算法 代码： /* Ëæ»Ï´ÅÆË㠳̻¾³: VC6.0 */ #include 我的代码中Random_Shuffle()中的第二个for循环，只需要执行n次 应该改为： for( i=0; i 真随机数生产效率没有伪随机数高，还有就是"信息熵的信息量如果很有限的话，就不是一定是真的随机数了"还有人质疑真正的随机数的存在，这是哲学问题，不在此涉及查了下现有的真随机数生成器，比如PuTTYgen的随机数是让用户移动鼠标达到一定的长度，之后把鼠标的运动轨迹转化为种子；Intel通过电阻和振荡器来生成热噪声作为信息熵资源；Unix/Linux的dev/random和/dev/urandom采用硬件噪音生成随机数；（待补充）基于特定Intel芯片组中random number generator(RNG)单元的真随机数生成器.在Intel 815E芯片组的个人电脑上安装Intel Security Driver(ISD)后,可以通过编程读取寄存器获取RNG中的随机数.有人在BBS上提到：RSA的书上介绍过一种随机数发生器,根据的是劣质内存芯片工作在高温下，其数据是不可预测的，读取这里面的数据，就会得到难以预测的随机数有采用这种技术制作随机数发生器板卡关于Linux系统的真随机数生成器在《Linux内核设计与实现》一书的附录B中有详细介绍 Linux自1.3.30版就在内核提供了真随机数生成器，至少是理论上能产生真随机数，它利用机器的噪音生成随机数，噪音源包括各种硬件运行时速，用户和计算机交互时速。 比如击键的间隔时间、鼠标移动速度、特定中断的时间间隔和块IO请求的响应时间等此外还有提供真随机数的网站，如： 1 http://random.irb.hr/ 是一个免费为学术和科研机构提供真随机数字服务的网站全名是Quantum Random Bit Generator Service (QRBGS)，由克罗地亚的计算机科学家开发其随机性依赖于半导体光子发散量子物理过程中内在的随机性，光子通过光电效应进行检测这些随机检测到的光子都是相互独立的 可以通过C/C++库、Web Service、Mathmatic/Matlab插件等多种方式访问将来会提供基于SSL的安全访问 它甚至还有个小小的Erlang的客户端访问程序 2. 还有http://random.org/，从1998年开始就在Internet上提供真随机数服务了，它用大气噪音生成真随机数有人还提到 用Java可以使用java.security.SecureRandom 产生真随机数（待查）； Linux系统有/dev/random,/dev/urandom向用户提供真随机数； Windows系统有CryptGenRandom 函數生成真随机数（待查）。
