随机数生成算法的研究

随机数生成算法的研究随机数生成算法的研究 日期 2006 05 23 来源 作者 字体 大 中 小 张敬新 摘摘 要 要 本文通过流程图和实际例程 较详细地阐述了随机数生成的算法和具体的程序设 计 分析了其符合算法特征的特性 关键词 关键词 随机数 算法 算法特征 程序设计 1 引言引言 在数据结构 算法分析与设计 科学模拟等方面都需要用到随机数 由于在数学上 整数 是离散型的 实数是连续型的 而在某一具体的工程技术应用中 可能还有数据值的范围 性和是否可重复性的要求 因此 我们就整数随机数和实数随机数 以及它们的数据值的 范围性和是否可重复性 分别对其算法加以分析和设计 以下以 Visual Basic 语言为工具 对整数随机数生成问题加以阐述 而对于实数随机数生成问题 只要稍加修改就可转化 为整数随机数生成问题 根据整数随机数范围性和是否可重复性 可分为 1 某范围内可重复 2 某范围内不可重复 3 枚举可重复 4 枚举不可重复 所谓范围 是指在两个数 n1 和 n2 之间 例如 在 100 和 200 之间这个范围 那么 只 要产生的整数随机数 n 满足 100 n 200 都符合要求 所谓枚举 是指有限的 已知的 若干个不连续的整数 例如 34 20 123 5 800 这 5 个整数就是一种枚举数 也就是 单独可以一个个确定下来 2 某范围内可重复 在 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 Print End Sub 运行结果 12 10 20 20 17 17 18 14 12 20 3 某范围内不可重复 要产生一定范围内不可重复的随机数 按通常的设计是把曾经生成的随机数保存起来作为 历史数据 产生一个新的随机数后在历史数据搜索 若找到就重新产生一个新的再重复数 据搜索 否则就认为已经找到了一个新的不同随机数 例如 要由计算机随机产生 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 Print End Sub 运行结果 199 174 147 126 120 190 192 146 122 111 粗看起来 上面的程序似乎没有什么问题 在执行过程中程序也能够通过 但 仔细分析 我们就会发现问题出在一个新产生的随机数是否已经存在的判定上 既然是随机数 那么 从数学的角度来说在概率上 每次产生的随机数 r 就有可能相同 尽管这种可能性很小 但确是一个逻辑性与正确性的问题 因此 每次产生的新的随机数 r 都有可能是数组 rand om 的前 i 1 个数中的某一个 也就是说程序在运行过程中由此可能会导致死循环 那么 能否找到一个不在数组 random 中的随机数 r 的工作就变得不确定了 从算法的角度来讲 在理论上 程序失去了有穷性 有效性和确定性 什么是算法 通常人们将算法定义为一个有穷的指令集 这些指令为解决某一特定任务规 定了一个运算序列 一个算法应当具有以下特征 1 输入 一个算法必须有 0 个或多个输入 它们是算法开始运算前给予算法的量 这些输 入取自于特定的对象的集合 它们可以使用输入语句由外部提供 也可以使用置初值语句 或赋值语句在算法内提供 2 输出 一个算法应有 1 个或多个输出 输出的量是算法计算的结果 3 确定性 算法的每一步都应确切地 无歧义地定义 对于每一种情况 需要执行的动作 都应严格地 清晰地规定 4 有穷性 一个算法无论在什么情况下 都应在执行有穷步后结束 5 有效性 算法中每一条运算都必须是足够基本的 就是说 它们原则上都能精确地执行 甚至人们只用纸和笔做有限次运算就能完成 一般来说 我们所编写的程序都是在特定算法基础上设计出来的 程序常常与算法是相互 对应的 在没有特殊的情况下 程序也应当具有以上五个特征 但 也有一些程序在设计 中 人们由于疏忽会想当然地认为 程序只要编写出来一般都会自然地符合算法的五个特 征 这是应当引为注意的 那么 应该如何对其进行改进 使其符合算法的五个特征呢 仍然以上述由计算机随机产生 10 个 101 200 之间互不相同的数为例进行阐述 首先 把要产生的所有数放到一个数组 a 中 令 upperbound 是此范围的上限 而 lower bound 是范围的下限 第二 每次随机生成数组 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 Print End Sub 运行结果 195 153 148 183 149 101 137 172 126 110 4 枚举可重复 这种随机数的生成比较简单 只要把各个枚举数放入一个数组中保存起来 然后随机生成 数组的下标 最后取出对应下标下的数组的值即可 流程图和程序可参考前面的论述 5 枚举不可重复 首先把各个枚举数放入一个数组中保存起来 其它的处理方法