Wie generiere ich Zufallszahlen, die zufällig "genug" sind?

Question

Ich versuche, das 280th Problem in Project Euler zu lösen, und dafür habe ich die folgende Simulation geschrieben;

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#include <sys/time.h> 

/* Directions 

    1 
2  3 
    4 
*/ 

int grid[5][5] = { 
    {0, 0, 0, 0, 2}, 
    {0, 0, 0, 0, 2}, 
    {0, 0, 0, 0, 2}, 
    {0, 0, 0, 0, 2}, 
    {0, 0, 0, 0, 2} 
}; 

int InitPos[2] = {2, 2}; 

int MaxExp = 5000000; 

bool Success = false; 
int StepCount = 0; 
int ExpNumber = 1; 
int AntsBag = 0; 
void Init(); 
void CarryFood(int * pos); 
void LeftFood(int * pos); 
bool checkMovability(int * pos, int direction); 
bool moveToDirection(int pos[2], int direction); 
bool checkSuccess(); 
void ShowResult(); 


int main(int argc, char const *argv[]) 
{ 
    timeval curTime; 
    gettimeofday(&curTime, NULL); 
    int milli = curTime.tv_usec/1000; 


    time_t t; 
    srand((unsigned)time(&t)); 

    //timeTData*.txt corresponds to using "time(&t)" above 
    //milliData.txt corresponds to using "milli" variable above 
    //timeTUnsigData*.txt corresponds to using "(unsigned)time(&t)" above 

    printf("%% Experiment Number : %d \n", MaxExp); 
    while(ExpNumber <= MaxExp) 
    { 
     Init(); 
     int pos[2]; 
     pos[0] = InitPos[0]; 
     pos[1] = InitPos[1]; 
     do{ 
      int direction = (rand() % 4) + 1; 
      if (moveToDirection(pos, direction)) 
      { 
       StepCount++;  
      } 
      if (pos[1] == 4&&grid[pos[0]][4]==2&&AntsBag==0) 
      { 
       CarryFood(pos); 
      } 
      if (pos[1] == 0&&grid[pos[0]][0]==0&&AntsBag==2) 
      { 
       LeftFood(pos); 
      } 
      checkSuccess(); 
     } 
     while(!Success); 

     ShowResult(); 
     ExpNumber++; 
    } 

    return 0; 
} 

void Init() 
{ 
    Success = false; 
    StepCount = 0; 
    AntsBag = 0; 
    int gridInit[5][5] = { 
     {0, 0, 0, 0, 2}, 
     {0, 0, 0, 0, 2}, 
     {0, 0, 0, 0, 2}, 
     {0, 0, 0, 0, 2}, 
     {0, 0, 0, 0, 2} 
    }; 
    for (int i = 0; i < 5; ++i) 
    { 
     for (int j = 0; j < 5; ++j) 
     { 
      grid[i][j] = gridInit[i][j]; 
     } 
    } 
} 

void ShowResult() 
{ 
    /* 
    for (int i = 0; i < 5; ++i) 
    { 
     printf("\n"); 
     for (int j = 0; j < 5; ++j) 
     { 
      printf("%d ", grid[i][j]); 
     } 
    } 
    */ 
    printf("%d %d\n", StepCount, ExpNumber); 
} 

void CarryFood(int * pos) 
{ 
     AntsBag = 2; 
     grid[pos[0]][4] = 0; 
} 

void LeftFood(int * pos) 
{ 
     AntsBag = 0; 
     grid[pos[0]][0] = 2; 
} 

bool checkMovability(int * pos, int direction) 
{ 
    switch(direction) 
    { 
     case 1: 
     { 
      if(pos[1]==0){ 
       return false; 
      } 
      break; 
     } 
     case 2: 
     { 
      if (pos[0]==0) 
      { 
       return false; 
      } 
      break; 
     } 
     case 3: 
     { 
      if (pos[0]==4) 
      { 
       return false; 
      } 
      break; 
     } 
     case 4: 
     { 
      if (pos[1]==4) 
      { 
       return false; 
      } 
      break; 
     } 
     default: 
     { 
      printf("Wrong direction input is given!!\n"); 
      return false; 
      break; 
     } 
    } 
    return true; 

} 

bool moveToDirection(int * pos, int direction) 
{ 
    if (!checkMovability(pos, direction)) 
    { 
     return false; 
    } 

    switch(direction){ 
     case 1: 
     { 
      pos[1] -= 1; 
      break; 
     } 
     case 2: 
     { 
      pos[0] -= 1; 
      break; 
     } 
     case 3: 
     { 
      pos[0] += 1; 
      break; 
     } 
     case 4: 
     { 
      pos[1] += 1; 
      break; 
     } 
     default: 
     { 
      printf("I'm stunned!\n"); 
      return false; 
      break; 
     } 
    } 
    return true; 
} 

bool checkSuccess() 
{ 
    for (int i = 0; i < 5; ++i) 
    { 
     if (grid[i][0] != 2) 
     { 
      return false; 
     } 
    } 
    //printf("Success!\n"); 
    Success = true; 
    return true; 
} 

Und die Ausgabe in eine * .txt-Datei und finden Sie den Erwartungswert der Anzahl der Schritte mit der folgenden Oktave Code umgeleitet;

clear 
load data.txt 
n = data(:,1); 

output_precision(15); 

mean(n) 

%% The actual data 

%% milliData1 -> 430.038224000000 
%% milliData2 -> 430.031745000000 

%% timeTData1 -> 430.029882400000 
%% timeTData2 -> 430.019626400000 

%% timeUnsigData1 -> 430.028159000000 
%% timeUnsigData2 -> 430.009509000000 

Aber auch ich den exakt gleichen Code ausführen zweimal ich unterschiedliche Ergebnisse erhalten, wie Sie aus den obigen Ergebnissen sehen. (Man beachte, dass, ich habe schon versucht, diesen mit verschiedenen srand (..) Eingängen aus dem Grunde, Ich werde es erklären.

Ich dachte, dass der Grund dafür ist, weil ich eine zufällige ganze Zahl zwischen 1-4 für die zufälligen Richtungen der Ameise erzeuge, denn so weit wie ich gewesen bin, sollte die Wahrscheinlichkeitsverteilung dieses Experiments die gleiche sein Solange ich das Experiment eine große Anzahl von Zeit (in diesem speziellen Fall 5000000 mal) wiederhole.

Also meine erste Frage ist, dass es wirklich das Problem mit der Methode ist, wie ich zufällige Ganzzahlen erzeuge? Wenn ja, wie können wir dieses Problem lösen, ich meine, wie können wir eine ganze Zahl zufällig genug erzeugen, so dass, wenn wir das gleiche Experiment viele Male wiederholen, der erwartete Wert zwischen diesen kleiner ist als diese Ergebnisse, die ich habe?

Answer 1

Sie können so etwas wie

std::mt19937 gen{std::random_device{}()}; 
std::uniform_int_distribution<int> dist{1, 4}; 

int randNumber = dist(gen); 

Dies erzeugt eine gleichmäßigere Verteilung von Werten verwenden.