##题目##

为分析用户行为，系统常需存储用户的一些query，但因query非常多，故系统不能全存，设系统每天只存m个query，现设计一个算法，对用户请求的query进行随机选择m个，请给一个方案，使得每个query被抽中的概率相等，并分析之，注意：不到最后一刻，并不知用户的总请求量。

##解法##

#include

#include

#define N 1000

#define M 11

void getRandM(int *a, int n, int *result, int m)

{

int i,j;

for(i=0; i

result[i] = a[i];

}

for(j=i; j

int randN = rand()%j;

if(randN >=0 && randN < m){

int randChange = rand()%m;

result[randChange] = a[j];

}

}

}

int main(){

int inStream[N];

int i = 0;

for(i=0; i

inStream[i] = i;

}

int outStream[M];

getRandM(inStream, N, outStream, M);

for(i=0; i

printf("%d ",outStream[i]);

printf("\n");

return 0;

}

[3].编程珠玑.采样一节.