我们可以使用 C++ 随机数生成器，根据题目要求构造各种规模的输入数据，对自己编写的程序进行检测。

随机数据生成

方法1：srand() 与 rand()

头文件 cstdlib(stdlib.h) 包含 rand 和 srand 两个函数，以及 RAND_MAX 常量。

RAND_MAX 是一个不小于 32767 的整数常量，它的值与操作系统环境、编译器环境有关，一般来说 Windows 系统中为 32767 ，在类 Unix 系统中为 2147483647 。

rand() 函数返回一个 0-RAND_MAX 之间的随机整数 int 。

srand(seed) 函数接受 unsigned int 类型的参数 seed ，以 seed 为“随机种子”。rand 函数基于线性同余递推式生成随机数，“随机种子”相当于计算线性同余时的一个初始参赛，感兴趣可以查阅相关资料。若不执行 srand 函数，则种子默认为 1 。

当种子确定后，接下来产生的随机数列就是固定的，所以这种随机方法也称为“伪随机”。 因此，一般在随机数据生成程序 main 函数开头，用当前系统时间作为随机种子。

头文件 ctime(time.h) 包含 time 函数，调用 time(0) 可以返回从 1970 年 1 月 1 日 0 时 0 分 0 秒（Unix纪元）到现在的秒数。 执行 srand((unsigned)time(0)) 即可初始化随机种子。 （注意使用 time 函数作为种子，单位是秒，如果在一秒内多次运行程序，可能会得到相同的数据）

下面的程序可作为随机数据生成器的模板，函数 random(n) 返回 0 ~ n-1 之间的随机整数。

#include<bits/stdc++.h>
using namespace std;
int random(int n)
{
	return (long long)rand()*rand()%n;
}
int main()
{
	srand((unsigned)time(0));   //使用时间初始化随机数种子
	int x=random(100);   //得到 0~99 之间的一个数 
	//...
	return 0;
}

方法二：mt19937

rand() 函数生成的随机数质量不高，可查阅 Don't use rand(): a guide to random number generators in C++

mt19937 生成的随机数质量高（一个表现为，出现循环的周期更长；其他方面也都至少不逊于 rand()），且速度比 rand() 快很多。使用时需要 #include，随机数的范围同 unsigned int 类型的取值范围。

mt19937 基于 32 位梅森缠绕器，由松本与西村设计于 1998 年，使用时用其定义一个随机数生成器即可：std::mt19937 myrand(seed)，seed 可不填，不填 seed 则会使用默认随机种子。

mt19937 重载了 operator ()，需要生成随机数时调用 myrand() 即可返回一个随机数。

另一个类似的生成器是 mt19937_64，基于 64 位梅森缠绕器，由松本与西村设计于 2000 年，使用方式同 mt19937，但随机数范围扩大到了 unsigned long long 类型的取值范围。

另外一点需要注意就是，如果单纯使用 time(0) 作为随机化种子，那么在对拍时，同一秒内，会得到相同的随机数，为了避免这个问题，可以将随机种子改为 time(NULL)^clock()

time(0) 返回的是秒为单位，clock() 函数可以返回自程序开始执行到当前位置为止, 处理器走过的时钟打点数(即"ticks", 可以理解为"处理器时间")，即使在一秒内，两个函数异或之后得到的种子都不会相同。

mt19937 rnd(time(NULL)^clock());
int rad(int x,int y)  //获得 [x,y] 之间的整数
{
	return rnd()%(y-x+1)+x;
}

考虑到 mt19937 随机数据效果更好，之后的例子中都用 mt19937 获得，即调用 int rad(int x,int y) 函数。

---

【实例1】随机生成整数序列

随机生成 $n(n\leq 10^5)$ 个绝对值在 $10^9$ 之内的整数。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int a[N];
mt19937 rnd(time(NULL)^clock());
int rad(int x,int y)
{
	return rnd()%(y-x+1)+x;
}
signed main()
{
	int n=rad(1,1e5);  //1e5是double类型，传递给int后自动转换int类型
	int m=1e9;
	for(int i=1;i<=n;i++)a[i]=rad(-1e9,1e9);
	//for(int i=1;i<=100;i++)cout<<a[i]<<"\n";
	return 0;
}

【实例2】随机生成区间列

随机生成 m 个 [1,n] 的子区间，这些区间可以作为数据结构题目的操作序列。

for(int i=1;i<=m;i++)
	{
		int l=rad(1,n);
		int r=rad(1,n);
		if(l>r)swap(l,r);
		printf("%lld %lld\n",l,r);
	}

【实例3】随机生成树

随机生成一颗 n 个点的树，即 n-1 条边的无连通向图，边权为 $[1,10^9]$ 的整数。

for(int i=2;i<=n;i++)
	{
		//从 [1,i-1] 任选一点与 i 连边 
		int fa=rad(1,i-1);
		int val=rad(1,1e9);
		printf("%lld %lld %lld",fa,i,val);
	}

【实例4】随机生成图

随机生成一张 n 个节点 m 条边的无向图，图中没有重边、自环，且连通，保证 $5\leq n\leq m\leq \frac{n\times(n-1)}{4} \leq 10^6$ 。（注超过这个范围，就是稠密图，可以考虑生成补图）

void build(int n,int m)
{
	const int N=1e5+10;
	pair<int ,int >e[N];
	map<pair<int,int>,bool>h;
	//生成树
	for(int i=1;i<n;i++)
	{
		int fa=rad(1,i);
		if(rad(0,10)<6)fa=rad(max(i-10,1ll),i);  //保证深度足够
		e[i]=make_pair(fa,i+1);
		h[e[i]]=h[make_pair(i+1,fa)]=1;
	}
	//再生成剩下的 m-n+1 条边
	for(int i=n;i<=m;i++)
	{
		int x,y;
		do{
			x=rad(1,n); y=rad(1,n);
		}while(x==y||h[make_pair(x,y)]);
		e[i]=make_pair(x,y);
		h[e[i]]=h[{y,x}]=1;
	}
	//随机打乱
	random_shuffle(e+1,e+m+1);
	for(int i=1;i<=m;i++)
	{
		//int w=rad(1,1e4);
		cout<<e[i].first<<" "<<e[i].second<<"\n";
	}		
}

在树、图结构中，有三类特殊数据用于程序进行极端测试：

1. 链行数据-很长的直径。

建立 i-1 与 i 的边。这种数据会造成很大的递归深度，也是点分治算法需要特别注意的数据。

2. 菊花形形数据。

任意选择一个作为中心，其余点与此点连边。这种数据画出来像一朵“菊花”，缩点等图论算法处理不当，复杂度容易在这种数据上退化。

3. 蒲公英形数据。

即链形与菊花形数据综合。 令树的一部分构成链，一部分构成菊花，再把两部分链接。

以上三种构图方法，再添加少量随机边，可得到一张既包含局部特殊结构、又不失一般性和多样性的图。

学习完毕

{{ select(1) }}

• YES
• NO