2

室友去面试得到了这个：

规则：

允许使用 rand();

RAND_MAX = 32 767；

不使用除法或模数；

TODO： 编写一个函数，该函数接受一个 int 参数并返回 0 - 参数范围内的 int。

头疼，睡不着。任何帮助表示赞赏。谢谢

4

5 回答 5

4

几种可能：

  • 范围转置方法：int r = rand() * 0.00003051855095 * n;

  • “随机排序”方法：int r; do { r = random(); } while (r >= n);

  • BSD方法：uint32_t r = arc4random_uniform(n);

等等等等等等。

于 2013-05-28T20:45:37.650 回答
2

在我的公共领域randlib中，我没有浮点，没有除法，没有乘法，只是位掩码和拒绝采样，如下所示：

int ojr_rand(ojr_generator *g, int limit) {
    int v, m = limit - 1;

    m |= m >> 1;
    m |= m >> 2;
    m |= m >> 4;
    m |= m >> 8; // m is smallest ((power of 2) - 1) > limit

    do {
            v = m & NEXT16(g);  // 16-bit random number
    } while (v >= limit);
    return v;
}

在最坏的情况下（限制是二加一的幂），这可以拒绝接近 50% 的生成数字，但它仍然比大多数快速 RNG 的除法或浮动数学要快，并且在一般情况下要快得多。此外，与浮点数学或 mod 不同，它是精确的，这意味着如果您要求限制为 3，那么您得到的值 0、1 和 2 的概率完全相等，而不仅仅是近似相等。

于 2013-05-29T02:32:37.080 回答
2

如果允许 c++11，则会提供一个随机标头，这使得这变得微不足道：

#include <random>
#include <iostream>

int Roll(int Max)
{
    if(Max>32767)
        Max=32767;
    std::random_device generator;
    std::uniform_int_distribution<int> distribution(0,Max);
    return distribution(generator);   
}


int main()
{
    std::cout << Roll(10) << std::endl
              << Roll(10) << std::endl
              << Roll(999999) << std::endl;
}

更多详情请访问：http ://en.cppreference.com/w/cpp/numeric/random

这假定 RAND_MAX 是由您的问题而不是由 C 标准提供的，当然您可以使用提供的常量，有关详细信息，请参阅：http ://en.cppreference.com/w/cpp/numeric/random/RAND_MAX

于 2013-05-28T21:02:54.357 回答
1 
do { r = random();} while (r >= max_rand);

起初我认为乘以分数会起作用，但从数学的角度来看，这可能被认为是作弊。

于 2013-05-29T22:36:49.160 回答
-1 
int getRand(int max)
{
    int val = rand();

    while (val > max)
    {
        val -= max + 1;
    }

    return val;
}

这显然会通过计数值 <=RAND_MAX % max比其他所有值多一次但rand() % max有同样的问题而略有偏差，所以我认为这个错误是可以接受的（对于max<<MAX_RAND的值，错误是微不足道的）。

于 2013-05-28T20:48:28.753 回答