Учитывая функцию rand7 (), напишите функцию, которая равномерно rand10 ()

Question

Могу ли я найти эффективное решение для вышеуказанной проблемы .... Я попытался выяснить проблему с этого сайта http://www.ihas1337code.com/2010/11/rejection-sampling.html, но не смог найти причину idx = col + (row-1) *7;почему они умножаются на 7 ....

мы могли бы сделать это также (rand7 () * rand7 ())% 10 ... или умножить на любое другое число, потому что в конце мы должнысделать мод 10, который даст результаты только в течение 10 ...

почему они сделали решение таким трудным ... Пожалуйста, объясните и ваши мысли по этому поводу ...

И что делаетединообразно значит в вопросе?

Спасибо ..

Answer 1

(rand7() * rand7()) % 10

не подойдет, поскольку некоторые значения будут более вероятными, чем другие.

Давайте сравним вероятность получения 1 и 2:

Чтобы получить 1:

• rand7() * rand7() должно быть равно 1, 11, 21, 31 или 41.
• Это может быть достигнуто следующими способами: 1 * 1, 3 * 7 или 7 * 3.
• То есть 3 раза из 49 вы получите 1

Чтобы получить 2: ,

• rand7() * rand7() должно быть равно 2, 12, 22, 32 или 42.
• Это может быть достигнуто следующими способами: 1 * 2, 2 * 1, 3 * 4, 4 * 3, 2 * 6, 6 * 2, 6 * 7, 7 * 6.
• То есть 8 из 49 вы получите 2!

---

Их решение решает эту проблему, позволяя каждому числу (от 1 до 10) быть одинаково вероятным: каждое число встречается 4 раза в 49 возможных исходах (9 результатов отбрасываются и приводят к повторной выборке).

---

По сути, реализация Random.nextInt(int n) делает нечто подобное:

int bits, val;
do {
    bits = next(31);
    val = bits % n;
} while (bits - val + (n-1) < 0);    // re-sample until in range.
return val;

Это фактически использует rand2 для реализации randN.

Answer 2

Это базовое преобразование двузначного числа base-7 в число base-10. И именно так вы бы расширили это решение до

Обобщенная задача

Реализация функции randA() с использованием randB(), для B, A> 1.

Решение

1. Генерирует достаточно много (ceil(ln(A)/ln(B))) цифр base-B

2. Обеспечить равномерное распределение: если число> A*floor(pow(B,ceil(ln(A)/ln(B)))/A) отклонить его и продолжить с 1, в противном случае продолжить с 3

3. Основание преобразовать полученное число в основание-A, выбрать младшую цифру, которая будет результатом randA ()

JavaScript-пример

// This function returns a randN function. Usage 
// example rand7=randn(7); rand7(); rand7()
function randn(i) {
    return function () {return Math.floor(Math.random() * i);};
}

// Given a random generator for numbers 0..b-1 this
// function returns a random generator for numbers 0..a-1

function randA(b, randB, a) {
    var digits=Math.ceil(Math.log(a)/Math.log(b));
    var maxNum=a*Math.floor(Math.pow(b, digits)/a)-1;
    return function() {
        var s;
        var number;
        do {
            s="";

            // Step 1
            for ( var i=0; i<digits; i++ )
                s += randB();

            number=parseInt(s, b);

        } while (number>maxNum); // Step 2

        return number%a; // Step 3
    };
}
// generates a rand8() number generator
rand8=randA(2,randn(2),8);
// generates array containing random numbers 0..7
[rand8(), rand8(), rand8()] 

Answer 3

Равномерно означает, что каждый результат происходит одинаково часто. Если вы позвоните rand7() семь миллионов раз, вы получите каждый результат примерно миллион раз.

Но попробуйте подсчитать результаты (rand7() * rand7()) % 10. Вы будете удивлены, насколько чаще один из результатов сравнивается с другими.