1） rand函数和srand函数介绍 随机函数rand() 会随机生成一个位于0-RAND_MAX之间的整数；
#include <stdio.h> #include <stdlib.h> int main() { for (int i = 0; i < 10; i++) printf("%d ", rand()); printf("\n"); return 0; }使用rand()函数的缺点是， 对于同一个种子，总是会产生相同的随机数序列；下面的代码在每次运行程序之后，产生的随机数序列都是相同的；多次运行的结果都是下面输出， 如下图所示： 如果要想每次程序运行产生不一样的随机数序列， 需要改变种子；使用函数 void srand(unsigned int seed); 实际开发过程中使用运行程序的当前时间作为srand参数， 只要运行时间不同， 生成的种子不同。种子不同将使得随机数序列不同； 代码如下：
#include <stdio.h> #include <stdlib.h> #include <time.h> int main() { srand(time(NULL)); for (int i = 0; i < 10; i++) printf("%d ", rand()); printf("\n"); return 0; }多次运行程序的结果是：因为for循环非常快， time函数得到的是秒， 因此在多个循环中time(NULL)的返回值是一样的，导致种子一样；
#include <stdio.h> #include <stdlib.h> #include <time.h> int main() { for (int i = 0; i < 100; i++) { srand(time(NULL)); printf("%d ", rand()); } return 0; }注意，使用下面代码得到的随机数组是不正确的， 2） 生成一定范围内的随机数
生成[a, b) 的随机整数， 使用 (rand() %(b-a)) + a； 生成(a, b] 的随机整数， 使用(rand() %(b-1)) + a+1； 生成[a, b] 的随机整数， 使用(rand() %(b-a+1)) + a； 生成0-1之间的浮点数， 使用rand()/double(RAND_MAX)；
产生随机数最简单的方法是线性同余数生成器， x(i+1) = (A * xi mod M)； 为了开始这个序列， 必须给出x0， x0 就是种子； 一般选取M = 2^31 -1 = 2 147 483 647； 选取A = 48 271；
基于线性同余数生成器的随机数生成器代码如下，C++ 实现：
#include <iostream> #include <time.h> using namespace std; static const int A = 48271; static const int M = (1 << 31) - 1; class Random { public: explicit Random(int initialValue = 1); int randomInt(); double random0_1(); int randomInt(int low, int high); private: int state; }; //将种子传入Random类 Random::Random(int initialValue) { if (initialValue < 0) initialValue += M; state = initialValue; if (state == 0) state = 1; } //计算随机数 int Random::randomInt() { return state = (A * state) % M; } //计算0-1 之间的随机数 double Random::random0_1() { return (double)randomInt() / M; }上述代码存在一个缺陷， 乘法运算 A * state 存在一个溢出的问题，导致结果中出现负数； 根据《数据结构与算法分析》书中的推算和论证， 可以使用下面公式优化； 具体的代码如下：
#include <iostream> #include <time.h> using namespace std; static const int A = 48271; static const int M = (1 << 31) - 1;//2 147 483 647 static const int Q = M / A; static const int R = M % A; class Random { public: explicit Random(int initialValue = 1); int randomInt(); double random0_1(); int randomInt(int low, int high); private: int state; }; //将种子传入Random类 Random::Random(int initialValue) { if (initialValue < 0) initialValue += M; state = initialValue; if (state == 0) state = 1; } //计算随机数 int Random::randomInt() { int tmpState = A * (state % Q) - R * (state / Q); if (tmpState >= 0) state = tmpState; else state = tmpState + M; return state; } //计算0-1 之间的随机数 double Random::random0_1() { return (double)randomInt() / M; } int Random::randomInt(int low, int high) { return (randomInt() % (high - low) + low); } int main() { Random a(time(NULL));//每次程序运行时候，生成的种子都是不同的 cout << a.randomInt() << endl; cout << a.random0_1() << endl; cout << a.randomInt(1, 10) << endl; return 0; }1） 问题分析 rand5() 函数能够生成1， 2， 3， 4， 5的随机数； rand7() 函数能够生成1， 2， 3， 4， 5， 6， 7的随机数； 现在已有rand5() 函数，求通过rand5() 生成rand7();
思路， 先考虑通过rand7() 函数生成rand5() 函数， 代码如下所示：
#include <stdio.h> #include <stdlib.h> #include <time.h> int rand7() { return (rand() % 7 + 1); } int rand5() { int ret; while ((ret = rand7()) > 5); return ret; } int main() { srand(time(NULL)); for (int i = 0; i < 10; i++) printf("%d ", rand5()); return 0; }在rand7() 函数中， 等概率地生成1， 2， 3， 4， 5， 6， 7； 在rand5() 函数中，舍去6， 7， 其余5个数的概率都是1/7， 因此也是等概率的；并且在rand5() 中生成1的概率是= （1/7） /（5/7） = 1/5； 得到一个一般的结论： 如果a > b, 那么一定可以用randa() 去实现randb()； 2） 使用rand5() 生成 rand7() 先将rand5() 函数映射到一个能产生更大随机数的randa() , 其中a > 7;映射后的randa() 一定满足等概率生成1-a； 考虑 rand5() + rand5() -1, 生成1-9的数，但是不是等概率的，生成1 的情形只有(1, 1); 生成2 的情形有(1, 2) 和（2， 1）； 组合 5*(rand5() -1) + rand5()；生成1-25的随机数，并且概率是一致的； 加法的前半部分产生0， 5， 10， 15， 20； 加法的后半部分产生1， 2， 3， 4， 5； 两者加起来刚好是1-25之间， 并且每个数的概率都是1/5， 1/5； 思考： 使用rand5 生成一个更大范围的随机数， 肯定至少调用2次rand5(); 此时生成随机数1的概率为1/5 × 1/5 = 1/25； 要求随机数等概率， 就得生成随机数的范围为1-25； 因此将1-25 分为5个区间[1, 5], [6, 10], [11, 15], [16, 20], [21, 25]； 使用第一个随机数从5个区间中选取一个区间，使用第二个随机数从选定的区间中选取一个数； 得到： 5*(rand5() -1) + rand5()； 相关的代码如下：
#include <stdio.h> #include <stdlib.h> #include <time.h> int rand5() { return (rand() % 5 + 1); } int rand7() { int ret; while ((ret = 5 * (rand5() - 1) + rand5()) >7); return ret; } int main() { srand(time(NULL)); for (int i = 0; i < 10; i++) printf("%d ", rand7()); return 0; }3） 代码优化 上述代码的一个缺点是，会产生1-25的随机数， 但是要截取8-25的数组，需要进行多次while循环之后才能返回得到1-7之间的随机数； 考虑舍去22， 23， 24， 25 这四个数，当返回的是1-21 的时候， 取余数+1 得到1-7的随机数；
#include <stdio.h> #include <stdlib.h> #include <time.h> int rand5() { return (rand() % 5 + 1); } int rand7() { int ret; while ((ret = 5 * (rand5() - 1) + rand5())) { if (ret <= 21) return ret % 7 + 1; } } int main() { srand(time(NULL)); for (int i = 0; i < 10; i++) printf("%d ", rand7()); return 0; }1） 思路1
使用两个rand5()调用最大只能产生1-25 范围的随机数， 使用3次rand5() 调用能生成1-125范围的随机数，然后在生成rand31() 2） 思路2 可以考虑使用rand5 生成rand7，然后使用rand5 和 rand7 生成1-35的随机数，之后裁剪到1-31 的随机数；
