C++随机数（rand和srand）函数用法详解（三）

解决一个问题：

从0....n-1中随机等概率的输出m个不重复的数。这里我们假设n远大于m

1. 方法一

最初的思想是每生成一个随机数，便于前面的所有随机数进行比较，如果有重复，则舍去不要，重新选取。但该方法十分费时，并且在数据量巨大的并且有一定限制的时候，会引发巨大问题。例如要生成10000个随机数，范围是0-9999，且不能重复，那么最后几个随机数有可能需要相当长的时间才能筛选出来。

下面我们从另外一个角度来思考，假设我们已经有一个数组长度为10000的数组，里面分别存储了数据0-9999，我现在的做法是想办法让10000个数进行随机排列，便得到了这样一个随机数列，如果我只要其中的100个数，那么从前面取出100个就好。这里利用algorithm.h里面的一个函数，来进行简单处理。

template<class RandomAccessIterator>  
    void random_shuffle(
      RandomAccessIterator _First, 
      RandomAccessIterator _Last
);

这个函数操作的对象是容器的迭代器，即我们需要将存储数据从数组变为容器就好了，下面代码实现一下：

void knuth(int n, int m)
{
	srand((unsigned)time(0));
	vector<int> temp;
	for (int i = 0; i < n; ++i)
	{
		temp.push_back(i);
	}

	random_shuffle(temp.begin(), temp.end());

	for (int i = 0; i < m; i++)
	{
		std::cout << temp[i] << " ";
	}
}

2. 方法二

按顺序产生这些数，但随机生成它们的位置。

void knuth(int n, int m)
{
	srand((unsigned)time(0));
	int *a=new int[n];
	int i;
	for (i = 0; i < n; i++) a[i] = i;
	for (i = n - 1; i > n - 1 - m; i--)
	{
		swap(a[i], a[rand() % (i + 1)]);
		cout << a[i] << endl;
	}
}

上面这段代码只需要遍历一次就可以产生这m个不重复的随机数，它是如何做到的呢？首先按顺序用0到n-1填满整个数组；随后，不断随机产生从0到i的一个数组下标，把这个下标的元素值跟i下标的元素值交换，一直进行到下标i为n-m的元素。因此它只需要遍历一次就能产生全部的随机数。

2. 方法三

void knuth(int n, int m)
{
	srand((unsigned)time(0));
	for (int i = 0; i < n; i++) {
		if (rand() % (n - i)<m) {
			cout << i << endl;
			m--;
		}
	}
}

首先在0....n-1这n个数中，随机等概率的输出m个不重复的数，则在第一次操作中每个数被输出的概率皆为：

第i(1<=i<=m)项分别代表第i次被输出的概率，因此在第一次操作中每个数被输出的概率皆为：m/n

注意：上面所讲的两次输出含义不一样

所以在第一次准备输出0时，其概率应该为 : m/n ;

第二次准备输出阶段的余下各数的输出概率需根据第一次那个数输出与否来决定；

因此在第二次准备输出1时，其概率应该是：

若第一次的那个数（即0）输出了，这次这个数（即1）输出概率为（m-1）/（n-1）；

若第一次的那个数（即0）没有输出，这次这个数（即1）输出概率为（m）/（n-1）；

一共有n次准备输出阶段，以此类推。

解决该问题的核心是要知道，每当输出一个数时，其需要输出的数的个数（即m）需要减1；每当遍历完一个数时，其能够选择的数的个数减1。依此来决定下一次准备输出阶段输出的概率。

该问题也是一种递推问题。

参考：https://www.cnblogs.com/VVingerfly/p/5990714.html

牛客网