Задать вопрос
  • Как сгенерировать непрерывные случайные величины с заданным законом распределения?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Во-первых, компьютеры вообще не могут в непрерывность. Так что вы получите лишь некоторое приближение: дискретную случайную величину с большим количеством возможных рациональных значений. Более того, компьютеры не умеют и в случайность, поэтому вы получите лишь псевдо-случайные числа.

    Обычно, сначала реализуют дискретную случайную равномерно распределенную величину. Гуглите алгоритмы генерации псевдослучайных чисел, если вам нельзя даже какой-нибудь rand() использовать.

    Далее получают равномерно распределенную случайную величину на отрезке [0,1]. Для этого генерируют случайное число от 0 до MAX_RAND и делят на MAX_RAND.

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

    Пусть x искомая случайная величина Fx(t) = P(x < t). u -равномерно распределенная случайная величина. Тогда x = Fx^(-1)(u).

    Например, для экспоненциальной случайной величины Fx(t) = 1-e^(-lt). Обратная функция будет Fx^(-1)(y) = -ln(1- y)/l. Значит считаете ваше случайное число, делите на MAX_RAND, подставляете в формулу -ln(1-y)/l. Или можно упрастить и брать просто -(ln y)/l, потому что равномерная случайная величина от 0 до 1 симметрична.

    Проблема тут с тем, что не для всех распределений можно получить обратную функцию в виде формулы. Для нормального распределения формулы как выше нет - надо использовать функцию erf(), или считать ее приблеженно руками через какие-нибудь ряды.
    Ответ написан
    Комментировать
  • Почему моё решение неправильное?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    В первом случае. P(B) = 0.2 ибо на 5 делиться только каждое 5-ое число. Соответственно, 0.1/0.2 = 0.5.

    Во втором случае у вас формула неправильная. Надо делить на P(A) = 0.5
    Ответ написан
    Комментировать
  • Почему эта программа вычисляет факториал больших чисел неправильно?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Полная фигня с распараллеливанием. Ну нельзя длинное число параллельно умножать сразу на много чисел. Во-первых, там гонка данных. Один поток может прочитать цифру, домножить ее на текущее число, в это время другой поток запишет свой результат, и тут первый поток этот результат перезапишет. Результат работы одного из потоков просто потерян. Но даже без этого - каждый поток должен видеть все цифры числа как они были, когда он начал умножать. Если какой-то другой поток там хоть что-то запишет - у вас бред будет.

    Правильное распараллеливание будет в умножении на одно число. Каждый поток домножает на число свой промежуток цифр и делает перносы только внутри своего отрезка цифр. Потом все потоки спят, а один делает переносы между границами отрезков и расширяет вектор, делая переносы в конце. При этом у вас в числе какие-то разряды будут больше базы. Потом потоки продолжают умножать уже на следующее число. Надо их синхронизировать какими-то заборами/событиями между каждым новым числом. В конце придется нормализовать число в один поток. Возможно это можно тоже распараллелить, но это сложно будет совсем.
    Ответ написан
    Комментировать
  • Почему неправильно работает сортировка вставками из "Алгоритмов..." Кормена и др.?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Потому что в книге нумерация элементов идет с 1, а в питоне - с 0.

    Надо поменять условия в циклах for и while.
    Ответ написан
  • Как составить наиболее эффективный алгоритм групповой рассылки сообщений по каналам WebSocket?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Вам по-любому придется отправить сообщение каждому пользователю, кто онлайн и подписан на канал.

    Единственное, что вы можете соптимизировать - это нахождение списка пользователей.

    Вам надо как-то побыстрее определить, какие пользователи сейчас онлайн из данного канала. Можно или поддерживать эту информацию в памяти (это будет map из channel_id в set user_id). Когда пользователь выходит в онлайн, надо добавить его в структуру данных для всех каналов, на которые он подписан. Когда пользователь отваливается - удаляйте его из памяти и чистите структуру (надо удалить ключ из map, если там значение осталось пустым).

    Еще вариант: сделать это прямо в базе данных. Для каждого пользователя поддерживайте флаг - онлайн ли он. И в базе данных спрашивайте список всех онлайн пользователей, которые подписаны на нужный канал. Можно даже ваш map user_id->socket_channel_id в базу запихать.
    Ответ написан
    Комментировать
  • Данные в таком случае будут хранится в стеке?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    В наше время можно просто проверить: godbolt.org

    И clang и g++ и при локальном и при глобальном объявлении кладут 1 на стек.
    Правда, clang чуть поумнее и выдает warning:
    warning: temporary whose address is used as value of local variable 'Number' will be destroyed at the end of the full-expression [-Wdangling]


    Нельзя надеяться, что по этому адресу останется лежать 1. В более сложных случаях этот адрес может быть переиспользован под что-то еще. Обращение по такому указателю - UB.
    Ответ написан
    Комментировать
  • Рандом маленькой разброс, как увеличить в рамках диапазона?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Можно, например, не вызывать srand, если у вас эта программа запускается несколько раз в секунду. Если реже, то все с программой хорошо, просто ваше представление о случайности не правильное.
    Ответ написан
    Комментировать
  • Undefined behavior в C++?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Скомпилирует любой компилятор с++. Может выдать ворнинги, если включена опция реагировать на предупреждения, как на ошибки, то тогда не скомпилирует, но только потому что его конкретно об этом попросили. Это не ошибка компиляции.

    В этом главная проблема Undefined Behavior: компилятор его почти всегда не видит, и программа с ним может даже работать в каких-то случаях так, как программист задумывал. А в других совершенно необъяснимо падает или выдает бред.

    У ОС защита от такой наглости с памятью, конечно, есть. Такая программа рано или поздно упадет с access violation, segmentation fault или еще чем-то подобным, когда цикл дойдет до не вашей памяти.
    Ответ написан
    Комментировать
  • С++ автоматически вставляет в функцию ссылку на вектор?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Это называется "передача по ссылке". Гуглите.
    Ответ написан
    Комментировать
  • C++ std::cout не выводит ничего?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Разность в поведении между сборками может быть обусловлена двумя причинами:
    1) в коде есть ifdef и часть функциональности просто отключена в релизной сборке. Довольно часто так намеренно отключают отладочный вывод.
    2) В коде есть ошибка, какое-то undefined behavior и при оптимизации в релизной сборке часть кода вырезается компилятором.

    Какой-то другой причины чтобы cout не работал в релизной сборке я не вижу.

    printf вы наверное сами куда-то добавили. Если заменить в коде библиотеки отсутствующий cout на printf оно так же работает? Или у вас нет доступа к коду?
    Ответ написан
    5 комментариев
  • Откуда появляется это странное число?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Читайте код внимательно:
    Ввод:
    for (int i=0; i<x; i++){

    Вывод:
    for (int i = 0; i <= x; i++){

    У вас там <= в конце. Из-за этого идет обращение к элементу по индексу x, за границей массива. И оттуда выводится какой-то мусор - это и есть ваше странное число.
    Ответ написан
    Комментировать
  • Насколько больше будет занимать памяти Свойство (get + set)?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Ну так тут у вас функции тоже есть. Эти две ваших лябды окажутся какими-то фнукциями, которые компилятор куда-то засунет, и в классе к вас будут 2 переменные, хранящие адресс этих функций.

    Если вы сделаете просто методы Get и Set, то будут точно такие же 2 функции в памяти. Важно, что в вашем текущем и в предолженном решении функции не храянятся в эксземплярах объекта. Обычно они в коде программы встречаются ровно по одному разу*.

    *Если не учитывать инлайнинг функций. Иногда компилятор вместо вызова тупо вставлят тело функции в код. Но это не сильно увеличивает размер кода обычно. И никак не зависит от количества и размера объектов в памяти.
    Ответ написан
    Комментировать
  • Как правильно перегрузить шаблонный оператор (метод, функцию), чтобы наследники попадали в нужный?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Можно попробовать enable_if<> скомбинировать с is_base_of<>. Только нужно все ваши классы Id унаследовать от одного какого-то общего. И во всех наследниках объявлять int поле, которое и брать в теле функции. Только уже не получится этот int сделать параметром шаблона.
    Ответ написан
    Комментировать
  • Что значит такое объявления полей в С++?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Да. Field - ссылка на приватное поле. Но она константная, поэтому так дается доступ к приватному полю только на чтение.

    Это становится понятнее, если воспринимать ссылки как указатели, которые не могут быть нулевыми, не могут менять адресс, куда они указывают, и должны быть инициализированны.
    Ответ написан
    5 комментариев
  • Как исправить ошибку error: linking with `link.exe` failed: exit code: 1120?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Надо линкеру указать dll-ку в которой эта функция определена. В документации не указано, в какой именно библиотеке оно лежит, но можно пропробовать Gdi32.dll или Ddraw.dll. Надо где-то в настройках проекта на вкладке про линкер указать эти dll.
    Ответ написан
    Комментировать
  • Как сделать в строке замену нескольких конкретных одинаковых символов на один такой?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Это еще ничего, а как вы хотите, чтобы парсилась строка "1111,2222,3333"? Как 11112222.3333? Или 111.22223333? Или что?

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

    Например, можно просто читать сразу число. Если вам надо, чтобы число было корректным и при использовании '.' и ',', то можно просто все запятые поменять на точку.
    Ответ написан
    2 комментария
  • Бинарный поиск. Правильно ли работает?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    if i == middle - 1 or i >= 5 and len(list) <= 4:
                return -1


    Вот эта часть вызвает вопросы. Отладочный код остался?

    Проблема в вашем коде, что он виснет, если числа в массиве вообще нет. Условие должно быть не про равенство, а про то, что у вас отрезок пуст (или длины 1) - надо сравнивать first и last.

    Обычно middle не поддерживают между итерациями цикла, а просто считают внутри. Между итерациями переходят только first и last.

    А так, да, бинпоиск - это весьма простой алгоритм.
    Ответ написан
    1 комментарий
  • Vcpkg: почему видит хедеры, но не видит cpp файлы?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Вам надо к вашему проету подключить библиотеки. Смотрите в свойствах линкера.
    Ответ написан
    1 комментарий
  • В чём смысл равного ограничения времени для разных ЯП в спортивном//олимпиадном программировании?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Смысл в том, что итак работает. Редко когда можно TLющееся решение переписать на другом языке программирования, и оно пройдет. Ибо все правильные решения различаются на десяки процентов, максимум, в разы. Неправильные же отсатют от правильных в десятки и сотни раз. По крайней мере на соревнованиях высокого уровня. А потом, ну просто лень составителям придумывать ограничения для всех языков программирования. А, поскольку оно итак работает, то никто этим не заморачивается. Многие системы тестирования даже не поддерживают разные ограничения под разные языки, и никто эту фичу не запиливает, потому что она никому и не нужна особо.
    Ответ написан
    Комментировать
  • Дейкстра почти за линейное время (для неориентированного графа)?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    В сетевом роутинге, в основном, нет* центрального узла с информацией о всей топологии, чтобы искать пути. Так что там вообще не работает Дейкстра, а работают распределенные алгоритмы.

    А так, да, на очень специфичных гарфах всеядный алгоритм Дейкстры не самый лучший вариант. И ваш алгоритм тут получается быстрее.

    * Вообще, есть такая тема, как Software Defined Networking, где как раз есть центральный узел, который все и решает, но это чисто теория пока, и там суть не в поиске кратчайших путей в графе а во всяких сложных механизмах приоритезации трафика и устойчивости к сбоям.
    Ответ написан
    1 комментарий