0

我给定的代码是原始程序的问题部分。它随机交换 myArray 的两个元素 N 次，循环次数为 T。该程序做了它应该做的，但是在点击“return 0”后它显示“program.exe已停止工作”的错误消息。调试输出显示

Stack cookie instrumentation code detected a stack-based buffer overrun

为什么程序在完成工作后显示错误？我怎样才能解决这个问题 ？

#include <iostream>
#include <ctime>    
#include <cstdlib>

using namespace std;

int main()
{
    const int N = 10000;
    const int T = 100; 

    srand((unsigned)time(0));   

    bool myArray[N] ;
    bool temp = true;
    int save1 = 0;
    int save2 = 0;

    //initializing myArray
    for (int index = 0; index < N/2; index++) {
        myArray[index] = false;
    }
    for (int index = N/2; index < N; index++) {
        myArray[index] = true;
    }

    for (int index = 0; index < T; index++) {

        for (int index1 = 0; index1 < N; index1++) {    
            save1 = int( N*rand()/RAND_MAX );
            save2 = int( N*rand()/RAND_MAX );


            temp = myArray[save1];
            myArray[save1] = myArray[save2] ;
            myArray[save2] = temp; 
        }
    }

    cout<<" Press any key to exit...";
    cin.get();

    return 0;
}

编辑：我必须生成从 0 到 (N-1) 的随机整数。在 myArray 中调用第 N 个位置会产生问题。

但以下两种方法都不是统一生成随机整数。

    save1 = int( (N-1)*rand()/RAND_MAX );

也不

    save1 = int( N*rand()/(RAND_MAX+1) );

关于这种方法的问题有一个很好的视频。(N-1)*rand()正如 Mic 和 Bob__ 所指出的那样，还有一个溢出的问题。

这种取模方法对于大范围的随机整数也非常低效（详情请查看本文）。因此，我生成统一随机数的最佳机会是以下方法（从文章中借用）。

while(true)
{
  int value = rand();
  if (value < RAND_MAX - RAND_MAX % range)
    return value % range;
}

同样对于洗牌数组元素，最好使用random_shuffle函数或Fisher–Yates shuffle获得最佳性能。

4

3 回答 3

0

让我们考虑这一行（编辑后的问题）：

save1 = int( (N-1)*rand()/RAND_MAX );

其中save1是 类型的变量int，N是相同类型的 const 并rand()返回int[0, RAND_MAX] 范围内的一个。

在 C++ 中，这个表达式是从左到右计算的，所以首先是乘法，然后是除法。如果rand()返回的值大于 INT_MAX / (N - 1)，则此操作会溢出，导致未定义行为。在大多数实现中，由于整数值的二进制补码表示，结果可能是负值。

之后，执行一个整数除以 RAND_MAX，因此对于任何值 x 使得 -RAND_MAX < x < RAND_MAX 结果为 0。

您可以在这里看到您的程序（我只添加了一行来证明我的观点）编译并执行。请注意有多少次 indeces 不为零。

C 中使用rand(), 生成 0 和 N（排除）之间的随机数的常用方法是：

int number = rand() % N;

还可以考虑一种更好的算法来对数组进行洗牌，例如Fisher Yates，您可以在 C 中将其实现为：

void my_c_shuffle(bool *arr, size_t n)
{
    while ( n > 1 )
    {
        size_t choice = rand() % n;
        --n;
        bool temp = arr[n];
        arr[n] = arr[choice];
        arr[choice] = temp;
    }
}

在 C++ 中，您应该使用标准库而不是重写这些算法：

#include <iostream>
#include <random>
#include <array>
#include <algorithm>

int main()
{
    std::random_device rd;
    std::mt19937 g(rd());

    std::array<bool, 10000> my_array;
    auto middle = my_array.begin() + my_array.size() / 2;
    std::fill(my_array.begin(), middle, false);
    std::fill(middle, my_array.end(), true);

    std::shuffle(my_array.begin(), my_array.end(), g);  
}
于 2017-07-02T14:27:47.213 回答
0

至少要解决一件事：

rand() 返回一个介于 0 和 RAND_MAX 之间的随机整数，因此您必须替换

  N*rand()/RAND_MAX

经过

  N*rand()/(1+RAND_MAX)
于 2017-07-02T08:01:20.910 回答
0

您应该替换N为(N-1). 可能这就是你想要做的。

    save1 = int( (N-1)*rand()/RAND_MAX );
    save2 = int( (N-1)*rand()/RAND_MAX );

只是想知道您是否打算在语句中使用“Index1”来计算 save1 和 save2。这也将解决问题。

于 2017-07-02T08:22:21.613 回答