全部博文(330)
分类:
2012-01-15 01:09:29
//生成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;
}
}