Расширить случайный диапазон от 1–5 до 1–7

Question

Учитывая функцию, которая производит случайное целое число в диапазоне от 1 до 5, напишите функцию, которая производит случайное целое число в диапазоне от 1 до 7.

1. Что такое простое решение?
2. Каково эффективное решение для уменьшения использования памяти или работы на более медленном процессоре?

Answer 1

Здесь разрешены проблемы с домашними заданиями?

Эта функция выполняет грубую математику «основание 5» для генерации числа от 0 до 6.

function rnd7() {
    do {
        r1 = rnd5() - 1;
        do {
            r2=rnd5() - 1;
        } while (r2 > 1);
        result = r2 * 5 + r1;
    } while (result > 6);
    return result + 1;
}

Answer 2

Вот рабочая реализация Python Ответ Адама .

import random

def rand5():
    return random.randint(1, 5)

def rand7():
    while True:
        r = 5 * (rand5() - 1) + rand5()
        #r is now uniformly random between 1 and 25
        if (r <= 21):
            break
    #result is now uniformly random between 1 and 7
    return r % 7 + 1

Мне нравится бросать алгоритмы, которые я рассматриваю, в Python, чтобы я мог поиграть с ними, подумал, что я опубликую это здесь в надежде, что это кому-то пригодится, а не то, что это заняло много времени .

Answer 3

Почему бы не сделать это просто?

int random7() {
  return random5() + (random5() % 3);
}

Вероятность получения 1 и 7 в этом решении ниже по модулю, однако, если вам просто нужно быстрое и удобочитаемое решение, это путь.

Answer 4

int rand7() {
    int value = rand5()
              + rand5() * 2
              + rand5() * 3
              + rand5() * 4
              + rand5() * 5
              + rand5() * 6;
    return value%7;
}

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

Обратите внимание, что этот генератор не идеален (число 0 имеет на 0,0064% больше шансов, чем любое другое число), но для большинства практических целей гарантия постоянного времени, вероятно, перевешивает эту неточность.

Объяснение

Это решение получено из того факта, что число 15 624 делится на 7, и, таким образом, если мы можем случайным образом и равномерно генерировать числа от 0 до 15 624, а затем взять мод 7, мы можем получить почти равномерный генератор rand7. Числа от 0 до 15 624 можно сгенерировать равномерно, выполнив rand5 6 раз и используя их для формирования цифр базового числа 5 следующим образом:

rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5

Свойства мода 7, однако, позволяют немного упростить уравнение:

5^5 = 3 mod 7
5^4 = 2 mod 7
5^3 = 6 mod 7
5^2 = 4 mod 7
5^1 = 5 mod 7

So

rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5

становится

rand5 * 3 + rand5 * 2 + rand5 * 6 + rand5 * 4 + rand5 * 5 + rand5

Теория

Число 15 624 не было выбрано случайно, но его можно обнаружить с помощью маленькой теоремы Ферма, которая гласит, что если p - простое число, то

a^(p-1) = 1 mod p

Так что это дает нам,

(5^6)-1 = 0 mod 7

(5 ^ 6) -1 равно

4 * 5^5 + 4 * 5^4 + 4 * 5^3 + 4 * 5^2 + 4 * 5 + 4

Это число в форме основания 5, и поэтому мы можем видеть, что этот метод можно использовать для перехода от любого генератора случайных чисел к любому другому генератору случайных чисел. Хотя при использовании показателя степени p-1 всегда вводится небольшое смещение в сторону 0.

Answer 5

Предпосылка правильного ответа Адама Розенфилда:

• x = 5 ^ n (в его случае: n = 2)
• манипулирует n вызовами rand5, чтобы получить номер y в диапазоне [1, x]
• z = ((int) (x / 7)) * 7
• если y> z, попробуйте еще раз. еще вернуть y% 7 + 1

Когда n равно 2, у вас есть 4 возможности выбрасывания: y = {22, 23, 24, 25}. Если вы используете n равное 6, у вас есть только 1 выбрасывание: y = {15625}.

5 ^ 6 = 15625
7 * 2232 = 15624

Вы звоните rand5 еще раз. Однако у вас гораздо меньше шансов получить одноразовое значение (или бесконечный цикл). Если есть способ получить возможное выбрасываемое значение для y, я еще не нашел его.

Answer 6

Предполагая, что rand (n) здесь означает «случайное целое число в равномерном распределении от 0 до n-1 », вот пример кода с использованием Python randint, который имеет такой эффект. Для получения эффекта randint (7) используются только randint (5) и константы. Немного глупо, на самом деле

from random import randint
sum = 7
while sum >= 7:
    first = randint(0,5)   
    toadd = 9999
    while toadd>1:
        toadd = randint(0,5)
    if toadd:
        sum = first+5
    else:
        sum = first

assert 7>sum>=0 
print sum

Answer 7

Вот мой ответ:

static struct rand_buffer {
  unsigned v, count;
} buf2, buf3;

void push (struct rand_buffer *buf, unsigned n, unsigned v)
{
  buf->v = buf->v * n + v;
  ++buf->count;
}

#define PUSH(n, v)  push (&buf##n, n, v)

int rand16 (void)
{
  int v = buf2.v & 0xf;
  buf2.v >>= 4;
  buf2.count -= 4;
  return v;
}

int rand9 (void)
{
  int v = buf3.v % 9;
  buf3.v /= 9;
  buf3.count -= 2;
  return v;
}

int rand7 (void)
{
  if (buf3.count >= 2) {
    int v = rand9 ();

    if (v < 7)
      return v % 7 + 1;

    PUSH (2, v - 7);
  }

  for (;;) {
    if (buf2.count >= 4) {
      int v = rand16 ();

      if (v < 14) {
        PUSH (2, v / 7);
        return v % 7 + 1;
      }

      PUSH (2, v - 14);
    }

    // Get a number between 0 & 25
    int v = 5 * (rand5 () - 1) + rand5 () - 1;

    if (v < 21) {
      PUSH (3, v / 7);
      return v % 7 + 1;
    }

    v -= 21;
    PUSH (2, v & 1);
    PUSH (2, v >> 1);
  }
}

Это немного сложнее, чем другие, но я считаю, что это минимизирует количество вызовов rand5. Как и в случае других решений, существует небольшая вероятность того, что он может зацикливаться в течение длительного времени.

Answer 8

Просто и эффективно:

int rand7 ( void )
{
    return 4; // this number has been calculated using
              // rand5() and is in the range 1..7
}

(По мотивам Какой ваш любимый мультфильм "программист"? ).

Answer 9

Мне не нравятся диапазоны, начинающиеся с 1, поэтому я начну с 0: -)

unsigned rand5()
{
    return rand() % 5;
}

unsigned rand7()
{
    int r;

    do
    {
        r =         rand5();
        r = r * 5 + rand5();
        r = r * 5 + rand5();
        r = r * 5 + rand5();
        r = r * 5 + rand5();
        r = r * 5 + rand5();
    } while (r > 15623);

    return r / 2232;
}

Answer 10

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

$num = 0;
$possibilities = 1;

sub rand7
{
  while( $possibilities < 7 )
  {
    $num = $num * 5 + int(rand(5));
    $possibilities *= 5;
  }
  my $result = $num % 7;
  $num = int( $num / 7 );
  $possibilities /= 7;
  return $result;
}