Задать вопрос
  • Как реализовать многопоточность на C++?

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

    Вот в 0 секунд у вас I1..I5 сгенерировали заявки, они пападают в накапители и сразу же из них в каналы. В 3 секунды K1 обработал заявку и свободен. Взял одну из накопителя. В 4 секунды K2 освободился, взял заявку из накопителя. В 5 секунд источники снова сгенерировали заявки... и т.д. Это можно просимулировать.

    Реализуется это с помощью приоритетной очереди событий. В нее вы складываете новые события, а в основном цикле достаете оттуда событие с минимальным временем. На c++ это будет что-то вроде:
    std::priority_queue<pair<int, Event>, std::vector, std::greater> queue
    .

    Еще вам надо написать классы для источника, накопителя, блокиратора с условиями (не понял, что это) и накопителя.

    Например, источник в момент создания кладет в очередь событие "в 0 секунд я создам заявку". При выполнении этого события, во-первых, создается и кладется в очередь новое событие "в t+5 секунд я создам заявку". Во-вторых, надо посмотреть, куда заявки из этого источника попадают. Если это накопитель, то заявка пихается в него.

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

    Класс канала при получении заявки создает событие во время t+время обработки заявки, что он освободится. При вы полнении этого события канал смотрит, к чему он подключен и если там не пустой накопитель, то забирает оттуда первую заявку.

    Класс Event должен как-то запоминать какой объект это событие выполняет. А основной цикл должен этот код вызывать (и передавать туда время события).
    Ответ написан
    Комментировать
  • Инструмент для сохранения всех вариантов сочетаний по заданной маске?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Есть. Называется python + модуль itertools.
    import itertools
    import string
    
    def generate_strings(length):
        chars = string.ascii_letters + string.digits
        for item in itertools.product(chars, repeat=length):
            yield "".join(item)
    
    for string in generate_strings(3):
        print(string)


    Для 8 символов поменяйте 3 в коде на 8.
    Ответ написан
    Комментировать
  • Как получить хендл без OpenProcess?

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

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

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Если вы уверены, что он планарный, то его надо нарисовать без пересечений ребер. Подвигайте вершины туда-сюда.

    А теоремы эти используют как раз, чтобы доказать, что граф не планарный. Тогда вы берете как-то стягиваете его вершины и получаете K33 или K5. Значит не планарный.

    Доказать отсутствие таких стягиваний очень муторно. Надо перебирать все варианты. Типа, что будет если мы вот эти 2 вершины стягиваем в одну? А если нет? В первом случае, а стягиваем ли мы туда вот эту третью? А если нет? И так у вас 100500 случаев. Если очень граматно выбрать вершины, то есть шанс, что количество вариантов будет не слишком большое. Если видите, что стянутый граф можно нарисовать без самопересечений, дальше стягивать не надо.
    Ответ написан
    2 комментария
  • Как из массива байтов HEX сделать сделать DEC?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Можно без перевода в десятичную систему считать. Столбиком, как в начальной школе. Это будет работать даже если ваши числа длиннее 4 байт.
    byte summ[N];  // N >= skoll_len+sprice_len.
    for (int i = 0; i < skoll_len; ++i ) {
      word carry = 0;
      for (int j = 0; j < sprice_len; ++j) {
        carry += summ[i+j] + (word)skoll[i] * sPrice[j];
        summ[i+j] = carry % 256;
        carry /= 256;
      }
      if (carry > 0)
        summ[x_len + y_len - 1] += carry;
    }


    Тут три неочевидных момента. При прибавлении одной строки из умножения столбиком все переносы считаются сразу одним проходом. Во-вторых, там может быть какой-то лишний перенос в конце, но только на одну дополнительную ячейку, потому что x < 256^x_len, y <256^x_len, а значит x*y < 256^(x_len+y_len), значит не будет никакой записи дальше ячейки x_len+y_len-1. И последнее, carry по пути нигде ни разу не переполнится, ибо максимальная сумма там может быть 255*255+255+255 < 256*256.

    P.s. Но если у вас числа уж очень длинные, то гуглите быстрое преобразование фурье + длинное умножение.
    Ответ написан
    3 комментария
  • Как узнать, входит ли игрок1 (x,y,z) в поле игрок2 (x,y,z)?

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

    Самый наивный алгоритм - перебрать все пары на сервере, если два игрока достаточно близкие, то выдать каждому список из соседей, а игрок уже сам с ними общается. Ну, или каждый игрок заправшивает у сервера кто его соседи, сервер ищет, перебирая всех соседей, и выдает список. Можно считать квадрат расстояния по теореме пифагора, и сравнивать с квадратом нужного расстояния (диаметр окружности).

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

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Конечно, на эту задачу можно натянуть префиксные деревья (это же вы бор/trie имеете ввиду, да?). Но тут какая-то растянутая сова получается.

    Например, можно, действительно, все слова сложить в trie, а потом его обойти. Вам нужно будет в рекурсивном обходе поддерживать количество последних ребер, которые шли по алфавиту. Еще в каждой вершине сразу хранить, сколько раз через нее проходят добавленные строки. Тогда в каждой вершине прибавляйте к ответу произведение двух счетчиков. При рекурсивном вызове или увеличивайте счетчик последних упорядоченных ребер, если следующий символ больше символа к отцу, или передавайте 1.

    Но это нисколько не эффективнее наивного итеративного подхода, где вы это же максимальное количество упорядоченных букв поддерживаете идя по строке слева направо, сбрасывая в 0 на пробелах.
    Ответ написан
  • Не работает math.pow, что я делаю не так?

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

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

    Во-первых, удалите flag. Ужасный, отвратительный подход. Что он означает? Зачем он вам нужен? Разве нельзя обе части выполнять в цикле всегда, вместо того, что бы чередовать их очень не читаемым и запутанным методом?

    Далее, надо поддерживать какой-то инвариант. У вас там 2 переменные в цикле first и last. Что вы поддерживаете? Все элементы до first не превосходят pivot, а все после last не меньше его? Определитесь с этим и докажите себе, что после каждой итерации цикла этот инвариант сохранится. Вместо того, чтобы следить за тем, где у вас ведущий элемент, просто запомните в переменную его значение.

    Если не разберетесь, смотрите на код в википедии, например.
    Ответ написан
  • Выдает ошибку, как ее можно исправить?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Индексы в сравнении напутаны. Вы делаете один проход пузырька (как бы полусортировка) поочередно по возрастанию каждого столбца. Вместо того, чтобы сделать все проходы сравнивая один и тот же 0-ой столбец.
    Ответ написан
    Комментировать
  • Чем отличается оператор от матрицы в линейной алгебре?

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

    Линейное преобразование - это конкретный тип операторов, который действует на элементы R^n и характирезуются тем, что они обладают свойством линейности (F(x+y) = F(x)+F(y), F(kx) = kF(x)).

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

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

    У вас в таблице же даже примеры нарисованы: последние 3 строки - это комбинации пары фундаментальных разрезов. Этот символ "плюс в кружочке" - это и есть исключающее или.
    Ответ написан
  • Как сгенерировать случайные величины с заданной функцией распределения и коэффициентом корреляции??

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

    Вообще, не для любых функций распределения можно получить любую корреляцию. Например, вы никак не сможете добиться полной (corr=1) корреляции равномерно распределенной величины и нормально распределенной величины.

    Но, если функция для обеих величин одинаковая, то есть, например, такой способ:
    1) Сгенерируйте случайную величину a согласно функции распределения.
    2) C вероятностью k выдайте это же значение как и вторую переменную (b=a).
    3) C вероятностью 1-k сгенерируйте случайную величину b согласно той же функции распределения.

    Этот способ выдаст коэффициент корреляции k. Если нужна отрицательная корреляция, то можно выдать b=2Ea-a во втором шаге (отражение относительно матожидания). Но тогда в третьем шаге плотность распределения будет уже не такая же как у a. Если заданная функия распределения f(x), то там надо использовать g(x)=(f(x) -kf(2Ea-x))/(1-k). Суть в том, чтобы g(x)*(1-k)+k*f(2Ea-x) = f(x) - и итоговая плотность распределения будет одинаковая.

    Этот способ даст заданную корреляцию, но может вам не подходить, потому что там куча исходов, где обе величины равны.

    Другой вариант, сгенерировать случайную величину a ~ f(x), потом взять b = k*a+c, где c - это какая-то независимая случайная величина, распределенная как-то хитро (об этом ниже). Регулируя k можно получать разный уровень корреляции. Удобно работать уже с центрированными случайными величинами. Пусть Ea = Eb = Ec= 0.

    Тогда коэффициент корреляции будет E((ka+c)a)/D(a) = (kEa^2+Eac)/D(a) = kE(a^2)/D(a) = k. Потому что a и c независимые случайные величины и Eac = Ea*Ec = 0*0. А D(a) = E(a^2)-Ea*Ea = E(a^2)-0*0.

    Пусть функция распределения a и b - F(x) (плотность f(x)). Искомая функция для c - G(x) (плотность g(x)).

    Надо будет решить интегральное уравнение:
    Int -int..inf g(t)f((x-t)/k)/k dt = f(t)

    Лучше всего это через преобразование лапласа это решать. Теоремму о свертке и свойство умножения на число примените.
    Ответ написан
    Комментировать
  • Как сгенерировать случайную величину с заданной многомерной функцией распределения?

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

    Известно, как сгенерировать одномерную величину с заданной функцией распределения: обращаем функцию распределения (интеграл плотности) и подставляем туда равномерно распределенную на отрезке 0..1 величину.

    Пусть у вас 3 компонены x,y,z. Интегриркем по y,z, получаем функцию плотности для x. Гегерируем. Потом подставляем это значение в функцию плотности и получаем новую, уже двухкомпонентную функцию (ее еще надо будет поделить на плотность для данного x l, чтобы нормировать). Повторяем операцию для y.

    Но, как и в одномерном случае, этот метод не просто применить, если функция рачпределения сложная, или у нее интеграл просто не берется.

    В противном случае можно натягивать сетку и считать интеграллы и обратные функции численно.
    Ответ написан
    4 комментария
  • Почему не существует не итерационных/точных методов для вычисления корня из числа?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Есть же методы: https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D...

    Они обычно медленнее и более трудоемкие, поэтому из и не используют особо.
    Ответ написан
  • Как объединить списки, полученные от 2 REST API с параметрами `limit` и `offset`, и вернуть его, согласно параметрам `limit` и `offset`?

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

    Но, если вам надо обязательно вот так извращатся, то это практически задача с leetcode: https://leetcode.com/problems/median-of-two-sorted...

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

    У вас же тут надо не медиану найти, а k-ый элемент.
    У вас тут фактически дано 2 массива API1 и API2. Чтобы прочитать один (или несколько) элементов вам надо сделать запрос к АПИ.

    Вам надо найти offset-ый, offset+1 и т.д элементы в объедененном массиве.
    Для начала просто найдите offset-ый элемент. Зная его позиции в обоих массивах сделайте 2 запроса с этих
    позиций и данным limit. Потом как в задаче о слиянии двух массивов выведите первые limit.

    Во время бинпоиска делайте запросы с limit=1, а offset = индекс в массиве.

    Update:
    Забыл написать, тут у вас будет что-то около 2*log(offer+limit) запросов с limit=1 к разным апи, и потом еще 2 запроса с limit=limit из общего запроса.
    Ответ написан
    4 комментария
  • Есть ли задача на распределенные вычисления, которую легко проверить?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Берете любую NP-complete задачу: https://en.m.wikipedia.org/wiki/List_of_NP-complet...

    Все их сложно решить и легко проверить ответ.
    Ответ написан
    Комментировать
  • Как программно работать с USB веб-камерой в Linux использую C/С++?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Нужны библиотеки. Гуглите v4l2, pipewire.
    Напрямую с драйверами или тем более свой драйвер с USB протоколами вы писать замучаетесь.
    Ответ написан
    2 комментария
  • Как правильно повернуть в нужную сторону обьект?

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

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

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

    Две оставшееся точки на окружности какого-то среднего радиуса под углами с небольшим отклонением от предыдущего угла в обе стороны.

    Эти углы надо будет рассчитать на бумажке. Нарисуйте 2 коружности заданого радиуса, постройте между ними ромб, проведите его диагонали, найдете там парочку прямоугольних треугольников. В программе можно будет просто эти длины засунуть в формулы и скормить какой-нибудь atan2() функции.
    Ответ написан
    1 комментарий
  • Почему make file компилятора выдает ошибку, что функция переопределяется?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Похоже на какие-нибудь циклические инклуды.
    У вас в data_process.h случайно не включается data_process.c?
    Так делать не надо.
    Ответ написан
    6 комментариев