• Как это решается?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Соотношение углов намекает, что стоит провести биссектрису угла ABC. Пусть она пересечет сторону AC в точке E. Можно заметить, что треугольник AEB будет равнобедренный и EM - его высота и медиана и параллельна СВ. Теперь проведите прямую через E, параллельную AB. У вас там сверху получится треугольник, подобный ABC, и отрезок CD будет его высотой. И там будет малая часть, равная искомому DM. Еще CBE будет подобен CAB. Вот составьте кучу соотношений для этих трех подобных треугольников.
    Ответ написан
    Комментировать
  • Как нагрузить расчёт в однопоточной программе C++ до 90-100% на используемом ядре?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Во-первых, вы уверены, что у вас эти 10-15% - это загрузка ядра, а не вcего процессора? Диспетчер задач обычно показывает как 100% полную загрузку всех ядер.
    Во-вторых, что у вас там за вычесления? Работа с целыми числами? Float? Всякие векторные инструкции? Точно нет никаких пауз вроде sleep()?

    Выделение памяти медленное, да, но это потому что надо много вычислений сделать, чтобы найти какой-же кусок памяти выдать программе.

    Самое вероятное место для тормозов - это вывод на экран/в файл. Если вы много отладочной информации выводите, это будет бутылочным горлышком.

    Теоретически очень активное обращение к памяти тоже будет тормозить, особенно, если памяти не хватает и идет работа с файлом подкачки.
    Ответ написан
  • Как использовать квадро-дерево, если его элементы необходимо изменять?

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

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Вот вы и определили наконец-то мю через ai. Теперь вам надо найти такие i, что мю по этой вот формуле равна заданному значению. И вероятность будет суммой вероятностей элементарных исходов, которые дают нужное значение. Просто подсчитайте 6 значений mu для каждого i.

    Первый случай: mu = 6. Т.е. i(7-i)=6. Подходят i=1 и i=6. Вероятности a1 и a6 - 1/91 и 36/91. Суммарно получается 37/91. Аналгоично для других значений.
    Ответ написан
    Комментировать
  • Как сгенерировать непрерывные случайные величины с заданным законом распределения?

    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 комментария