Erweitern Sie einen Zufallsbereich von 1-5 auf 1-7

Question

Geben Sie eine Funktion an, die eine zufällige ganze Zahl im Bereich von 1 bis 5 erzeugt. Schreiben Sie eine Funktion, die eine zufällige ganze Zahl im Bereich von 1 bis 7 erzeugt.

1. Was ist eine einfache Lösung?
2. Was ist eine effektive Lösung, um die Speichernutzung zu reduzieren oder mit einer langsameren CPU zu arbeiten?

Answer 1

Die richtige Antwort von Adam Rosenfield beruht auf folgender Prämisse:

• x \= 5^n (in seinem Fall: n \=2)
• n rand5-Aufrufe manipulieren, um eine Zahl zu erhalten y im Bereich [1, x]
• z \= ((int)(x / 7)) * 7
• wenn y > z, erneut versuchen. sonst return y % 7 + 1

Wenn n gleich 2 ist, gibt es 4 Möglichkeiten zum Wegwerfen: y = {22, 23, 24, 25}. Wenn n gleich 6 ist, gibt es nur 1 Wegwerfmöglichkeit: y = {15625}.

5^6 = 15625
7 * 2232 = 15624

Sie rufen rand5 weitere Male auf. Die Wahrscheinlichkeit, dass Sie einen wegwerfbaren Wert (oder eine Endlosschleife) erhalten, ist jedoch viel geringer. Wenn es einen Weg gibt, keinen möglichen Wegwerfwert für y zu erhalten, habe ich ihn noch nicht gefunden.

Answer 2

Hier ist meine Antwort:

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

Sie ist etwas komplizierter als andere, aber ich glaube, sie minimiert die Aufrufe von rand5. Wie bei anderen Lösungen besteht auch hier eine geringe Wahrscheinlichkeit, dass die Schleife sehr lange dauert.

Answer 3

Einfach und effizient:

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

(Inspiriert durch Was ist Ihr Lieblings-Cartoon für Programmierer? ).

Answer 4

Ich mag keine Bereiche, die bei 1 beginnen, also fange ich bei 0 an :-)

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 5

Solange nicht sieben Möglichkeiten zur Auswahl stehen, ziehen Sie eine weitere Zufallszahl, die die Anzahl der Möglichkeiten mit fünf multipliziert. In 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;
}