随机数生成算法的研究
[日期：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 的值。

在调用Rnd 之前，先使用无参数的Randomize 语句初始化随机数生成器，该生成器具有一个基于系统计时器的种子。

若要生成某给定范围内的随机整数，可使用以下公式：
Int((upperbound - lowerbound + 1) * Rnd + lowerbound)
这里，upperbound 是此范围的上限，而lowerbound 是范围的下限。

程序流程图：
程序例程：下面是一个生成10个10~20之间随机数的例子。

运行结果：12 10 20 20 17 17 18 14 12 20
3 某范围内不可重复
要产生一定范围内不可重复的随机数，按通常的设计是把曾经生成的随机数保存起来作为历史数据。

产生一个新的随机数后在历史数据搜索，若找到就重新产生一个新的再重复数据搜索；否则就认为已经找到了一个新的不同随机数。

例如，要由计算机随机产生10个101～200之间互不相同的数。

程序流程图：
程序：
运行结果：199 174 147 126 120 190 192 146 122 111
粗看起来，上面的程序似乎没有什么问题，在执行过程中程序也能够通过。

但，仔细分析我们就会发现问题出在一个新产生的随机数是否已经存在的判定上。

既然是随机数，那么从数学的角度来说在概率上，每次产生的随机数r就有可能相同，尽管这种可能性很小，但确是一个逻辑性与正确性的问题。

因此，每次产生的新的随机数r都有可能是数组random的前i-1个数中的某一个，也就是说程序在运行过程中由此可能会导致死循环，那么，能否找到一个不在数组random中的随机数r的工作就变得不确定了。

从算法的角度来讲，在理论上，程序失去了有穷性、有效性和确定性。

什么是算法？通常人们将算法定义为一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列。

一个算法应当具有以下特征：。