隨機(jī)函數(shù)是平時刷題練習(xí)時驗證正確性的比較靈魂的方法。
java中提供了Math.random()函數(shù)：返回一個[0~1)等概率的一個double類型的值。
1、驗證代碼
package com.yubin.algorithms;
/**
* 介紹隨機(jī)函數(shù)的使用
* @author YUBIN
* @create 2021-03-13
*/
public class Code0007_RandToRand {
public static void main(String[] args) {
// 驗證Math.random()函數(shù)[0,1)是等概率的
int testTimes = 10000000;
int count = 0;
for (int i = 0; i < testTimes; i++) {
if (Math.random() < 0.75) { // 其概率應(yīng)該約等于0.75
count++;
}
}
System.out.println((double)count / (double)testTimes);
System.out.println("===========================");
// [0,1)*8 => [0,8)
count = 0;
for (int i = 0; i < testTimes; i++) {
if (Math.random() * 8 < 5) { // 其概率應(yīng)該約等于 5/8=0.625
count++;
}
}
System.out.println((double)count / (double)testTimes);
System.out.println("===========================");
int k = 9;
// [0,k) 相當(dāng)于 [0,l-1]
int[] counts = new int[k];
for (int i = 0; i < testTimes; i++) {
int ans = (int) (Math.random() * k);
counts[ans]++;
}
for (int i = 0; i < k; i++) {
System.out.println(i + "這個數(shù),出現(xiàn)了" + counts[i] + "次");
}
System.out.println("===========================");
}
}
2、題目一：如何利用Math.random()函數(shù)，把得到[0,x)范圍上的數(shù)的概率從x調(diào)整成x2
題目分析：經(jīng)過上面的驗證Math.random()隨機(jī)函數(shù)[0,1)范圍上概率是相等的，對應(yīng)的0 ~ x范圍的概率就是x，那么如何讓0 ~ x的概率變成x2呢？
利用Math.max(Math.random(), Math.random())
Math.max(a1,a2); 只有當(dāng)a1和a2兩個值都在0 ~ x范圍內(nèi)的時候值才會在0 ~ x范圍內(nèi)，這樣[0,x)的概率就變成x2了。
private static double xToPower2() {
return Math.max(Math.random(), Math.random());
}
注意：如果這里改成Math.min()函數(shù)的話，概率就變成 1-(1-x)2
3、題目二：從1 ~ 5隨機(jī)到1 ~ 7隨機(jī)
題目分析：程序中已提供一種1 ~ 5的隨機(jī)是等概率的方法，如何利用該函數(shù)實現(xiàn)1 ~ 7的隨機(jī)是等概率的。
其實這個題目有一個限制就是1~7的等概率隨機(jī)數(shù)不能使用 (int)(Math.random()*7)+1的方式，只能使用現(xiàn)成的方法。
思路：
已知函數(shù)是等概率返回[1,5]的整數(shù)
那么1,2,3,4,5的概率分別是20%， 如果我使用1和2 表示0; 4和5表示1 當(dāng)遇到3的時候再次隨機(jī)即將得到3的概率分?jǐn)偟狡渌?個數(shù)上面,此時得到1、2、4、5的概率都是25%，因此得到0的概率就是50%，得到1的概率也是50%。
通過[1,5]等概率函數(shù)可以得到一個0,1等概率函數(shù)，然后再利用二進(jìn)制的方式可以拿到一個0 ~ 7的等概率函數(shù)
000,001,010,011,100,101,110,111。 因為7這個數(shù)至少需要3位來表示。
代碼實現(xiàn)：
/**
* 返回[1,5]的等概率隨機(jī)數(shù)
* 假設(shè)該方法是lib里面,不能修改
* @return
*/
private static int f1() {
return (int) (Math.random() * 5) + 1;
}
/**
* 隨機(jī)機(jī)制,等概率返回0和1 只能使用f1函數(shù)
* 分析 f1函數(shù)是等概率返回[1,5]的整數(shù)
* 那么1,2,3,4,5的概率分別是20%， 如果我使用1和2 表示0; 4和5表示1 當(dāng)遇到3的時候再次隨機(jī)即將得到3的概率分?jǐn)偟狡渌?個數(shù)上面,
* 此時得到1、2、4、5的概率都是25%，因此得到0的概率就是50%，得到1的概率也是50%
*
* @return
*/
private static int f2() {
int ans = 0;
do {
ans = f1();
} while (ans == 3);
return ans < 3 ? 0 : 1;
}
// 得到000 ~ 111 做到等概率 0 ~ 7等概率返回一個 每一個數(shù)的概率是1/8
private static int f3() {
return (f2() << 2) + (f2() << 1) + (f2() << 0);
}
// 0 ~ 6等概率返回一個
private static int f4() {
int ans = 0;
do {
ans = f3();
} while (ans == 7);
return ans;
}
// 1 ~ 7等概率返回一個
private static int g() {
return f4() + 1;
}
同理：從a ~ b隨機(jī)到c ~ d隨機(jī)這個題目也可以使用上面這個方法來實現(xiàn)。
將a ~ b變成01等概率發(fā)生器 ，將c ~ d變成0 ~ (d-c) 這時再看d-c需要幾個二進(jìn)制位, 同時如果超過d-c部分的重做即可
4、題目三：01不等概率隨機(jī)到01等概率隨機(jī)
分析：01不等概論，但是可以知道0和1是固定概率的，這樣的話我們使用兩位來表示
00，01，10，11
這每個數(shù)出現(xiàn)的概率都是第一位的概率 * 第二位的概率， 而已知的函數(shù)0和1雖然概率不一樣但是0的概率*1的概率是一樣的，這樣01,10就是等概率的了， 使用01表示0，10表示1，其它情況重做即可，這樣最后就能得到一個01的等概率隨機(jī)。
代碼實現(xiàn)：
// 已知的01不等概論函數(shù)，但是0和1的概率是固定的
private static int x() {
return Math.random() > 0.84 ? 0 : 1;
}
// 通過x函數(shù)得到01的等概率隨機(jī)
private static int y() {
int ans = 0;
do {
// 第一次調(diào)用x函數(shù)
ans = x();
} while (ans == x()); // 第二次調(diào)用x函數(shù) 兩次返回的結(jié)果不一樣則說明要么是01 要么是10
return ans;
}
