编程珠玑：第12章采样问题学习笔记

本文将基于《编程珠玑》第12章的内容，通过编程实践生成三种类型的大数据文件，以供后续算法学习使用。这三种文件分别是：100万个有序且不重复的随机整数、100万个无序且不重复的随机整数，以及100万个无序且可重复的随机整数。所有数据均小于1000万。

1. 关于课后习题1中的大随机数问题：

   C库函数rand()通常返回约15个随机位。为了实现返回至少30个随机位的函数bigrand()和返回范围在[l, u]内的随机整数的函数randint(l, u)，可以使用以下代码：

   int bigrand()
   {
       return RAND_MAX * rand() + rand();
   }
   
   int randint(int l, int u)
   {
       return l + bigrand() % (u - l + 1);
   }

   需要注意的是，RAND_MAX在Windows下的VC环境中通常是32767（即0x7FFF），而在GNU环境下则是2^31-1。因此，在生成大随机数时，不需要重新定义bigrand()函数。如果不确定RAND_MAX的值，可以在程序中打印出来查看。否则可能会出现负的随机数，特别是在Linux中执行相关程序时可能导致内核崩溃。

2. 关于第三种方法，即将包含整数0到n-1的数组顺序随机打乱，然后输出前m个元素：

   书中提供的代码如下：

   void genshuf(int m, int n)
   {
       int i, j;
       int *x = new int[n];
       for (i = 0; i 
   上述代码中，new分配的内存需要在最后释放，以防止内存泄漏。如果希望输出的随机数不按顺序排列，可以去掉sort(x, x + m)这一行。将输出结果保存到文件中，可以在Linux下执行命令：./a.out > out.txt。

3. 关于课后习题：

   后续将继续补充。