СЛУЧАЙНОЕ Поколение Чисел в C - PullRequest
4 голосов
/ 19 апреля 2010

Недавно я начал разработку простой игры. Это улучшенная версия более ранней версии, которую я разработал. Большая часть успеха игры зависит от генерации случайных чисел в разных режимах:

MODE1 - действительно случайный режим

myRand (мин, макс, режим = 1);

  • Должен вернуть мне случайное целое число ч / б мин и макс.

MODE2 - псевдослучайный: токен из режима сумок

myRand (мин, макс, режим = 2);

  • Должен вернуть мне случайное целое число ч / б мин и макс. Также должен внутренне отслеживать возвращаемые значения и не должен возвращать то же самое значение снова, пока все другие значения не будут возвращены по крайней мере один раз.

MODE3 - псевдослучайный режим: человек

myRand (мин, макс, режим = 3); * +1032 *

  • Должен вернуть мне случайное целое число ч / б мин и макс. Рандомизация должна быть не чисто математически случайной, а скорее случайной, как ее воспринимает пользователь. Как люди видят СЛУЧАЙНО .

* Предположим, что код критичен ко времени (т. Е. Приветствуются любые оптимизации производительности)

* Псевдокод подойдет, но мне нужна реализация на C.

* Пожалуйста, будьте проще. Одной функции должно быть достаточно (вот что я ищу)

Спасибо

Ответы [ 4 ]

4 голосов
/ 19 апреля 2010

Во-первых, исследуйте Twister Mersenne. Это должно стать отличной основой для вашей проблемы.

Режим 1: напрямую используйте значения. Учитывая, что значения являются 32-битными, в зависимости от диапазонов min и max, по модулю (max-min + 1) может быть достаточно хорошим, хотя есть небольшой уклон, если этот интервал не является степенью двойки. В противном случае вы можете рассматривать значение как значение с плавающей запятой в диапазоне от 0 до 1 и требовать дополнительных операций. Могут быть и другие решения, чтобы получить равное распределение с целыми числами, но я еще не исследовал эту конкретную проблему. Википедия может помочь здесь.

Режим 2: используйте массив, который вы заполняете min..max, а затем перемешиваете его. Вернуть перемешанные значения по порядку. Когда вы пройдете через массив, добавьте и перетасуйте.

Режим 3 является наиболее сложным. Небольшие количества случайных значений показывают кластеры, то есть если вы подсчитываете вхождения разных значений, у вас есть среднее значение, и значения обычно выше или ниже этого среднего. Как я понимаю вашу ссылку, люди ожидают, что случайность будет иметь все значения в среднем. Поэтому посчитайте вхождения и дайте различным значениям более высокую вероятность, в зависимости от их расстояния до среднего значения. Может быть достаточно просто повторно использовать режим 2 с несколькими массивами, например используйте массив, в 10 раз превышающий размер (max-min + 1), заполните его 10x min, 10x min + 1 и т. д. и перемешайте его. Каждые полные 10 раундов вы получаете равное количество.

РЕДАКТИРОВАТЬ в режиме 3:

Скажем, у вас есть мин = 1 и макс = 5. Вы считаете события. Если все они имеют одинаковую вероятность (которую они должны использовать с помощью хорошего генератора случайных чисел), то эта вероятность для каждого значения будет равна 0,2, поскольку вероятности составляют в сумме 1,0:

Value Occur Probability
1     7x    0.2
2     7x    0.2
3     7x    0.2
4     7x    0.2
5     7x    0.2
Average: 7x

Но теперь давайте скажем, что 3 произошло только 5x и 5 произошло 9x. Если вы хотите сохранить равное распределение, то 3 должно стать более высокой вероятностью, чтобы догнать среднее вхождение, а 5 должно стать более низкой вероятностью, чтобы не расти так быстро, пока все другие значения не будут догонены. Тем не менее, все индивидуальные вероятности должны составлять в целом 1,0:

Value Occur Probability
1     7x    0.2
2     7x    0.2
3     5x    0.3
4     7x    0.2
5     9x    0.1
Average: Still 7x

Разные вхождения должны также иметь разные вероятности в зависимости от их среднего расстояния:

Value Occur Probability
1     10x   0.05
2     4x    0.35
3     5x    0.3
4     7x    0.2
5     9x    0.1
Average: Still 7x

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

3 голосов
/ 19 апреля 2010

В качестве первого шага иди и прочитай Кнут

0 голосов
/ 19 февраля 2011

воспринимаемое человеком будет таким же, как в первом режиме, за исключением того, что результаты, кратные 2, 5, 10, могут быть произвольно отклонены.

если бы я попросил случайное число и получил 5 или 10, я бы подумал, что это не достаточно случайно.

0 голосов
/ 19 апреля 2010

Вы можете использовать регистр сдвига с линейной обратной связью для режима 2, если max-min = 2 ^ N-1. Этот тип генератора случайных чисел создает повторяющуюся последовательность из 2 ^ N-1 чисел с N-битной внутренней памятью. См. http://en.wikipedia.org/wiki/LFSR для более подробного объяснения и кода.

...