 多路树查找－外部查找(B树)【源代码】多路树查找－外部查找(B树)【下载及演示说明】双向链表演示程序【下载及演示说明】循环链表演示程序【下载及演示说明】链表【讲解】动态存储分配之边界标识法演示程序【下载及演示说明】动态存储分配之边界标识法【讲解】首次适应算法和最佳适应算法【讲解】动态存储分配之边界标识法【源代码】振荡排序算法【讲解】振荡排序演示程序【下载及演示说明】树和二叉树相互转化【讲解】深度优先搜索【下载及演示说明】深度优先搜索【源代码】朴素字符串匹配演示程序【下载及演示说明】当前1/4页 首页 上一页 下一页 尾页 | |
算法讲堂 |
|
本栏目所有文章由本站组织业内技术专家原创而成，用汇编语言向学习者讲解经典问题的编程思想和编程方法。 本栏目所有文章的版权归本站所有，转载请注明出处为汇编网<www.asmedu.net> 。 现本栏目的内容处于不断添加中，请随时关注。 |
|
| 算法讲堂－》线性同余产生随机数【讲解】 |
|
线形同余产生随机数
一.线形同余算法介绍： 在计算机上产生随机数，比较普遍的一种方法是用数学递推公式产生，这样产生的序列与真正的随机数序列不同，所以称为伪随机数或伪随机序列。只要方法和参数选择合适，所产生的伪随机数就能满足均匀性和独立性，与真正的随机数具有相近的性质。计算机产生的随机数一般都只是一个周期很长的数列，不是真的随机数。也就是说，随机数一般是伪随机数，每个随机数都是由随机种子开始的一个已定的数列。 当今所流行的随机数生成程序方法之一为线形同余法。这种方法通过设置 Xn+1 = （ aXn + c ） mod m ，n >= 0 式中的四个整数 m ， 模数 0 < m a ， 乘数 0 <= a<m c ， 增量 0 <=c<m X0，开始值 0<=X0<m 而得到所求的随机数序列<Xn>。这个序列称作线形同余序列。 同余序列总是进入一个循环，这是一个事实，它最终必定在N个数之间无休止的重复循环。 使用该方法产生的伪随机数能不能近似真正的随机效果，跟四个整数的设置相关： 1. 序列的开始值，一般取正整数。 2. m：一个同余序列的周期不可能多于m个元素，所以，为了达到预期的随机效果，一般我们希望这个值稍稍大一点。在大多数情况下，当m = 2e（e表示计算机的字大小）时，在计算机中得到的随机效果就比较令人满意了。而且这样对于随机数生成速度也是比较合理的。 3. a：当a=1的时候，Xn=（X0+nc）mod m ，它不具有随机序列的特性；而当a=0的时候甚至更糟糕。因此，为实用起见，选择2 <= a<m比较合理。 4. c：当c=0时，数的生成过程比c！=0的时候要稍微快些，它的限制缩短了这个序列的周期长度，但是也仍然有可能得到一个相当长的周期。当c=0时被称为乘同余法，c！=0称为混合同余法。为了一般性，我建议选择采用混合同余法。 由m，a，c和X0所定义的线形同余序列得到最大的周期长度m的条件如下： 当且仅当（1）c与m互素。 （2）对于整除m的每个素数p，b=a-1是p的倍数。 （3）如果m是4的倍数，则b也是4的倍数。 就像开始提到的，伪随机数的产生都是由一个起始种子数开始的，上面描述的就是由一个种子数下能够产生的随机数的序列。这个序列的周期性是必然的，当这个周期能够满足预期的效果的时候，就是我们看到的满意的随机效果。 在确定初始种子数的时候，可以有多种形式，例如将某时刻的时钟数据做种子，通过时间的不停变化，进行随机数的求取来达到随机效果。这些都是方法问题了，不在算法讨论范畴。 二.学习建议及计划： 根据观察和学习线形同余产生随机序列的体会，编写一个能够产生使自己满意的随机效果的汇编程序。 [07/09/21] |