2007-08-23
跳蚤算法 - [Algorithms]
版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://conoon.blogbus.com/logs/7872464.html
一、算法的诞生及设计初衷。
传统教材中取得x个0 to n之间不重复随机数的方法一般是这样：（x个不重复随机数输出到a()数组）
for i=1 to x Do r=int(rnd*(n+1)) c=<确定r不包含在a()内> Loop Until c <将r添加到a()> Next 由于r可能与a()内的值重复，且每次循环都要历遍a()，因此该算法的效率很低。而且r是否命中到a()存在一定的随机性，取得一个合适的r要循环多次（次数不确定），从运算时间上来说是不可预见的。 不重复随机数是编写程序经常需要的算法。
因此，出于高效、稳定的需要，通过对扑克洗牌的观察，设计出如下算法。由于不清楚这个算法的学名，因其在工作时数值随机交换，好似跳蚤一样跳来跳去的，因此给它取个有趣的名字叫“跳蚤算法”，并在CSDN的VB版多次提供。 “跳蚤算法”有许多改进方式及应用方法。
以下仅是最基本的“跳蚤算法”，以便于描述这个算法的原理。
这个算法的优点在于运算时间稳定、高效，缺点是需要大量的存储空间。
需要的空间与n的取值有关。通常情况下，如果您要从s to e的范围内选择x个随机数，假如e-s的绝对值大于10000000一般我不推荐您使用这个算法。
如果这个绝对值大于2000000000，在VB下是难以做到的。
该算法原则上不适用于浮点数。
二、跳蚤算法原理
a()为一个数组，元素上下标符合a(0 to n)的理想状态。在0 to n范围内取得x个随机数，(x<=n) i为数组元素的当前索引 r为一个随机数 r。(0<=r<=n)
1、首先需要为数组赋值，打乱一个所有值都一样的数组是没有意义的。 For i=0 to n a(i)=i Next
2、打乱原有顺序排列的数组元素值。 For i=0 to n r=int(rnd*(n+1)) Swap a(i),a(r) Next Sub Swap(V1,V2) //交换两值 T=V1:V1=V2:V2=T End Sub
3、获取x个不重复随机数，输出到b()里面。 For i=1 to x b(i)=a(i-1) Next
收藏到：Del.icio.us
