(Untitled)

[_winnie]

Невозможно 2147483648 конфет раздать поровну миллиарду детишек: у кого-то будет две, у кого-то три.
Будьте осторожны с rand()%N

Ссылки:
Как правильно делать в C++11: http://dobrokot.ru/pics/i2014-06-27__02-01-24_55kb.png (из этой презентации, видео), спасибо bik_top

Comments

[realsupport]

Немудрено - задача одна, а алгоритм, видимо, решает совсем другую - случайным образом раздать конфеты, не более N в одни руки, причем все раздавать необязательно.

[_winnie]

"раздать случайно" это "вероятности одинаковые". Когда делаем rand()%N - они получаются не одинаковые. Для небольших N чуть-чуть неодинаковые, а для больших - уже заметно.

Связанная задача: Имея честную монетку, научиться эмулировать честный игральный кубик с шестью гранями.

[realsupport]

Ах, вот ты о чем.
Только не просто для больших/небольших, а связанных с RAND_MAX:
Тут более-менее толково написано:
http://stackoverflow.com/questions/10984974/why-do-people-say-there-is-modulo-bias-when-using-a-random-number-generator

[ahaxopet]

Просто эмулировать кубик легко - кидаем монетку три раза подряд, генерируем число от нуля до семи. Если получилось 6 или 7 - результат отбрасываем, повторяем упражнение.

А вот как эмулировать эффективно - это уже интереснее..

[_winnie]

Можно как арифметическое кодирование:

считаем, что у нас есть последовательность нулей и единиц.
Считаем, что это запись двоичной дроби, число от 0 до 1.

Делим промежуток A = [0, 1) на шесть равных частей. Смотрим, в какую 1/6 часть попало это число. Эту часть считаем новым промежутком A.

Делить точно на равные 6 частей - неудобно при написании программмы (легко набажить при реализации, медленней работает). Если готовы терпеть не совсем точное деление на 6 - то можно поделить на промежутки [i*2^32/6, i = 0,1,..5]

[ahaxopet]

Если делить точно - то невозможно гарантировать выдачу ответа за конечное время. Мы кидаем монетку, а она каждый раз выдает следующий знак двоичного разложения 1/6...

Интересно, есть ли алгоритм с гарантированным временем генерации каждого результата?

[_winnie]

Нет, 2^N конфет не раздашь шести детишкам поровну :)