C语言如何生成不重复的随机数？

C语言实现不重复随机数：从基础到高效算法，一篇搞定！

** 在C语言编程中，生成不重复的随机数是一个常见且重要的需求，尤其在游戏开发、数据采样、密码学等领域，本文将从C语言随机数生成的底层原理讲起，逐步深入到多种实现不重复随机数的方法，包括朴素法、置换法、哈希表法等，并提供完整可运行的代码示例，助你彻底攻克这一技术难题。

引言：为什么我们需要“不重复”的随机数？

想象一下,你要开发一个扑克牌游戏，需要发牌给玩家，如果发出去的牌有重复，那游戏就失去了公平性，再比如，你需要从1000个用户中随机抽取10名幸运用户，如果某个用户被抽中多次，显然不符合抽奖的初衷。

生成不重复的随机数，其核心在于保证一个序列中的每个元素都是唯一的，C语言的标准库提供了生成随机数的函数，但它们本身并不能保证不重复，我们该如何实现呢？别担心，接下来我们将一步步拆解这个问题。

C语言随机数生成基础：rand() 和 srand()

在讨论“不重复”之前，我们必须先理解C语言是如何生成随机数的。

1. rand() 函数

   • 功能： 生成一个介于 0 到 RAND_MAX 之间的伪随机整数。RAND_MAX 是一个宏，通常值为32767或更大。
   • 原理： rand() 并不是真正的随机，它是一个伪随机数生成器（PRNG），它的内部状态是一个种子值，每次调用都会根据这个种子值计算出下一个“随机数”，如果种子相同，生成的随机数序列也会完全相同。

2. srand() 函数

   • 功能： 为 rand() 函数设置种子。

   • 为什么需要它？ 为了避免每次程序运行时都生成相同的随机数序列（因为默认种子可能是固定的）。

   • 最佳实践： 通常使用当前时间作为种子，因为时间是不断变化的，代码如下：

     #include <stdio.h>
     #include <stdlib.h> // rand(), srand()
     #include <time.h>   // time()
     int main() {
         // 使用当前时间作为随机数生成器的种子
         // time(NULL) 返回自1970年1月1日以来的秒数
         srand((unsigned int)time(NULL));
         for (int i = 0; i < 10; i++) {
             printf("%d ", rand() % 100); // 生成0-99的随机数
         }
         return 0;
     }

小结： srand(time(NULL)) 是获得“看似随机”数列的标准做法，但这并不能保证不重复。

核心挑战：如何实现“不重复”？

现在我们进入正题,要生成不重复的随机数，关键在于“已生成的数”与“待生成的数”之间的管理，下面我们介绍几种主流方法，从简单到高效。

朴素法（暴力法）

这是最直观的思路：生成一个数，检查它是否已经出现过，如果出现过就重新生成，直到生成一个不重复的数为止。

算法步骤：

1. 定义一个数组或链表来存储已经生成的随机数。
2. 循环生成随机数。
3. 对于每个新生成的数,遍历已存储的数组，检查是否存在。
4. 如果不存在,则将其存入数组，并继续下一个。
5. 如果存在,则放弃此数，重新生成。

代码示例：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
#define ARRAY_SIZE 10
#define MAX_NUM 100
bool isUnique(int arr[], int size, int num) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == num) {
            return false;
        }
    }
    return true;
}
int main() {
    int uniqueNumbers[ARRAY_SIZE];
    int count = 0;
    srand((unsigned int)time(NULL));
    while (count < ARRAY_SIZE) {
        int randomNum = rand() % MAX_NUM;
        if (isUnique(uniqueNumbers, count, randomNum)) {
            uniqueNumbers[count] = randomNum;
            count++;
        }
    }
    printf("生成的%d个不重复随机数是:\n", ARRAY_SIZE);
    for (int i = 0; i < ARRAY_SIZE; i++) {
        printf("%d ", uniqueNumbers[i]);
    }
    printf("\n");
    return 0;
}

优点：

• 逻辑简单,容易理解和实现。

缺点：

• 效率低下：当需要生成的随机数数量接近范围上限时（从100个数中取99个），冲突会急剧增加，导致大量的无效循环和重复检查，性能会变得非常差，这种方法的时间复杂度在最坏情况下接近 O(n²)。

置换法（Fisher-Yates Shuffle / Knuth Shuffle）

这是最高效、最经典的方法，尤其适用于需要在一个固定范围内生成不重复随机数序列的场景（1到N的乱序排列）。

核心思想： 我们不是“凭空”生成随机数，而是从一个有序的数列开始，然后通过随机交换的方式将其打乱，这样，打乱后的数列自然就是一个不重复的随机序列。

算法步骤：

