抽奖机随机号码序列生成算法实现与比较
抽奖机随机号码序列生成算法实现与比较
一、课题背景
本课题以“抽奖机随机号码生成”为应用场景，实现并比较四种随机抽样算法，包括：
基础随机法
洗牌算法（Fisher–Yates）
加权随机法
批量随机法
目标是学习随机算法原理、实现方式以及效率比较。
二、课程设计目标
1. 知识目标
理解随机算法思想
掌握 Fisher–Yates 洗牌算法
能用 C++ 生成无重复随机序列
了解加权随机抽取的概率控制方法
2. 能力目标
提升编程实现能力
能分析不同算法的复杂度和适用性
三、算法原理
1. 基础随机法
不断生成随机数，若不重复则加入结果。
缺点：查重开销大，效率低。
2. 洗牌算法（Fisher–Yates）
步骤：
构建完整号码池
从后向前遍历
与
[0..i]随机位置交换取最后 k 个作为结果
优点：等概率、高效率。
3. 加权随机法
通过权重控制被选中的概率，用于“某些号码更容易中”的场景。
4. 批量随机法
一次生成一批随机数，统一去重，提高效率。
四、程序设计与实现（C++）
#include <iostream> #include <vector> #include <unordered_set> #include <algorithm> #include <ctime> #include <numeric> using namespace std; // ====================== 方法1：基础随机法 ====================== vector<int> randomDraw_basic(int min_num, int max_num, int k) { vector<int> result; if (min_num > max_num || k <= 0 || k > (max_num - min_num + 1)) { return result; } int total_num = max_num - min_num + 1; while (result.size() < k) { int num = rand() % total_num + min_num; bool is_duplicate = false; for (int v : result) { if (v == num) { is_duplicate = true; break; } } if (!is_duplicate) { result.push_back(num); } } return result; } // ====================== 方法2：洗牌算法 ====================== vector<int> randomDraw_shuffle(int min_num, int max_num, int k) { vector<int> pool; for (int i = min_num; i <= max_num; ++i) { pool.push_back(i); } int n = pool.size(); if (k >= n) return pool; for (int i = n - 1; i >= n - k; --i) { int rand_idx = rand() % (i + 1); swap(pool[i], pool[rand_idx]); } return vector<int>(pool.end() - k, pool.end()); } // ====================== 方法3：加权随机法 ====================== vector<int> randomDraw_weighted(int min_num, int max_num, int k, const vector<double>& weights) { vector<int> result; unordered_set<int> used; double total_weight = accumulate(weights.begin(), weights.end(), 0.0); while (result.size() < k) { double r = (rand() / (double)RAND_MAX) * total_weight; double cur = 0.0; int selected = -1; for (int i = 0; i < weights.size(); ++i) { cur += weights[i]; if (cur >= r) { selected = min_num + i; break; } } if (selected != -1 && used.find(selected) == used.end()) { used.insert(selected); result.push_back(selected); } } return result; } // ====================== 方法4：批量随机法 ====================== vector<int> randomDraw_batch(int min_num, int max_num, int k) { vector<int> result; unordered_set<int> used; int total_num = max_num - min_num + 1; const int BATCH = k * 2; while (result.size() < k) { vector<int> temp; for (int i = 0; i < BATCH; i++) { temp.push_back(rand() % total_num + min_num); } for (int num : temp) { if (used.find(num) == used.end()) { used.insert(num); result.push_back(num); if (result.size() == k) break; } } } return result; } void printResult(const vector<int>& nums, const string& name) { cout << "【" << name << "】:"; for (int v : nums) cout << " " << v; cout << endl; } int main() { srand((unsigned)time(nullptr)); const int MIN = 1, MAX = 50, K = 6; vector<double> weights(MAX - MIN + 1, 1.0); for (int i = 0; i < weights.size(); i++) { if (MIN + i >= 20 && MIN + i <= 30) { weights[i] = 3.0; } } printResult(randomDraw_basic(MIN, MAX, K), "基础随机法"); printResult(randomDraw_shuffle(MIN, MAX, K), "洗牌算法"); printResult(randomDraw_weighted(MIN, MAX, K, weights), "加权随机法"); printResult(randomDraw_batch(MIN, MAX, K), "批量随机法"); return 0; }五、运行结果示例
【基础随机法】: 5 13 27 40 48 2 【洗牌算法】: 10 21 6 34 8 49 【加权随机法】: 22 27 25 6 30 41 【批量随机法】: 7 16 29 11 3 44六、结果分析
基础随机法：实现简单，但效率最低。
洗牌算法：随机性最强，效率最高，工程最常用。
加权随机法：可人为控制概率，结果偏向权重高的区间。
批量随机法：性能介于基础法和洗牌法之间。
七、课程设计总结
通过本次课程设计，我掌握了随机算法的实现方式，并理解了：
随机数生成不仅是调用 rand()，还需关注均匀性和去重方式
Fisher–Yates 是真正保证等概率的算法
加权抽取可灵活实现概率控制
批量生成可显著提高效率
本次课设提高了我的算法能力、工程实现能力以及团队合作能力。