作者：dabing🧁

算法小白开始算法学习了，从最简单的开始，一步一步来，这里记录一下。

第二天～

随机函数：[0,1) 之间的数等概率随机

Math.Random();

# 1- 测试随机函数是等概率

	/**
	* 测试 Math.random () 是否等概率
	* 这里测试 0.5
	*/
	public static void testP(){
	int testTimes=10000000;// 执行 100 万次
	int count=0;
	double p=0d;
	for (int i = 0; i < testTimes; i++) {
	double ans=Math.random();
	if(ans<0.5){
	count++;
	}
	}
	p=(double)count/(double)testTimes;
	System.out.println(p);//0.4999083 即 & lt;0.5 的概率，这里约等于 0.5 说明是等概率的。
	}

# 2 - 由 random 到其他随机数

	// 等概率返回 [0,8) 随机数
	Math.random()*8

	// 等概率返回 [0,8) 随机整数，即 [0,7]
	(int)(Math.random()*8)

	// 等概率返回 [1，5] 整数随机
	(int)(Math.random()*5)+1

	....

# 3 - 由 [1,5] 到 [1,7]

只给你一个 f() 函数， f() 表示等概率返回 [1,5] 的随机整数，让你使用 f() 得到 f0() ，等概率返回 [1,7] 的随机整数，就是不许你用 Math.random() ;

思路：

1、整数 0，1，2，3…7，的二进制位都是由 0 和 1 组成的。

2、因此能不能控制将 f() 得到 f1() 等概率返回 0 和 1？----> 可以，因为返回 1 或 2 的概率跟返回 4 或 5 的概率是一样的，也就是等概率，都是 2/5。-----> 控制返回 1 或 2 的时候是事件 0，返回 4 或 5 是事件 1，返回 3 的时候重做。这样事件 0 和事件 1 是等概率的（不明白可以看下面的代码展示）

3、由 f1() 排列组合正好就能随机得到 [0,7]，即 f2()

4、由 f2() 得到 [1,7] 随机整数，即题目所需 f0()

5、总结一套通用方法

代码实现：

	/**
	* 由函数 f ()---> 得到 [1,7] 的随机整数
	* 这个方法比较通用
	* 如 f () 表示得到 [1,5] 的随机整数
	*/
	public static int f(){
	return (int)(Math.random() * 5)+1;
	}

	/**
	* 由 f ()---> 等概率返回 0 和 1
	*/
	public static int f1(){
	int ans=0;
	do{
	ans=f();
	}while (ans==3);// 遇到 3 重做
	return ans<3 ? 0 : 1;
	}


	/**
	* 由 f1 ()----> 等概率返回 [0,7] 的随机整数
	*/
	public static int f2(){
	return (f1()<<2) + (f1()<<1) + (f1()<<0);
	}

	/**
	* 由 f2 ()---> 等概率返回 [1,7]
	* 遇到 0 重做
	*/
	public static int f0(){
	int ans=0;
	do{
	ans=f2();
	}while (ans==0); // 遇到 0 重做
	return ans;
	}

# 4 - RandomBox 到任意范围随机整数

同样思路，给你一个 RandomBox，不管他是随机得哪个范围，只要找到等概率的事件，把这两个事件当作 0 和 1，就都能组成任何范围的数。

思路：

1、找等概率事件，范围 [min,max] ，分两半，左一半，右一半，如果有中间就重做。

如果是奇数，就有中间一个数得重做。偶数就正好一半，不用重做

2、由 RandomBox–> 等概率返回 0 和 1

3、确定 from–>to 需要多少个二进制位

4、随机组合返回整数

	/**
	* 更加通用的，给你一个 RandomBox, 等概率返回任意范围的随机整数
	* 然后让你通过这个 RandomBox 来实现等概率返回指定范围的随机整数
	*/
	public static class RandomBox {
	// 这个结构是唯一的随机机制
	// 你只能初始化并使用，不可修改
	private final int min;
	private final int max;

	// 初始化时请一定不要让 mi==ma
	public RandomBox(int mi, int ma) {
	min = mi;
	max = ma;
	}

	// 13 ~ 17
	// 13 + [0,4]
	public int random() {
	return min + (int) (Math.random() * (max - min + 1));
	}

	public int min() {
	return min;
	}

	public int max() {
	return max;
	}
	}

	public static int rand01(RandomBox randomBox){
	int min=randomBox.min();
	int max=randomBox.max();
	// 判断是否为奇数
	int size=max-min+1;
	boolean odd = size % 2 == 1 ; // 与 2 取余为 1 即为奇数
	int mid=size/2;
	int ans=0;
	do{
	ans=randomBox.random()-min;
	}while (odd && ans==mid);
	return ans < mid ? 0 : 1;
	}

	// 给你一个 RandomBox，这是唯一能借助的随机机制
	// 等概率返回 from~to 范围上任何一个数
	// 要求 from<=to
	public static int random(RandomBox randomBox, int from, int to) {
	if (from == to) {
	return from;
	}
	// 3 ~ 9
	// 0 ~ 6
	// 0 ~ range
	int range = to - from;
	int num = 1;
	// 求 0～range 需要几个 2 进制位
	while ((1 << num) - 1 < range) {
	num++;
	}

	// 我们一共需要 num 位
	// 最终的累加和，首先 + 0 位上是 1 还是 0，1 位上是 1 还是 0，2 位上是 1 还是 0...
	int ans = 0;
	do {
	ans = 0;
	for (int i = 0; i < num; i++) {
	ans \|= (rand01(randomBox) << i);
	}
	} while (ans > range);
	return ans + from;
	}

# 5 - 对数器

利用 Math.random () 生成随机的数组序列，对代码进行测试。

如：生成随机大小的数组序列

	/**
	* 生成随机大小的随机序列
	* @param maxLen 最大长度
	* @param maxVal 最大数字
	* @return
	*/
	public static int[] randArrs(int maxLen,int maxVal){
	int length=(int)(Math.random()*(maxLen+1));
	int[] arr=new int[length];
	for (int i = 0; i < length; i++) {
	arr[i]=(int)(Math.random()*(maxVal+1));
	}
	return arr;
	}

如：生成随机的有序序列

	/**
	* 随机有序序列
	*/
	public static int[] orderRandArr(int maxLen,int maxVal){
	int[] arr=randArrs(maxLen,maxVal);
	Arrays.sort(arr);
	return arr;
	}

…

算法

# 1- 测试随机函数是等概率

# 2 - 由 random 到其他随机数

# 3 - 由 [1,5] 到 [1,7]

# 4 - RandomBox 到任意范围随机整数

# 5 - 对数器

服务器配置hexo开启https（ssl证书）

RabbitMQ入门（聊天室）-简单模式