Java의 무작위 함수 변환 예에 대한 자세한 설명-java지도 시간-php.cn

이 글은 Java에서 무작위 함수의 변환을 주로 소개하는 java에 대한 관련 지식을 제공합니다. 글의 샘플 코드가 자세히 설명되어 있으므로 관심이 있으시면 읽어보실 수 있습니다. 자세히 알아보기

Java의 무작위 함수 변환 예에 대한 자세한 설명

solved questions

문제 1

Java에서 Math.random() 함수는 동일한 확률의 구간을 반환합니다. [0,1) 임의의 10진수입니다. 즉, x 의 경우 <code>[0,x)의 숫자가 나타날 확률은 x입니다. x < 1의 경우 [0,x)에 있는 숫자의 확률이 x^2로 조정됩니다. . 무엇을 해야 합니까? Math.random()函数是等概率返回区间[0,1)中的任意一个小数。即x < 1情况下，[0,x)中的数出现的的概率是x，如果我们要将x < 1情况下，[0,x)中的数出现的的概率调整成x^2，应该如何做？

问题1思路

由于[0,x)的概率是x，那么调用两次Math.random()，如果较大的那个值也要在[0,x)区间内，那么两次调用都必须在[0,x)区间内（因为任意一次在[x,1)都会导致返回值不在[0,x)上），即概率是x^2，代码如下

package snippet;

public class Code_0004_RandToPow2 {
    // 将`[0,x)`中的数出现的的概率调整成`x^2`
    public static double randToPow2() {
        return Math.max(Math.random(), Math.random());
    }
}

로그인 후 복사

我们可以通过如下测试代码来验证问题1的解法：

package snippet;

public class Code_0004_RandToPow2 {
    // 将`[0,x)`中的数出现的的概率调整成`x^2`
    public static double randToPow2() {
        return Math.max(Math.random(), Math.random());
    }

    // 测试用例
    public static void main(String[] args) {
        int count = 0;
        int testTimes = 10000000;
        double x = 0.17;
        for (int i = 0; i < testTimes; i++) {
            if (randToPow2() < x) {
                count++;
            }
        }
        System.out.println((double) count / (double) testTimes);
        System.out.println(Math.pow(x, 2));
    }
}

로그인 후 복사

打印的结果如下

0.0288603
0.028900000000000006

接近目标要求。

问题2

假设我们有一个随机函数f()，这个函数可以等概率返回[1,5]中的一个数，如何只利用f()函数而不引入其他随机函数，得到一个等概率返回[1,7]中任意一个数的函数g()。

思路

由于目标是求[1,7]等概率返回一个，如果我们能加工得到一个x()函数，这个函数是等概率返回[0,6]范围内的任意一个数，那么目标函数g()只需要调用这个x()函数再加上1，即是g()函数要求

public static int g() {
    return x() + 1;
}

로그인 후 복사

要得到[0,6]等概率返回一个数，我们需要先得到一个0和1等概率返回的随机函数m()，我们可以通过f()函数来得到，即

// 通过[0,5]等概率返回的随机函数f()
// 加工出等概率得到0和1
// 1,2,3,4,5 五个数
// 得到1，2的时候，返回0
// 得到4，5的时候，返回1
// 得到3的时候，弃而不用，再次尝试
    public static int m() {
        int ans = 0;
        do {
            ans = f();
        } while (ans == 3);
        return ans < 3 ? 0 : 1;
    }

로그인 후 복사

有了等概率返回 0 和 1 的随机函数 m()，我们可以很方便的生成[0,6]随机等概率返回一个数的方法，因为[0,6]需要三个二进制数表示，那么我们可以调用三次m()函数，可以等概率得到[0,7]范围内任意一个数，我们可以在得到 7 的时候，重试上述过程，只有结果在[0,6]才返回，这样就加工出了x()函数。

    // 等概率返回0~6
    public static int x() {
        int ans = 0;
        do {
            ans = (m() << 2) + (m() << 1) + m();
        } while (ans == 7);
        return ans;
    }

로그인 후 복사

最后，目标函数f()通过如下方式

    // 等概率返回1~7
    public static int g() {
        return x() + 1;
    }

로그인 후 복사

即可得到。完整代码如下

package snippet;

public class Code_0005_Rand5ToRand7 {

    // 此函数只能用，不能修改
    // 等概率返回1~5
    public static int f() {
        return (int) (Math.random() * 5) + 1;
    }

    // 通过[0,5]等概率返回的随机函数f()
// 加工出等概率得到0和1
// 1,2,3,4,5 五个数
// 得到1，2的时候，返回0
// 得到4，5的时候，返回1
// 得到3的时候，弃而不用，再次尝试
    public static int m() {
        int ans = 0;
        do {
            ans = f();
        } while (ans == 3);
        return ans < 3 ? 0 : 1;
    }

    // 等概率返回0~6
    public static int x() {
        int ans = 0;
        do {
            ans = (m() << 2) + (m() << 1) + m();
        } while (ans == 7);
        return ans;
    }

    // 等概率返回1~7
    public static int g() {
        return x() + 1;
    }

    
}

로그인 후 복사

问题3

和问题2思路一致，核心都是要先实现一个等概率返回 0 和 1 的随机函数m()。，然后看目标函数区间需要几个二进制位，来决定调用几次m()函数，不赘述，完整代码见

/**
 * The rand7() API is already defined in the parent class SolBase.
 * public int rand7();
 * @return a random integer in the range 1 to 7
 */
class Solution extends SolBase {
    public int rand10() {
        return rand(10);
    }

