Array的重新排列元素：基于堆栈的缓冲区溢出错误

我给出的代码是原始程序的问题部分。它随机交换myArray的两个元素N次，并在T个循环中交换。该程序做它应该做的，但点击“返回0”后，它显示“program.exe已停止工作”的错误信息。调试输出显示为Array的重新排列元素：基于堆栈的缓冲区溢出错误

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

有这种方法的问题一个不错video。 Mic和Bob__指出，还存在由(N-1)*rand()引起的超限问题。

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

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

同样对于混洗的数组元素最好是使用以获得最佳性能random_shuffle功能或Fisher–Yates shuffle。

来源

2017-07-02 SS.

这是用于写入数组末尾的bat信号。当然，rand（）不会做你认为它做的事情。这段代码通常是非常错误的，它实际上并不是随机的，请google“C++ fisher yates shuffle”。 –

rand（）/ RAND_MAX'执行一个* integer *除法，结果为0（或rand（）返回RAND_MAX时为1） –

如果RAND_MAX很大，计算N * rand（）将溢出，您将得到奇怪的索引值。您可以使用模块算术或将其转换为double。谷歌stdlib兰特关于如何使用rand（） – Mic

让我们考虑这条线（所编辑qustion的）：

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

哪里save1是int类型的变量，N是相同类型的常量和rand()返回值的范围[0的int， RAND_MAX]。

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

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

你可以看到here你的程序（我只添加一行来证明我的观点）编译并执行。请注意indeces数量不为零。

在C A常见的方式，使用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-02 14:27:47

至少有一点修正：

兰特（）返回一个0到RAND_MAX（含）之间的随机整数，所以你必须更换

N*rand()/RAND_MAX

通过

N*rand()/(1+RAND_MAX)

来源

2017-07-02 08:01:20

此时应更换N与(N-1)。可能这就是你想要做的。

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

只是想知道，如果你的目的是使用'索引1' 的语句计算SAVE1 & SAVE2。这也将解决问题。

来源

2017-07-02 08:22:21 MKR

的例子谢谢..这解决了我的问题。没有意识到这个愚蠢的错误。 –

Array的重新排列元素：基于堆栈的缓冲区溢出错误

回答

相关问题