Специальный простой генератор случайных чисел
Как создать функцию, которая на каждом вызове генерирует случайное целое число? Это число должно быть самым случайным как возможное (согласно равномерному распределению). Только позволяется использовать одну статическую переменную и самое большее 3 элементарных шага, где каждый шаг состоит только из одной основной арифметической операции арности 1 или 2.
Пример:
int myrandom(void){
static int x;
x = some_step1;
x = some_step2;
x = some_step3;
return x;
}
Основные арифметические операции +, - %, и, не, xor, или, сдвиг влево, сдвиг вправо, умножение и разделение. Конечно, никакой рэнд (), случайный () или подобный материал не позволяется.
5 ответов
Линейные конгруэнтные генераторы - один из самых старых и простых методов:
int seed = 123456789;
int rand()
{
seed = (a * seed + c) % m;
return seed;
}
Всего несколько инструкций с базовыми арифметическими операциями, вот и все, что вам нужно.
Учтите, что этот алгоритм работает хорошо, только если a, c и m выбраны определенным образом!
Чтобы гарантировать максимально возможный период этой последовательности, c и m должны быть простыми, a - 1 должно быть кратно всем простым факторам m, а также 4, если m кратно 4.
Некоторые примеры параметров приведены в Википедии: например, ANSI C для некоторых компиляторов предлагает m = 2 ³¹, a = 1103515245 и c = 12345.
Если я напишу man rand , я смогу прочитать возможный пример, приведенный в POSIX.1-2001, для реализации rand () и srand (). См., Например, здесь . Если вам нужно что-то более сложное, загляните в Научную библиотеку GNU ; вы, конечно, можете загрузить код и увидеть реализацию (ы).
Boost имеет очень красивую библиотеку случайных чисел, и исходный код доступен, так что вы можете попробовать поискать там и использовать то, что вам нужно (то есть вырезать и вставить).
Вот функция с равномерным распределением по всему диапазону int:
int rand()
{
static int random = 0;
return random++;
}
Вы можете посмотреть это . Это далеко не «идеальный» генератор случайных чисел, но, насколько я могу судить, он удовлетворяет вашим требованиям.
Здесь вы можете найти дополнительную информацию о генерации случайных чисел.