    public int rand(int N) {
        int bit = 1;
        int base = 2;
        while (base <= N) {
            base = 2 << bit;
            bit++;
        }
        int v = build(bit);
        while (v < 1 || v > N) {
            v = build(bit);
        }
        return v;
    }

    private int build(int bit) {
        int v = 0;
        for (int i = 0; i < bit; i++) {
            v += (m() << i);
        }
        return v;
    }

    // 核心：生成 0 和 1 等概率返回的随机函数
    public int m() {
        int i = rand7();
        while (i == 7) {
            i = rand7();
        }
        return (i == 1 || i == 2 || i == 3) ? 0 : 1;
    }
}

로그인 후 복사

问题4

有一个函数f()，不等概率（但是是固定概率）返回0和1，如何只通过f()函数，得到等概率返回 0 和 1 的随机函数g()，

思路，

调用两次f()函数，可以得到如下情况

0 0
1 1
0 1
1 0

当两次都是0，或者两次都是1的时候，舍弃，虽然 0 和 1 的概率不一样，但是

0 1
1 0

概率一定一样

所以得到 0 1就返回 0 ，得到 1 0就返回1，即g()

질문 1에 대한 아이디어

[0,x)의 확률이 x이므로 Math.random()을 두 번 호출하세요. 더 큰 값도 [0,x) 간격 내에 있어야 하므로 두 호출 모두 [0,x) 간격 내에 있어야 합니다(< code>[0,x) 간격 code>[x,1)로 인해 반환 값이 [0,x))에 있지 않게 됩니다. 확률은 x^2, 코드는 다음과 같습니다

package snippet;

// 不等概率随机函数变成等概率随机函数
public class Code_0005_EqualProbabilityRandom {

    // 不等概率函数，
    // 内部内容不可见
    public static int f() {
        return Math.random() < 0.8 ? 0 : 1;
    }

    // 等概率返回0和1
    public static int g() {
        int first;
        do {
            first = f(); // 0 1
        } while (first == f());
        return first;
    }

}

로그인 후 복사

다음 테스트 코드를 통해 질문 1의 답을 확인할 수 있습니다. rrreee인쇄된 결과는 다음과 같습니다🎜

🎜0.0288603
0.028900000000000006🎜

🎜목표 요구 사항에 근접했습니다. 🎜

질문 2

🎜 무작위 함수 f()가 있다고 가정해 보겠습니다. 이 함수는 [1,5]에 동일한 확률로 숫자를 반환할 수 있습니다. , 다른 임의의 함수를 도입하지 않고 f() 함수만 사용하는 방법과 [1,7]에서 임의의 숫자를 반환할 동일한 확률을 얻는 방법 code> 함수 <code>g(). 🎜🎜Idea🎜🎜[1,7]을 동일한 확률로 반환하는 것이 목표이므로 x() 함수를 처리할 수 있다면 이 함수는 동일한 확률로 반환됩니다. 확률 [0,6] 범위 내의 임의의 숫자인 경우 대상 함수 g()는 이 x() 함수만 호출하면 됩니다. 더하기 1, 즉 g() 함수는 🎜rrreee🎜에서 [0,6]를 가져와 동일한 확률로 숫자를 반환해야 합니다. 0과 1을 먼저 얻습니다. 동일한 확률을 반환하는 무작위 함수 m()은 f() 함수를 통해 얻을 수 있습니다. 즉, 🎜rrreee 🎜 0과 1을 반환할 확률은 같습니다. 무작위 함수 m()를 사용하면 동일한 확률로 숫자를 반환하는 [0,6] 메서드를 쉽게 생성할 수 있습니다. [0,6] 표현하려면 세 개의 이진수가 필요하기 때문에 m() 함수를 세 번 호출하면 다음 범위의 어떤 숫자든 얻을 수 있습니다. [0,7] 동일한 확률로 위의 프로세스를 7을 얻으면 다시 시도할 수 있으며, [0,6]일 때 결과만 반환되므로 다음을 처리합니다. x() 함수. 🎜rrreee🎜마지막으로 목적함수 f()는 다음과 같이 얻을 수 있습니다 🎜rrreee🎜. 전체 코드는 다음과 같습니다🎜rrreee

질문 3

🎜🎜아이디어는 질문 2와 동일합니다. 핵심은 먼저 m()이라는 무작위 함수를 구현하는 것입니다. 동일한 확률로 0과 1을 반환합니다. 그런 다음 m() 함수를 호출할 횟수를 결정하기 위해 대상 함수 간격에 필요한 바이너리 비트 수를 살펴봅니다. 전체 코드는 🎜rrreee

질문 4

를 참조하세요. 🎜동일한 확률(그러나 고정된 확률)로 0과 1을 반환하는 f() 함수가 있습니다. f() 함수를 통해서만 0과 1을 반환합니까? 1의 무작위 함수 g(), 🎜🎜idea, 🎜🎜는

f() 함수를 두 번 사용하면 다음 상황이 발생할 수 있습니다. 🎜<blockquote>🎜0 0<br>1 1<br>0 1<br>1 0🎜</blockquote>🎜두 번 모두 0인 경우 또는 두 번 모두 1이므로 0과 1의 확률은 다르지만 🎜 <blockquote>🎜0 1<br>1 0🎜</blockquote>🎜 확률은 동일해야 하므로🎜🎜 <code>0 1

, 0을 반환하고, 1 0을 얻으면 1을 반환합니다. g() 함수🎜🎜완전한 코드 🎜rrreee🎜추천 학습: "🎜java 비디오 튜토리얼🎜"🎜

위 내용은 Java의 무작위 함수 변환 예에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!