随机数生成用于验证算法正确性
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
| import java.util.Arrays;
import com.day1.sort.insertionSort;
public class ArrayComparator {
public static void comparator(int[] arr) {
Arrays.sort(arr);
}
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
public static boolean isEqual(int[] arr1, int[] arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
return false;
}
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 20;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
insertionSort.insertionSort(arr1);
comparator(arr2);
if (!isEqual(arr1, arr2)) {
succeed = false;
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
int[] arr = generateRandomArray(maxSize, maxValue);
printArray(arr);
insertionSort.insertionSort(arr);
printArray(arr);
}
}
|
不等概率变成等概率
f()函数是生成0和1的函数，但是概率不相等，要求使用 f()函数生成一个 g()函数，g()函数生成0和1的概率相等.
算法思路：将 f()函数执行两次，得到00和11都不要，重新生成，得到01返回0，得到10返回1
1
2
3
4
5
6
7
8
9
10
11
12
13
| public class Random0_neq_1to0_eq_1 {
public static int f(){
return Math . random ()<0.84 ? 0:1;
}
public static int g(){
int ans =0; do {
ans = f ();
} while ( ans == f ());
return ans ;
}
}
|
函数置换
得到1到5随机数的函数fn()如何置换成获得1到7随机数的函数g(x)
一、从1到5随机数得到1到7随机数
题设: 给定一个函数fn(), fn()会等概率得到15的随机数(整数)
要求: 可以使用fn()但是不能更改fn(), 最终要等概率得到17的随机数(整数)
解:
1.先构造出01发生器
fn()会随机得到1~5， 那么定义如果得到1和2就返回0，得到4和5就返回1，得到3就重试，一直循环知道能得到2，4，5中的某一个数终止。
假设01发生器函数为 f2();
2.找到最终得到的最大数，用二进制形式表示出来
最终需要得到1~7， 7为最大数，用二进制表示就是 000 ~ 111。总共有3位，每一位的值都是0或1。
3.使用01发生器等概率得到000~111之间的数
int result = (f2()<<2) + (f2()<<1) + f2();
4.最终需要1~7，所以如果result=0则重试，直到结果为1到7终止，这样就能得到1到7的等概率随机数了。
二、推广到一般情况 根据a到b随机得到c到d随机数
根据上面1到5随机数得到1到7的随机数可得
1.先构造出01发生器
fn()会随机得到a~b
(1) 如果b-a+1是偶数，则得到左边一半的数即a到((a+b+1)/2)-1就返回0，得到右边一半即((a+b+1)/2)到b就返回1。
(2) 如果b-a+1是奇数，则得到左边一半a到((a+b)/2-1)就返回0，得到右边一半即((a+b)/2+1)到b就返回1，得到(a+b)/2就重试。
假设01发生器函数为 f2();
2.找到最终得到的最大数，用二进制形式表示出来
假设c=13,d=59
最终需要得到c~d， d为最大数，则用二进制表示就是 000000 ~ 111111(0到63)。总共有6位，每一位的值都是0或1。
3.使用01发生器等概率得到000000~111111之间的数
int result = (f2()<<6) + (f2()<<5) + (f2()<<4) + (f2()<<3) + (f2()<<2) + f2();
4.最终需要c~d，所以我们得到0到(d-c)的随机数在+c即可得到c到d的随机数
即如果result>d-c则重试，直到结果为0到d-c终止，这样就能得到0到d-c的等概率随机数了然后再加上c即可。
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
56
57
58
59
60
61
| public class Random1_5to1_7 {
public static void main(String[] args) {
int times = 10000000;
int[] count = new int[8];
for (int i = 0; i < times; i++) {
int num = g();
count[num]++;
}
for (int i = 0; i < count.length; i++) {
System.out.println("得到" + i + "的次数:" + count[i]);
}
}
private static int fn() {
return (int) (Math.random() * 5) + 1;
}
private static int f2() {
int result = 0;
do {
result = fn();
} while (result == 3);
return result < 3 ? 0 : 1;
}
private static int f3() {
return (f2() << 2) + (f2() << 1) + f2();
}
private static int g() {
int result = 0;
do {
result = f3();
} while (result == 0);
return result;
}
}
|