虽然TX的面试已经过去好几天了，然而惨痛的过程还历历在目。人生中第一次正式job面试就这么挂掉了。在于面试官的交流过程中，被问及了几个算法设计题，在今后几篇博文中，我一一总结与诸君分享。
1. 给定一个函数rand()能产生1到m之间的等概率随机数，产生1到n之间等概率的随机数？ （为了简化问题，此处m小于n）
当被问到这个问题的时候，LZ我首先的想法就是能不能通过一次Rand就可以把结果找到。然后这个想法就被瞬间推翻了。
那么能否通过多次选取，然后组合呢? 答案是肯定的，然而悲剧的是，当时LZ的脑袋有点混乱了，想到了几个思路都不完备。
这几天冷静下来之后，仔细想了想，现给出一个可行的方案，跟大家讨论讨论。
假设：
已知函数 RandM能够生成[1,m]之间的随机数，满足均匀分布
Rand_mn 在已有RandM的基础上，生成均匀分布的[1,n]之间随机数的函数
m： 已知随机数最大值
n: 目标随机数最大值
PS : 此处约定 m<n && n< m*m
-----------------------------------------
思路：
（1） 通过分别两次生成[1,m]之间的均匀分布的随机数x,y那么 x,y 都属于[1,m]，如果要将x和y进行组合的话
其最小覆盖问题变成了
|
z = a*x +y min a 使得z的取值均匀分布 s.t. x属于[1,m] y属于[1,m] |
（2） 由于 x,y 都是在[1,m]之前取值， 所以a能取的最小值为m。
（3） 当a=m时，z的取值范围为 [m+1, m*(m+1)]
若z=z-m, 则z的取值范围就变成了 [1, m*m],并且是均匀分布
（4） 此时，我们的问题就简化成了将[1,m*m]区间的值映射到[1,n]
（5） 采用“舍去法”， 令 re = m*m mod n,可知多余元素的个数
当z的值为(m*m-re, m*m]时，递归进行新的随机数生成，否则进行步骤6
（6） 将[1, m*m -re] 均匀分成n份， 每份的间隔为 gap = (m*m -re)/n;
C++代码实现如下：
#include <iostream> #include <cmath> #include <ctime> using namespace std; int RandM(int m) { return rand()%m +1; } /******************************************** * Rand_mn 在已有RandM的基础上， * 生成均匀分布的[1,n]之间随机数的函数 * m： 已知随机数最大值 * n: 目标随机数最大值 * * PS : 此处约定 m<n && n< m*m * ----------------------------------------- * 思路： * （1） 通过分别两次生成[1,m]之间的均匀分布的随机数x,y * 那么 x,y 都属于[1,m]，如果要将x和y进行组合的话 * 其最小覆盖问题变成了 z = a*x +y min a 使得z的取值均匀分布 * （2） 由于 x,y 都是在[1,m]之前取值， 所以a能取的最小值 * 为m。 * （3） 当a=m时，z的取值范围为 [m+1, m*(m+1)] * 若z=z-5, 则z的取值范围就变成了 [1, m*m],并且是均匀分布 * (4) 此时，我们的问题就简化成了将[1,m*m]区间的值映射到[1,n] * （5） 采用“舍去法”， 令 re = m*m mod n,可知多余元素的个数 当z的值为(m*m-re, m*m]时，递归进行新的随机数生成，否则进行步骤6 * （6） 将[1, m*m -re] 均匀分成n份， 每份的间隔为 gap = (m*m -re)/n; *********************************************/ int Rand_mn(int m,int n) { int rand1 = RandM(m), rand2 = RandM(m); int temp = m*rand2 + rand1; int re = m*m%n; // 多余个数 int gap =(m*m -re)/n; // 取值间隔 if((m+1)*m-re<temp && temp<=m*(m+1)) // 需要舍弃的部分 return Rand_mn(m,n); else return (temp - m -1)/gap +1; //返回随机结果 } int main() { int m,n; srand((unsigned )time(NULL)); while(cin>>m>>n) { int t=100; while(t--) cout<<Rand_mn(m,n)<<endl; cout<<endl; } return 0; }