如何生成足够随机的随机整数？

Question

我正在尝试解决欧拉计划的第280个问题，并为此编写了以下模拟代码;

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

把输出重定向到一个*.txt文件，并使用以下Octave代码找到步数的期望值：

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

然而，即使我运行完全相同的代码两次，也会得到不同的结果，正如您可以从上面的结果中看到的那样。（请注意，出于我将要解释的原因，我已经尝试过使用不同的srand（..）输入。）

我认为这个问题的原因是我如何生成1-4之间的随机整数来确定蚂蚁的随机方向，因为根据我的理解，只要我重复大量次数的实验（在这种情况下是5000000次），这个实验的概率分布应该是相同的。

所以我的第一个问题是，真的是由于我生成随机整数的方法存在问题吗？如果是这样，我们该如何克服这个问题，我的意思是，我们如何生成足够随机的整数，以便当我们重复相同的实验大量次数时，期望值比我得到的结果更小？

- Our

---

我怀疑你更倾向于通过数学而非模拟来解决这个问题。构建状态图并分析以计算平均值可能是可行的。但是，我一时半会儿不确定。 - Eric Postpischil

输入可能具有巨大的方差，例如100-1000，因此5m数据点只能给您展示同样数量的显著性（例如430.03±0.02）；输入随机性不太可能是主要问题。尽管如此，这仍然可以在没有任何随机性的情况下解决；搜索“马尔可夫链预期步数”以获取本科级别的相关材料。 - Veedrac

@Veedrac 你是怎么知道输入的方差的？你是如何计算那个误差棒的？ - Our

不确定我能否在这里的评论中快速概括误差条，但（非常）粗略地说，您只需取样本数的平方根即可获得相对显着性，并将其乘以您的值以获得绝对显着性。我不知道是否手动检查了方差，但如果您知道随机游走的工作原理，您可以猜测一些东西。 - Veedrac

@Veedrac 好的，谢谢你的回答。 - Our

Answer 1

你可以使用类似于

这样的东西。

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

int randNumber = dist(gen);

这将生成更具均匀性的值分布。

- Kalika