Перемешивание элементов массива: ошибка переполнения буфера в стеке

Данный код является проблемной частью оригинальной программы. Он меняет два элемента 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). Вызов Nth местоположения в myArray создавал проблему.

Но ни один из следующих методов не генерирует случайное целое число равномерно.

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

ни

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

Есть хороший видео по проблеме этого метода. Существует также проблема переполнения, вызванная (N-1)*rand() как указывали Мик и Боб.

Этот метод по модулю также очень неэффективен для большого диапазона случайных целых чисел (отметьте это статья для деталей). Итак, мой лучший шанс генерации равномерных случайных чисел — следующий метод (заимствовано из статьи).

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

Также для перетасовки элементов массива лучше всего использовать random_shuffle функция или Fisher–Yates shuffle для оптимальной производительности.

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 < Икс < RAND_MAX результат 0.

Ты можешь видеть Вот что ваша программа (я только добавил строку, чтобы доказать свою точку зрения) компилируется и выполняется. Пожалуйста, обратите внимание, сколько раз значения не равны нулю.

Общий способ в C, используя rand(), чтобы сгенерировать случайное число от 0 до N (исключено):

int number = rand() % N;

Рассмотрим также лучший алгоритм перемешивания массива, например Фишер Йейтс, что вы могли бы реализовать в 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);
}
0

Другие решения

По крайней мере, одна вещь, чтобы исправить:

rand () возвращает случайное целое число от 0 до RAND_MAX включительно, поэтому вы должны заменить

  N*rand()/RAND_MAX

от

  N*rand()/(1+RAND_MAX)
0

Вы должны заменить N с (N-1), Вероятно, это то, что вы хотите сделать.

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

Просто интересно, если вы намерены использовать `Index1 ‘в выражениях для вычисления save1 & save2. Это тоже исправит проблему.

0