Перемешивание элементов массива: ошибка переполнения буфера в стеке
Данный код является проблемной частью оригинальной программы. Он меняет два элемента 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 для оптимальной производительности.
Решение
Давайте рассмотрим эту строку (отредактированного кода):
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);
}
Другие решения
По крайней мере, одна вещь, чтобы исправить:
rand () возвращает случайное целое число от 0 до RAND_MAX включительно, поэтому вы должны заменить
N*rand()/RAND_MAX
от
N*rand()/(1+RAND_MAX)
Вы должны заменить N с (N-1), Вероятно, это то, что вы хотите сделать.
save1 = int( (N-1)*rand()/RAND_MAX );
save2 = int( (N-1)*rand()/RAND_MAX );
Просто интересно, если вы намерены использовать `Index1 ‘в выражениях для вычисления save1 & save2. Это тоже исправит проблему.