怎么设计等概率的随机函数

如何设计等概率的随机函数

本文主要介绍以下主题：

如何设计随机函数，即洗牌算法？

如何设计测试用例检查随机函数的正确性？

随机函数有哪些应用？

Knuth Shuffle的洗牌算法，算法复杂度O(n)，洗牌的目的是产生一串等概率的随机列。
1)如何保证等概率：从r个剩余的元素中选择s个元素，那么下一个元素选中的概率为s/r。
2)假设函数bigrand()返回一个大的随机整数（比m和n个大很多），那么bigrand()%n返回[0,n-1]范围的随机整数
4）应用：其他应用如从n个城市中选择出m个城市的名字，可以先对城市名进行签名标记为0,1,...,n-1
记住：我们面对的随机函数的输入是0,1,...,n-1，具体应用可以运用签名转换成成对应的0,1,...,n-1
5）如果要按序输出，可以先对操作对象排序，然后签名[0,n-1]，这样通过按序访问数，就能保证输出结果是有序的

public int rand7() {      int x = 0;     while(x>21)     {          x = 5 * (rand5()-1) + rand5();  //rand5()生成[1,5]的整数，则rand5()-1生成[0,n-1]的整数    }//end while     return x%7+1;  //x%7生成[0,7-1]的整数，则x%7+1生成[1,7]的整数} //end rand7()

rand()产生的是0~RAND_MAX之间的随机数。产生一定范围随机数的通用表示公式
要取得[a,b)的随机整数，使用(rand() % (b-a))+ a;
要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a;
要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1;
通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。
要取得a到b之间的随机整数，另一种表示：a + (int)b * rand() / (RAND_MAX + 1)。
要取得0～1之间的浮点数，可以使用rand() / double(RAND_MAX)。