导读
这里随机数问题介绍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);
}
运行结果：
呼~ 终于写完了。。。
啰嗦一句：
特别是 第三题的代码里的注释要好好看一下，可能写的不是很清楚，但是自己手写一遍，带几个数字进去，跟着代码走一遍，应该也很清楚了。。。
京公网安备 11010502036488号