1. 创建一个包含所有可能数字的数组,int pool[] = {1, 2, 3, ..., N}。
2. 从数组的最后一个元素开始,倒序遍历。
3. 在每一步 i，生成一个 0 到 i 之间的随机索引 j。
4. 交换 pool[i] 和 pool[j] 的值。
5. 遍历结束后,pool 数组就是一个完全打乱的、不重复的随机序列。

代码示例：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 20 // 生成1到20的不重复随机数
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
void fisherYatesShuffle(int arr[], int size) {
    for (int i = size - 1; i > 0; i--) {
        // 生成一个 0 到 i 之间的随机索引
        int j = rand() % (i + 1);
        // 交换元素
        swap(&arr[i], &arr[j]);
    }
}
int main() {
    int pool[N];
    // 初始化池子
    for (int i = 0; i < N; i++) {
        pool[i] = i + 1;
    }
    srand((unsigned int)time(NULL));
    // 进行洗牌
    fisherYatesShuffle(pool, N);
    printf("洗牌后的%d个不重复随机数是:\n", N);
    for (int i = 0; i < N; i++) {
        printf("%d ", pool[i]);
    }
    printf("\n");
    return 0;
}

优点：

• 效率极高：时间复杂度为 O(N)，性能稳定且优秀。
• 结果是完美的随机排列,每个数字出现的概率均等。

缺点：

• 需要一个与范围大小相当的数组作为“池子”，如果范围非常大（1到10亿），内存消耗会很高。

哈希表法（适用于超大范围）

当随机数的范围非常大,无法一次性存入内存时（从1到10亿中随机取1000个不重复的数），置换法就不再适用，这时，哈希表法（或更准确地说是基于集合的方法）是更好的选择。

核心思想： 使用一个数据结构（如C++的std::unordered_set，或C语言中自己实现的哈希表）来记录已经生成的随机数，由于哈希表的查找和插入平均时间复杂度为 O(1)，所以效率很高。

注意： 在纯C语言中，标准库没有内置的哈希表，我们可以使用一个“标记数组”来模拟，但这只适用于范围不是特别大的情况（例如范围在百万级别），如果范围极大，实现一个高效的哈希表会非常复杂，这里我们以概念性代码和思路为主。

代码思路（C语言伪代码/概念）：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// 假设我们有一个简单的哈希表结构（实际实现会更复杂）
#define HASH_SIZE 1000000 // 哈希表大小，应大于要生成的随机数数量
int hashTable[HASH_SIZE] = {0}; // 0表示未使用，1表示已使用
int main() {
    int count = 0;
    int targetCount = 1000;
    int range = 10000000; // 范围是1到一千万
    srand((unsigned int)time(NULL));
    while (count < targetCount) {
        int randomNum = (rand() % range) + 1; // 生成1到range的随机数
        // 检查哈希表
        if (hashTable[randomNum] == 0) { // 如果这个数还没被使用
            hashTable[randomNum] = 1;     // 标记为已使用
            printf("%d ", randomNum);
            count++;
        }
    }
    printf("\n");
    return 0;
}

优点：

• 内存效率高：如果只需要取少量数，内存占用与目标数量成正比，而不是与整个范围成正比。
• 查找和插入速度非常快。

缺点：

• 在纯C语言中实现一个高效、无冲突的哈希表有一定难度。
• 如果目标数量接近范围大小,哈希表会变得非常稀疏，空间利用率不高。

方法对比与选择指南

如何选择？

• 如果你的需求是“从1到100中随机取10个数”：直接使用置换法，这是最优雅、最高效的解决方案。
• 如果你的需求是“从1到1000000中随机取100个数”：哈希表法是最佳选择，你可以用一个足够大的标记数组来模拟哈希表。
• 如果你的需求是“从1到10亿中随机取1000个数”：必须使用哈希表法，并且需要仔细设计哈希函数以处理冲突，或者，可以考虑更高级的算法，如“蓄水池抽样”，但实现更复杂。
• 如果你的需求非常简单，比如只是取3-5个不重复的数：为了代码简洁，可以考虑朴素法，因为性能问题不明显。

总结与最佳实践

在C语言中实现不重复随机数,没有“银弹”，最佳方法取决于你的具体应用场景。

1. 牢记基础：srand(time(NULL)) 是获得随机序列的前提。
2. 首选置换法：对于大多数常见的、范围可控的场景（如抽奖、发牌、乱序数组），Fisher-Yates洗牌算法是无可争议的王者，它兼顾了效率、正确性和实现的简洁性。
3. 应对超大范围：当数字范围大到无法创建完整数组时，哈希表法是必然选择，虽然C语言原生支持较弱，但其思想是解决此类问题的核心。
4. 避免朴素法：除非场景极其简单，否则应尽量避免使用朴素法，因为它在数据量稍大时就会成为性能瓶颈。

希望这篇文章能为你提供一份清晰、完整、可操作的C语言不重复随机数生成指南，从理论到实践，从基础到进阶，助你在编程道路上更加得心应手！