Comments 16
давайте рассмотрим дроби 999999/1000000 и 1/1000000
Иметь массив с миллионом значений — это как-то странно. Зачем? Когда мы получили индекс в условной честной кости, просто сравниваем — индекс меньше 999999? Значит ноль. Больше — один. Массив с 999999 нулями абсолютно не нужен.
Дальше не стал читать, не похоже, что автор исходной статьи профессионал.
Я её не упустил. Автор рассмотрел две грани, я тоже рассмотрел две грани. Зачем вы говорите про одну грань, мне не понятно. В случае N граней схема примерно такая же. Если выбросили меньше шести — ответ ноль. Меньше 6+4 — ответ один. Меньше 6+4+1 — ответ два. Иначе — ответ три. (Это для случая самой первой шуллерской кости из статьи)
Генерация таких условий достаточно проста и намного выгоднее по памяти, чем массив. Если минусующие кроме минуса ещё и пояснят, в чем я ошибаюсь, буду благодарен.
По сути — в том, что вы заранее предполагаете, что автора глупее вас. И столкнувшись с примером, который он приводит для подготовки к введению действительно крутого алгоритма, утверждаетесь в своём предположении и до этого алгоритма не дочитываете.
Alias — действительно крутой алгоритм, тут возражений нет. Но качество алгоритма и качество статьи стоит рассматривать отдельно.
ну, O(log(n)), если с двоичным поиском
Согласен, я действительно упустил этот момент.
Минусы этого алгоритма, кстати, понятны — НОК может быть очень высок и не влезать в MAX_INT используемого языка программирования. Придется использовать библиотеку для работы с большими числами. Рулетка более удобна. Но генерировать массив — это явно странное решение, разве нет?
Шулерская кость из честных костей/несимметричных монет(бросание дротика)
Не будет ли, для этого метода, худшим случаем бесконечное число бросков? Ведь если для любого броска существует вероятность не попасть, то, существует вероятность, что мы не попадем никогда. Или я что-то не учитываю?
Дротики, кости и монеты: алгоритмы выборки из дискретного распределения