Chinaunix首页 | 论坛 | 博客
  • 博客访问: 828249
  • 博文数量: 330
  • 博客积分: 9641
  • 博客等级: 中将
  • 技术积分: 3181
  • 用 户 组: 普通用户
  • 注册时间: 2007-01-19 14:41
文章分类

全部博文(330)

文章存档

2012年(17)

2011年(135)

2010年(85)

2009年(57)

2008年(36)

我的朋友

分类:

2012-01-15 01:09:29

文章来源:http://hi.baidu.com/lujunqianglw/blog/item/270401ade85f891e4a36d6dc.html
转载自
最终编辑
我们经常看到排序的算法,但有的时候,也需要将某个有序的序列打乱顺序,就叫“乱序”吧。
按排序的定义,“乱序”应该是这样的:将一组记录(或者元素,本身可以是有序或者无序的)按照某
个域的值(称之为“排序码”)的随机次序重新排列的过程。
这里我们注意到无论是排序还是乱序,都是按某个域的值进行的。比如我们将一组数据存放在
某个数组中,需要进行乱序,则只需要将数据下标(1-N)进行乱序后,再依次输出数组的内容,就可以
达到乱序的目的了。
一提到随机,当然免不了需要用到随机函数,这里并不打算讨论随机的深入算法,只说明随机
函数在乱序算法中的使用。随机函数一般都不是真正的随机,而是通过算法在某个范围内按某个分布函
数生成的随机数。在VB中,Rnd()函数可以生成0-1之间的随机小数,然后再通过运算得到想要的分布范
围;在C++中,使用rand()函数可以生成0-RAND_MAX(0x7ffff)之间的整数,也同样需要经过运算。当然
为了每次生成的随机数不同,在VB中使用Rnd()函数之前,要先用Randonize time 语句,使用当前时间作
随机种子;而在C++中,则可以用 srand((unsigned)time(NULL)); 来设置随机种子。要说明的是,随机种
子语句一般只用一次,多次使用反而会使随机函数"不随机"了。这里仅以C++为例,来写一个自定义的函数,
这个函数的作用是,输入整数a和b,随机生成[a,b]之间的整数(Echo注:这个[a,b]是指区间,即生成的数
是包含a和b的)。

//生成a,b 之间的随机整数
int Random (int a, int b)
{
int area=0;
int ret=0;
//生成区间
area=b-a+1;
ret=(int)(rand()*area/(1.0 * RAND_MAX)+a);
return ret;
}

说完了随机函数,我们再来看看如何乱序。假设我们先把需要乱序的数保存在一个数组A中,另外
建一个与A数组一样大小的数组B,来存放乱序后的结果。
算法一:这是经常看到的算法
(1)从A中随机抽取一个数;
(2)查一下B中是否已经有这个数
(3)如果B中没有,则把这个数放到B中;如果有表示重复了,再回到(2)
(4)直到B中的数组满了,结束;

这里存在两个问题:
1、在步骤(2)中去检查已经随机抽出来的数是不是有被抽过,这本身就存在问题,因为有可能在A中某个数
本身就是出现多次,比如这样一个序列:"1,2,4,5,2,3,4,7,22" 数字2和4都出现的2次。所以这种判断方式只能
用于不出现重复的情况;
2、设想一下随机抽取最后一个数的情况,假设一个序列“1,2,3,4,5,6,7" 随机抽取6次后得到"5,3,1,2,4,7"
就剩下最后一个数字6了,但是这时在第(1)步中是随机抽取一个数,程序会在1-7中随机选择一个数,有可能
重复了很多次后仍没有选出6这个数,但实际上,这时已经不需要再随机了,只有6才可以被抽取。
通过算法一我们可以看出乱序不能以抽取的数据内容作为标准,而应该是这样一种方式:先将需要乱序
的数放到临时数组A中,然后:
算法二:
(1)从A中随机抽取一个数K,并放入B中;
(2)从A中把K删除;
(3)回到第(1)步,直到A中为空
使用这种方式,可以不需要理会A中数据是否重复,同时,每次到步骤(2)后,A中的数据个数就少1,也不需要
进行判断。这其实也符合实际生活中我们打乱顺序的过程:随机抽一张牌,放到外面;再随机抽一张牌,放到原
刚才那张的上面,直到结束。
让我们看看C++的程序,下面的程序是给直接在数组中进行乱序,每次随机选择一个位置,把它与最后一
个位置的数据对换,直到结束。

//生成0-n不重复的随机数字
void GetRand(int n,int arr[])
{
int i;
int p;
int tmp;
for (i=0;i<=n;i++)
{
   arr[i]=i;
}

for (i=n;i>0;i--)
{
   p=Random(0,i);
   tmp=arr[p];
   arr[p]=arr[i];
   arr[i]=tmp;
}
}

在主程式调用上面函数时,需要先用 srand((unsigned)time(NULL));语句来设置随机种子。生成随机数组后,
即可使用下标的方式引用数据了。测试的主程式没有写,有兴趣的朋友可以自己完成,其实只要输出arr[]的值
就看以看到乱序后的结果了。
Echo备注:GetRand函数里没有检查arr[]的大小,有可能会出现错误,请保证arr下标为0-n,即大小为n+1。

阅读(1030) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~