0%

【算法编程】随机数的不重复选择

​ 前一篇文章中,我们在Java中用实现两种不同接口的类,解决了不重复选择随机数的问题。现在我们在C++中,通过几种不同的算法来解决上述问题。在下面的四种算法实现中,用的随机函数都是C的库函数,这个函数产生的随机数的范围是限定的,[0, 32767]。当然我们可以通过四则运算来改变取值范围。具体的算法实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<iostream>
#include<ctime>
#include<algorithm>
#include <set>
using namespace std;

/****************************************\
函数功能:从n个数中随机选择m个不同的数
函数输入:n为样本空间,m为选择的个数
函数输出:在屏幕上打印选取的数
算法描述:结果范围在[0,n),呈递增数列,
当n比较大m比较小时,耗时较大
\****************************************/
void random1(int n,int m)
{
srand(time(NULL));//使用这个就可以每次运行不同
for(int i=0;i<n;i++)
{
if(rand()%(n-i)<m)
{
cout<<i<<endl;//随机数结果按递增顺序排列
m--;
}
}
}

/****************************************\
函数功能:从n个数中随机选择m个不同的数
函数输入:n为样本空间,m为选择的个数
函数输出:在屏幕上打印选取的数
算法描述:结果范围在[0,n),思想简单:每生成
一个随机数就检查是否与已存在的数重合
\****************************************/
void random2(int n,int m)
{
int *a = new int[m];
srand(time(NULL));//使用这个就可以每次运行不同

a[0]=rand()%n;
int temp=0;
int j=0;
bool flag=true;
for(int i=1;i<m;i++)
{
temp=rand()%n;
flag=true;
for(j=0;j<i;j++)//循环遍历是否有重复的数
{
if(temp==a[j])
{
i--;
flag=false;
break;//其实这里可以用goto语句,但是goto语句不推荐使用
}
}
if(j==i&&flag)
a[i]=temp;

}

for(int k=0;k<m;k++)
cout<<a[k]<<" ";
}

/****************************************\
函数功能:从n个数中随机选择m个不同的数
函数输入:n为样本空间,m为选择的个数
函数输出:在屏幕上打印选取的数
算法描述:结果范围在[0,n),从已存在的数组
a中选择,当n比较大时,占用空间大
\****************************************/
void random3(int n,int m)
{
int i;
srand(time(NULL));//使用这个就可以每次运行不同
int *a=new int[n];
for(i=0;i<n;i++)
a[i]=i;
for(i=0;i<m;i++)
{
int j=i+rand()%(n-i); //随机产生 [i,n-1) 的数作为数组的下标
if(i!=j)
{
int temp=a[i];//将a[i]与a[j]互换
a[i]=a[j];
a[j]=temp;
// swap(a[i],a[j]);//上面三行的互换可以调用库函数
}
}
// sort(&a[0],&a[m]); //进行排序
for(i=0;i<m;i++)
cout<<a[i]<<" ";
}

/****************************************\
函数功能:从n个数中随机选择m个不同的数
函数输入:n为样本空间,m为选择的个数
函数输出:在屏幕上打印选取的数
算法描述:结果范围在[0,n),利用set中
没有重复元素的特性
\****************************************/
void random4(int n,int m)
{
set<int> s; //利用set中没有重复元素的特性
srand(time(NULL));//使用这个就可以每次运行不同
while(s.size()<m)
s.insert(rand()%n); //若是重复元素则不插入

for(set<int>::iterator iter=s.begin();iter!=s.end();iter++)
cout<<*iter<<" ";
}


void main()
{
cout<<RAND_MAX<<endl;//随机数的最大范围32767
//random1(6,4);
//random2(6,4);
//random3(6,4);
random4(6,4);
}
坚持原创技术分享,您的支持将鼓励我继续创作!