从5随机到7随机及其扩展

基本题目

题目

给定一个等概率随机产生1~5的随机函数rand1To5如下：
public int rand1To5() {
return (int) (Math.random() * 5) + 1;
}
除此之外不能使用任何额外的随机机制，请用rand1To5实现等概率随机产生1~7的随机函数rand1To7。

思路

插空和筛选

  • 插空
    5 * (rand1To5-1) -> 等概率随机产生1~20

5 (rand1To5-1) + (rand1To5-1) -> 等概率随机产生0~24 ,
5 (rand1To5-1)和 rand1To5-1是两个独立的函数

( 5 * (rand1To5-1) + (rand1To5-1) )% 7 不等随机产生 0~6，
产生3,2,1,0的概率更高，因为0~20等概率产生0~6，21~24又产生了0~3

这里乘以5的原因是，rand1To5产生5个数

  • 筛选
    由于0~3多产生了，因此不等概率，需要筛选
    过程就是产生了大于20的数字，重新产生，这样，产生的每个数字都是0~20

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>
#include<stdlib.h>
int rand1To5() {
	//rand()%5，random0-4
	//rand()%5 + 1，random1-5 
	return  rand()%5 + 1;
}
int rand1To7(){
	int num;
	do{
		num = 5*(rand1To5()-1)+rand1To5()-1;
	}while(num>20);//´óÓÚ20ɸѡ 
	return num%7+1;
}
int main(){
	for(int i=0;i<200;i++){
		int k =rand1To7();
		printf("%d\n",k);
	}
	return 0;
}

补充题目

给定一个以p概率产生0，以1-p概率产生1的随机函数rand01p如下：
public int rand01p() {
// you can change p as you like
double p = 0.83;
return Math.random() < p ? 0 : 1;
}

除此之外不能使用任何额外的随机机制，请用rand01p实现等概率随机产生1~6的随机函数rand1To6。

思路

由于产生0和1概率不等，但是产生(0,1)和(1,0)组合的概率相等，可以把这个看做是0和1
然后题目就变成了用0-1产生1-6，仍然是插空和筛选

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<stdio.h>
#include<stdlib.h>
int rand01p() {
	// you can change p as you like
	double p = 0.83;
	return rand()%2 < p ? 0 : 1;
}
int rand01(){
	//rand 0,1
	while(1){
		int a=rand01p();
		int b=rand01p();
		if(a==1 && b==0){
			return 1;
		}else if(a==0 && b==1
			){
			return 0;
		}
	}
	
}
int rand0To3(){
	return rand01()*2+rand01();
}
int rand1To6(){
	int a;
	do{
		a = 4*rand0To3() + rand0To3();
		
	}while(a>11);
	return a%6+1;
}
int main(){
	//int a = rand1ToN(10);
	for(int i=0;i<10;i++){
		int ans = rand1To6();
		printf("%d\n",ans);
	}
	
}

这里是先产生0-3，再产生1-6
但是按照进制的方法不知道这样子是否可以
rand01()*2 *2 + rand01()*2 + rand01() —> 产生0-7，然后再进行筛选

1
2
3
4
5
6
7
8
9
10
11
12
//用01产生1-n的任何数，没看懂
int rand1ToN(int n){
	int ans = 0;
	do{
		for(int i=0;n;n >>= 1,i++){
			if(rand01() == 1){
				ans = (1<<i);
			}
		}
	}while(ans >= n);
	return ans +1;
}

进阶题目

题目

给定一个等概率随机产生1~M的随机函数rand1ToM如下：
public int rand1ToM(int m) {
return (int) (Math.random() * m) + 1;
}
除此之外不能使用任何额外的随机机制。有两个输入参数分别为m和n，请用rand1ToM(m)实现等概率随机产生1~n的随机函数rand1ToN。

思路

把随机产生先化成0~m-1，然后看做是m进制的数字，看n最多能占几位，然后筛选
比如，从5产生7，由于1位5进制只能表示0-4，而2位5进制能表示0-24

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public int rand1ToM(int m) {
	return (int) (Math.random() * m) + 1;
}
public int rand1ToN(int n, int m) {
	int[] nMSys = getMSysNum(n - 1, m);
	int[] randNum = getRanMSysNumLessN(nMSys, m);
	return getNumFromMSysNum(randNum, m) + 1;
}
// 把value转成m进制的数
public int[] getMSysNum(int value, int m) {
	int[] res = new int[32];
	int index = res.length - 1;
	while (value != 0) {
		res[index--] = value % m;
		value = value / m;
	}
	return res;
}
// 等概率随机产生一个0~nMsys范围上的数，只不过是m进制表达的。
//没看懂！！
public int[] getRanMSysNumLessN(int[] nMSys, int m) {
	//创造一个新数，和n-1的位数相等
	int[] res = new int[nMSys.length];
	//下面应该是构造新数的过程
	int start = 0;
	while (nMSys[start] == 0) {
		start++;
	}
	int index = start;
	//应该最后创造的数不能比n-1大的标志
	boolean lastEqual = true;
	while (index != nMSys.length) {
		res[index] = rand1ToM(m) - 1;
		if (lastEqual) {
			if (res[index] > nMSys[index]) {
				index = start;
				lastEqual = true;
				continue;
			} else {
				lastEqual = res[index] == nMSys[index];
			}
		}
		index++;
	}
	return res;
}
// 把m进制的数转成10进制
public int getNumFromMSysNum(int[] mSysNum, int m) {
	int res = 0;
	for (int i = 0; i != mSysNum.length; i++) {
		res = res * m + mSysNum[i];
	}
	return res;
}