Лучшее решение для моего подхода к созданию процедуры Rand(a,b) с использованием процедуры Rand(0,1)

Я читал CLRS и столкнулся с проблемой написания процедуры Rand(a,b), которая генерирует случайное число между a и b равномерно случайным образом, используя процедуру Rand(0,1), которая генерирует 0 или 1 с вероятностью 50%.,

Я подумал о следующем решении, которое O(b) во времени:

int Rand_a_b(int a,int b)
{
    int i,k=0;
    for(i=0;i<b-a;i++)
    {
         k+=Rand(0,1);
    }
    return a+k;
}

Пожалуйста, предложите лучший подход к этому.

Источник

3 ответа

Решение

Если число различных чисел в диапазоне не является степенью двойки, вы должны быть осторожны, потому что любая процедура, которая всегда принимает N чисел, видит только 2^N разных возможностей, и распределить 2^N по-разному невозможно возможности равномерно в диапазоне, если диапазон не имеет степени двух разных возможностей.

Один из подходов при генерации чисел между a..b заключается в использовании k случайных чисел в качестве отдельных битов в k-битном числе для получения числа в диапазоне a..a+2^k-1, где k выбрано так, чтобы a+2^k-1 >= b. Если окажется, что сгенерированное вами случайное число выходит за пределы допустимого диапазона, начните снова с нуля. Это уклоняется от проблемы выше, беря переменное количество случайных битов, в зависимости от того, как часто вы генерируете что-то вне диапазона и должны ли начинать заново.

Источник

Что здесь должно сделать это в log (n). (Я не проверял границы, это не проверялось!) Вы не можете сделать это быстрее, чем это - если вы излучаете только один бит за раз, вам нужно как минимум log(ba) раундов за интервал.

function Rand_a_b(int a, int b) {
   if (a == b) return a;
   int middle = (b-a)/2;
   if (Rand(0,1)) {
      return Rand_a_b(middle + 1, b);
   } else {
      return Rand_a_b(a, middle);
   }
}
Источник

Вот алгоритм: рассчитать разницу между a и b: k = abs(a-b) и начать делать бинарный поиск так:

сохранить номер n = 0.флип свою монету - Rand(0,1), если результат 1 добавить k/2 на ваш n иначе ничего не добавлю. чем перевернуть это снова для k/4 и повторять до k/i это 0.

Источник
Другие вопросы по тегам