• Как сделать взаимодействие между несколькими процессами?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Это называется IPC (inter-process communication). Гуглите IPC + ваш язык программирования, что-то да найдете. Полно библиотек готовых. Есть способы по-производительнее сокетов (всякие отображаемые в память файлы, например), но велосипед тут переизобретать смысла нет, если это только не задание на курсе по программированию.

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

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

    Обозначьте |MSL_VEL - TGT_VEL| за t.

    Получите уравнение TGT_DIR = (MSL_VEL-TGT_VEL)/t

    Преобразуйте: TGT_DIR*t = (MSL_VEL-TGT_VEL)

    Но тут неизвестные вектор MSL_VEL и t. Но они связаны, ведь t - это длина вектора. Обозначим неизвестный вектор MSL_VEL как (x, y, z) Значит:
    t^2=(x - TGT_VEL_x)^2 + (y - TGT_VEL_y)^2 + (z - TGT_VEL_z)^2

    Ну и еще вы знаете, что скорость ракеты фиксированная же:
    x^2+y^2+z^2 = MSL_SPEED^2

    У вас тут 4 неизвестных и аж 5 уравнений (ведь первое - это векторное уравнение):
    TGT_DIR_x*t = x - TGT_VEL_x
    TGT_DIR_y*t = y - TGT_VEL_y
    TGT_DIR_z*t = z - TGT_VEL_z
    t^2=(x - TGT_VEL_x)^2 + (y - TGT_VEL_y)^2 + (z - TGT_VEL_z)^2
    x^2+y^2+z^2 = MSL_SPEED^2


    Раскройте скобки в 4-ом, подставьте туда пятое и из первых трех выразите x, y, z:

    t^2 = MSL_SPEED^2+TGT_SPEED^2-2*TGT_VEL_x*(TGT_DIR_x -t*TGT_VEL_x)-... = MSL_SPEED^2+(1-2t)TGT_SPEED^2-2(TGT_DIR*TGT_VEL)


    Там в конце векторное произведение векторов. Дальше сами раскройте и получите квадратное уравнение на t. Решите его по школьной формуле. Если дискриминант отрицательный, то решения тупо нет. Слишком быстро цель улепетывает. Потом не забудьте проверить, чтобы t получилось положительное. Потом подставьте t в первые 3 уравнения и найдите искомые x, y, z.

    Еще можно так себе это все представить. Свяжем систему координат с целью. Тогда множество точек, куда может смотреть скорость ракеты - это сфера с центром в TGT_VEL и радиусом MSL_SPEED. Вам надо выбрать на этой сфере точку так, чтобы она была коллинеарна с вектором TGT_DIR. Т.е. у вас есть луч из центра координат вдоль векторо TGT_DIR. Вам надо найти где он пересечет сферу. Введите параметр t вдоль луча и дальше получите то же самое квадратное уравнение.
    Ответ написан
    Комментировать
  • Как максимально быстро найти в диапазоне IP-адресов или подсетях нужный IP-адрес?

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

    Поэтому вам надо лишь эти префиксы в trie сложить, а в вершине сохранить саму запись. При запросе надо спускаться по битам айпишника в trie, пока не упретесь в лист - вот он и соответсвтует искомому диапазону.

    Если хотите использовать существующие БД, то можно сохранить в любой реляционной базе данных начала диапазонов. По запросу IP вам надо найти последнюю стороку не больше его. Буквально
    where range_start <= IP order by range_start desc limit 1
    .

    Смотрите только аккуратно, что сравнивать их надо как битовые строки/32-битные числа, а не просто как строки. Ибо должно выполнятся 127.0.01 > 8.8.8.8. Сравнение как строки же не сработает. Или храните как битовые строки, или преобразуйте в числа, или нулями отбивайте октеты, короче трех символов.

    Раскрывать все 4 миллиарда айпишников в отдельные записи - вообще не работающая идея.
    Ответ написан
    Комментировать
  • Как мне продолжить сокращать формулу?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Два наблюдения:
    1) изначальная формула имеет вид (a=>b)*(b=>a).
    2) b = !a

    Отсюда в одно действие видно, что она вырождается в ложь: (a=>!a)*(!a=>a)

    Для второго наблюдения надо применить какой-то там закон, что !x+xy=!x+y
    Ответ написан
    4 комментария
  • Как создать многомерный массив в одной области памяти?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Есть еще 2 варианта:

    1) Используйте std::vector<std::array>.

    2) Что-то среднее между двумя вариантами у вас: как и везде, у вас есть одномерный массив для данных. А operator[] на классе возвращает int* на первый элемент в строке. То же, что у вас, только не надо никакого вспомогательного класса. Таким образом двойная индексация будет работать как надо. Но, как и во втором упомянутом вами примере, тут не будет проверки выхода за границы массива.
    Ответ написан
    Комментировать
  • Как выбрать диапазоны значений по вхождению значения в диапазон?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Дерево интервалов. Оно же interval tree.

    Оно как раз позволяет быстро искать все отрезки, пересекающие данную точку, но изменять его очень тяжело. Хорошо, что вам это и не надо.
    Ответ написан
    Комментировать
  • Всё ли в порядке с данным блоком?

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

    Во-первых, он не компилируется. У вас там названия переменных кое где из двух слов состоят (А в других местах те же переменные с '_' идут - явно кто-то ошибся при перепечатывании текста).

    Во-вторых, тут подход немного через пятую точку. Не нужна вам строка из алфавита. Чтобы получить случайный символ, можно случайное число от 0 до 25 прибавить к 'a' - ведь символы в C++ - это целочисленные переменные, хранящие ASCII коды букв. B вот дизайнеры этих кодов были довольно умные дяденьки, поэтому английский алфавит идет там по порядку одним блоком.
    Ответ написан
    Комментировать
  • Сокращение функций в си++?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Нет.
    Ответ написан
    3 комментария
  • Не фиксируемое количество аргументов 1 типа в c++?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    На выбор: std::initializer_list, variadic arguments, variadic templates.

    Примеры по ссылкам есть. Последнее - вообще оверкилл, и в вашем случае вообще не нужно. Советую использовать initializer_list.
    Ответ написан
    1 комментарий
  • Как реализовать приоритетную очередь с функциями extractMax и add, которая поддерживает одинаковые элементы?

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


    Если нумерация массива идет с 1, то два ребенка элемента i будут 2*i и 2*i+1. У вас же нумерация с 0, т.ч. у вас дети - 2*i+1 и 2*i+2.

    Первое условие достигается правильной расстановкой строгого и нестрогого неравнества в условиях в алгоритме.

    Похоже, проблема в том, что у вас нумерация с 0 и, если новый элемент оказывается итак максимальным, вы вернете индекс 0, вместо нужного 1. Если вы элемент вниз просеиваете, то у вас там +1 стоит в res.first, но изначально у вас-то там 0.

    Далее, вы вектор неправильно используете. Вы делаете reserve и потом работаете с пустым вектором, как-будто он фиксированного размера. Вам надо делать resize вместо reserve. Или еще лучше, вместо вашей переменной size вы используйте arr.size(). При изменении размера массива делайте pop_back() и push_back().
    Ответ написан
    8 комментариев
  • Ошибка в конструкторе при передаче массива c++?

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

    Вот так работает:
    int data[] = {90, 90};
    Array<int, 3> arr (data);


    Ну не может компилятор по Array<int, 3> arr { 90,90 }; догадаться, что {90, 90} - это числа в массиве, адресс которого надо передать.

    Кстати, у вас тут ошибка: Array вы создали на 3 элемента и копируете 3 элемента, а данных задали только 2.
    Ответ написан
  • Почему неправильно решает задачу?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Небольшое замечание: можно код сильно ускорить, применяя математику. Можно взять все номера букв по модулю 26, тогда a=1, ... y=25, z=0. Тогда операция будет - умножение на 2 и взятие по модулю 26 (для 'a' все также выдаст 'b', для 'z' все так же выдаст 'z'). До этого можно додуматься, потому что вот это вот "вычитание 26" - ну очень похоже на операцию взятия по модулю 26.

    Применение этой операции 2024 раза равносильно умножению на 2^2024 по модулю 26. Воспользовавшисть теоремой эйлера, это равносильно умножению на 2^(2024 % 12) = 2^8 = 128. Далее, умножение на 128 по модулю 26 равносильно умножению на 24.

    Т.е. можно умножать один раз на 24 вместо 2024 умножений на 2 (и в конце взять по модулю 26).
    Ответ написан
    Комментировать
  • Как использовать двусвязный список в Buddy аллокаторе?

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

    Только надо поддерживать еще указатели на buddy. Т.е. тут что-то вроде трех-связного списка будет. При освобождении бока, если видите, что его buddy свободен, то удаляете его их обоих из списка и "освобождаете" удвоенный кусок.

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

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

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    На винде? Кроме gdi+ можно ещё через directx (гуглите dxgi duplicator) или через windows graphics capture api. Но последние 2 не работают в старых системах.

    Если же вам только посмотреть на несколько пикселей, то можно и в gdi+ делать скриншот лишь маленькой части, или вообще ничего не копировать и смотреть на цвет пикселей в экранном DC.
    Ответ написан
    1 комментарий
  • Правильно ли я дал описание для диаграммы?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Нет. В вашу формулу подойдет и верхний треугольник между A и B.
    Ответ написан
  • Как ускорить поиск элементов из статичного string[] по подстроке?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Сначала объедините все ваши строки в одну через какой-то раздилитель, которого не может быть в искомой строке (можно и без него, но с ним код чуть проще будет). В конце поставьте этот же разделитель 2 раза. Вроде "строка1$строка2$строка3$...$строкаN$$".

    Вот уже ваша задача - быстро искать какую-то остроку в фиксированном тексте, а не куче строк.
    Тут есть много вариантов. Например, постройте суффиксное дерево алгоритмом Укконена. Вот эта ваша структура. При запросе, как в боре, поищите искомую строку в этом дереве. Если где-то перехода нет - вхождения вы не нашли. Если вы остановились на какой-то вершине (или ребре в дереве), то вам осталось каким-нибудь обходом в глубину найти все листья в поддереве этого места. Каждый лист соответствует вхождению. Еще при построении суффиксного дерева вы каждый лист пометите началом суффикса. Можно в тот же момент место в строке и конкатенаций перобразовать в номер исходной строки (например, бинпоиском по индексам начал строк в тексте. Или просто заведите массив, где для каждого символа в тексте при построении запишите, какая изначальная строка там была).

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

    Другой вариант - через преобразование Барроуза — Уилера. Вот есть лекция. Этот алгоритм часто упоминается в курсах по биоинформатике. Реализацию может даже найдете где-то. Потом можно найти номера исходных строк из индексов вхождений через тот же бинпоиск по сортированному массиву индексов начал всех строк в тексте.

    Да, проблема тут будет, если у вас шаблон короткий, то вы найдете все вхождения, включая повторы в каждой из исходных строк. Тогда эти алгоритмы могут работать не сильно лучше наивного.

    Учтите, что построение структуры данных тут будет в несколько раз медленнее простого for+Contains. Выигрыш вы получите, если у вас текст действительно статичный и вы в нем много раз что-то ищите.
    Ответ написан
    7 комментариев
  • Какой тип бинарного дерева используется для Buddy аллокатора?

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

    Его можно вообще без указателей реализовать в массиве. У блока с номером i два ребенка с номерами 2i+1 и 2i+2.

    Можно вообще битовый массив использовать для пометок.
    Ответ написан
    Комментировать
  • Как правильно сделать граф?

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

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

    srand устанавливает состояние генератора псевдослучайных чисел. В качестве seed вы там используете количество миллисекунд, которое целую миллисекунду одинаковое, поэтому состояние генератора у вас в каждой функции rand_offer одно и то же - поэтому числа и генерируются одни и теже. sleep(1) лечит проблему потому, что следующий вызов посчитает другое значение count_ms.
    Ответ написан
    Комментировать