有关随机数的一些问题

导读

这里随机数问题介绍3个题目，可以算是一大类的吧。
话不多说，直接看题：

第一题：基础题目

思路：

用随机数1——5，来产生随机数1——7。
就要想办法通过已有的条件1——5，来凑！
首先要有个0出来，方便后面计算。rand1To5() - 1 ：可产生：0,1,2,3,4
这些范围比7小，还要连续的数字都要有，（4后面是5，所以乘以5）
那么rand1To5() * 5 可产生：0,5,10,15,20
这两个凑出来的相加，可产生：0,1,2,3,4,5,6,。。。,20,21,22,23,24。
这些范围已经大于7了，那么就将大于7的那部分，在重新随机下，保证产生在0——6之间的数即可，在加上个1，就是产生1——7。

代码：

	public static int rand1To5() {
   
		return (int)(Math.random()*5) + 1;
	}
	
	// 解法
	public static int rand1To7() {
   
		int num;
		do {
   
			num = (rand1To5() - 1) + ((rand1To5() - 1) * 5); 
		}while(num >= 7);
		return num + 1;
		
	}

检验正确性

	public static void main(String[] args) {
   
		// 检验基础题目
		int[] map = new int[8]; 	// 哈希表。 下标是对于产生的数字，相应的值是产生的次数。
		int times = 1000; 			//随机生成的次数
		int sum = 0;
		for(int i = 0; i < times; i++) {
   
			int num = rand1To7();
			map[num]++;
		}
		for(int i = 0; i < 8; i++) {
   
			System.out.println("出现数字" + i + "的次数 ： " + map[i]);
			sum += map[i];
		}
		System.out.println(sum); // 看看总的次数是不是和 随机生成的次数相等
	}

运行结果：

第二题：补充题目

思路：

题目中不是等概率产生的0，1。
但是！
调用2次，产生01，和产生10的概率是相等的，概率都是p*(1-p)。以此思想来等概率的产生 0 和 1。记为 rand01()
接着做法和基础题目差不多了，
rand01() 等概率产生0，1
则 rand01() * 2 等概率产生 0，2
以上相加，等概率产生 0，1，2，3
至此，还是没有产生到1——6，范围小了。还要连续的数字都要有，（3后面是4，所以乘以4）
则以上相加后的结果 * 4，即(0,1,2,3)*4，等概率产生 0，4，8，12
2组的（0,1,2,3）和 (0,4,8,12) 相加，
等概率产生 0,1,2,3,4,5,6,。。。,12,13,14,15
在6之后的重复此步骤，保证随机产生0——5,
结果加1，就等概率产生了1——6.

代码：

	public static int rand01p() {
   
		double p = 0.83;
		return Math.random() < p ? 0 : 1;
	}
	
	// 解法：
	// 先等概率产生0和1
	public static int rand01() {
   
		int num;
		do {
   
			num = rand01p();
		}while(num == rand01p()); // 这2此调用，一次0，一次1，不相等，就跳出while循环。 相应的，产生的0或1是等概率的
		return num;
	}
	// 等概率产生0到3
	public static int rand0To3() {
   
		return rand01() * 2 + rand01();
	}
	// 等概率产生1到6
	public static int rand1To6() {
   
		int num;
		do {
   
			num = rand0To3() * 4 + rand0To3();
		}while(num >= 6);	// 产生0——5
		return num + 1;
	}

检验正确性：

	public static void main(String[] args){
   
		// 检验补充题目
		int[] map = new int[7]; 	// 哈希表。 下标是对于产生的数字，相应的值是产生的次数。
		int times = 500; 			//随机生成的次数
		int sum = 0;
		for(int i = 0; i < times; i++) {
   
			int num = rand1To6();
			map[num]++;
		}
		for(int i = 0; i < 7; i++) {
   
			System.out.println("出现数字" + i + "的次数 ： " + map[i]);
			sum += map[i];
		}
		System.out.println(sum); // 看看总的次数是不是和 随机生成的次数相等
	}

运行结果：

第三题：进阶题目

思路：

用等概率产生1——M，来等概率产生1——N。
这说明可以用任意的等概率随机数,来产生另外的任意的等概率随机数。

