objective-c – 如何使用错误的生成器获取随机数

前端之家收集整理的这篇文章主要介绍了objective-c – 如何使用错误的生成器获取随机数前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
问题:假设您有一个随机生成器randn(),它返回0到n-1之间的均匀分布的随机数.给定任意数m,写一个随机生成器,返回0到m-1之间的均匀分布的随机数.

我的答案:

-(int)randm() {
    int k=1;
    while (k*n < m) {
        ++k;
    }
    int x = 0;
    for (int i=0; i<k; ++i) {
        x += randn();
    }
    if (x < m) {
        return x;
    } else {
        return randm();
    }
}

它是否正确?

解决方法

你很接近,但你的答案的问题是,有一种方法可以将一个数字写成另外两个数字的总和.

如果m 方法可以将数字写成另外两个数字的总和.例如,只有一种方法可以获得0但是有很多方法可以获得m="" 2,因此概率不会相等.="" 示例:n="2且m" =="" 3="" <="">

0 = 0+0
1 = 1+0 or 0+1
2 = 1+1

所以你方法的概率分布是

P(0)=1/4
P(1)=1/2
P(2)=1/4

哪个不统一.

解决此问题,您可以使用唯一分解.在基数n中写m,跟踪所需的最大指数,例如e.然后,找到小于n ^ e的m的最大倍数,称之为k.最后,用randn()生成e数,将它们作为某个数x的基数n展开,如果x <1. k * m,返回x,否则再试一次. 假设m

int randm() {

    // find largest power of n needed to write m in base n
    int e=0;
    while (m > n^e) {
        ++e;
    }

    // find largest multiple of m less than n^e
    int k=1;
    while (k*m < n^2) {
        ++k
    }
    --k; // we went one too far

    while (1) {
        // generate a random number in base n
        int x = 0;
        for (int i=0; i<e; ++i) {
            x = x*n + randn(); 
        }
        // if x isn't too large,return it x modulo m
        if (x < m*k) 
            return (x % m);
    }
}
原文链接:https://www.f2er.com/c/117552.html

猜你在找的C&C++相关文章