a=b*r + q
В C++ есть генератор случайных целых чисел – int rand() – диапазон выдаваемых значений ограничен размером внутренней константы RAND_MAX - от 0 до 32767. Но на практике иногда приходится работать с более узкими диапазонами. Как же можно сузить диапазон в данном случае? Для этого прибегают к такому ухищрению:
rand()%x + y
В этом случае мы будем получать случайные числа из диапазона между y и x, то бишь
y ≤ rand()%x + y ≤ x
Корректно ли использовать данный подход? Для поиска ответа снова воспользуемся вышеприведенным выражением:
a = b*r + q
С точки зрения программирования это выражение можно представить и так:
a = b*(a/b) + (a%b)
Мы знаем, что в случае, когда a кратно b, то второе слагаемое равно нулю:
То есть в точках 2n и 2n+1 q обращается в ноль. Рассмотрим этот диапазон, для этого предположим, что a/b лежит между 2n и 2n+1, запишем это утверждение следующим образом:
(a/b) = 2n + ε, где ε - величина смещения в диапазоне от 2n до 2n+1
Подставим данное уравнение в общее уравнение:
a = b(2n + ε) + q = 2nb + bε + q,
q(ε) = a - 2nb - bε
Так как 0 ≤ ε ≤ 1, то q(1) ≤ q ≤ q(0), здесь стоит оговориться – возможно, что покажется неочевидным второе неравенство, но если посмотреть внимательно на полученное уравнение:
q(ε) = a - 2nb - bε,
то можно видеть, что чем больше ε, тем меньше q(ε) и наоборот, чем меньше ε, тем больше q(ε). Отсюда имеем математическое неравенство q(1) ≤ q ≤ q(0), раскроем его и решим:
a - 2nb - b ≤ q ≤ a - 2nb,
-b ≤ q ≤ 0
Перемножим обе части неравенства на -1:
0 ≤ q ≤ b
Перепишем это неравенство с точки зрения программирования:
0 ≤ (a%b) ≤ b
Таким образом, мы доказали (подтвердили) правильность подхода при сужении диапазона выходных случайных чисел для тех или иных практических задач с помощью вот такого выражения:
rand()%x + y
Всем отличного утра, дня или ночи :)