先说下对这道题的宏观看法，宏观思想：
首先，如果M >= N 的话，直接进行前面的题的最后步骤，超出范围内的话，在重复随机产生步骤，保证产生的数在范围内。很简单。
最后，如果M < N 的话，我们还要用1——M这个函数，来随机产生比N范围大的数，不管怎么凑,只要比N范围大就行。接着就是上面的那种情况了

好了，再来看看微观的解法：（怎么用代码实现）
已有的是随机产生1——M，我们可以拿到这些数字，那么把N这个数字用M进制来表示，其范围也仍是 0——M-1。
在随机产生1——N范围的数字，用M进制表示，因为我们能控制的是1——M的随机数，用M进制要方便很多。
最后把产生的在范围内的 M进制数字转化为十进制数字即可。

	public static int rand1ToM(int m) {
   
		return (int)(Math.random() * m + 1);
	}
	
	// 解法：
	// 将N 转成 M进制的数字，方便后续操作
	public static int[] getNnumByMsys(int m, int n) {
   
		int[] res = new int[32];	//这里认为 一个整数 的位数 最多有 32位。
		int index = res.length - 1;
		while(n != 0) {
   
			res[index--] = n % m;
			n = n / m;
		}
		return res;
	}
	
	// 生成 用M进制表示的 0——N的随机数，
	public static int[] getRandNumByMsys(int m, int[] nByMsys) {
   
		int[] res = new int[nByMsys.length];
		int start = 0;		// 记录着 第一个不为0的数字的下标位置
		while(nByMsys[start] == 0) {
   
			start++;
		}
		int index = start;
		boolean lastEqual = true; 	// 比较后面的数字 有没有必要 接着和 N 的M进制的数字 来比较
		while(index != nByMsys.length) {
   
			res[index] = rand1ToM(m) - 1;
			if(lastEqual) {
   
				if(res[index] > nByMsys[index]) {
     // 第一位数字，不能比 N 的数字要大， 否则就超出了1——N的范围了。
					// 一旦是要大于的，不管在那个步骤，都要重新来，从头来（即从start位置开始） 产生， 全部恢复初始状态位置。
					// 否则的话，只有continue。 后面产生2位数字的话，最后几位数（比较接近末尾的，比较大的数）产生的概率要明显比前面的数的概率要大。
					// 因为没有恢复初始状态，而只是在index位置继续随机产生，前面start位置的数字是相等的，所以概率对应的也要大一些。
					// 可以试试 只有continue的情况， N的取值>=10。 就能看出情况了。
					index = start;	
					lastEqual = true;
					continue;
				}else {
   
					// 第一位数字相等还要比较后面的数字，如果产生的比 N 的相应数字要小，则后面的数随便产生了（当然是M进制内的数字）。
					lastEqual = res[index] == nByMsys[index];  
				}
			}
			index++;
		}
		return res;
	}
	
	// 将生成的 M进制的随机数 转换成 十进制的数字
	public static int getNnumFromMsys(int m, int[] nByMsys) {
   
		int res = 0;
		int index = 0;
		while(index < nByMsys.length) {
   
			res = res * m + nByMsys[index++]; 	// 秦九韶算法。 就是把那些公因子 一步一步的提出来了。
		}
		return res;
	}
	
	// 随机产生 1——N
	public static int rand1ToN(int m, int n) {
   
		int[] nByMsys = getNnumByMsys(m, n);
		int res = 0;
		while(res == 0) {
   	// 函数内部实现的是0——N，我们没有要0。
			int[] nRandByMsys = getRandNumByMsys(m, nByMsys);
			res = getNnumFromMsys(m, nRandByMsys);
		}
		return res;
	}

-检验正确性

	public static void main(String[] args){
   
		// 检验进阶题目
		int m = 3;
		int n = 20;
		int times = 10000;
		int[] map = new int[n+1];
		for(int i = 0; i < times; i++) {
   
			int num = rand1ToN(m, n);
			map[num]++;
		}
		int sum = 0;
		for(int i = 0; i < n+1; i++) {
   
			System.out.println( i + " : " + map[i]);
			sum += map[i];
		}
		System.out.println("sum : " + sum);
	}