题目描述：从n个元素抽取k个元素，使得每个元素被抽取的概率相同
思路：按照蓄水池抽样算法，先将n个元素的前k个元素加入到被抽取的集合中，再从i=k+1开始遍历，每次从1-i之间随机取一个数m，若该数m小于等于k，则将当前第i个数替换掉被抽取的集合中第m个数，遍历结束后，被抽取的集合即为所求
证明：
使用数学归纳法，若n=k时，显然成立
当n=m时成立，对于n=m+1，已知对前m个数可以做到使每个数被等概率抽取，即每个数被抽取的概率为
k/m,对于i=m+1，从1-m+1之间随机取一个数s,则第m+1个数被抽取的概率为k/m+1(即当s<=k时),前m个数中的数被抽取的概率为(k/m)*(m/(m+1))=k/(m+1),i=m+1成立
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <bits/stdc++.h>
using namespace std;
int main(){
int n,k;
int a[100];
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
srand(time(0));
for(int i=k+1;i<=n;i++){
int m=rand()%i+1;
if(m<=k){
a[m]=a[i];
}
}
cout<<"所求的k个数为：";
for(int i=1;i<=k;i++){
cout<<a[i]<<" ";
}
cout<<endl;
return 0;
}
|