2

ルームメイトが面接に行って、これを手に入れました：

ルール:

rand(); の使用が許可されています。

RAND_MAX = 32 767;

除算または剰余を使用しない。

TODO: 1 つの int パラメーターを取り、範囲 0 からパラメーターの int を返す関数を作成します。

頭が痛い、眠れない。どんな助けでも感謝します。ありがとう

4

5 に答える 5

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;
}

最悪の場合 (制限は 2 のべき乗 + 1)、これは生成された数値の 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これは、値 <= を他のすべてよりも 1 回以上カウントすることによって明らかにわずかにずれますがrand() % max、同じ問題があるため、このエラーは許容できると想定しています ( max<<MAX_RANDの値の場合、エラーは重要ではありません)。

于 2013-05-28T20:48:28.753 に答える