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

    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 комментариев
  • Как правильно удалять элементы хэш таблицы?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Никак. Конечно, можно проверить, что там дальше ячейка пустая через k*k для всех возможных k (или что ячейка на (k-1)^2 назад пуста), но это слишком долго. И не сработает во всех случаях. Поэтому так и не делают вообще. Обычно "удаленные" значения убирают при перехешировании, которое все-равно придется делать при достаточном заполнении таблицы.
    Ответ написан
    3 комментария
  • Возможно ли присвоить «ничего» в ссылку?

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

    В вашем коде 2 проблемы. = default; можно писать, если у вас нет никакого списка инициализации. И константную ссылку нельзя использовать для инициализации неконстантной.

    Вот такой код компилируется:
    template<typename T>
    struct Test
    {
        T& ref;  // нужно присвоить null
    
        Test(T& _ref) : ref(_ref) {};
    };
    Ответ написан
    3 комментария
  • Как использовать целое число с размером больше чем 64 бита в C++?

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

    Если надо делить нацело или брать по модулю маленького числа (<64 бит), то тоже элементарно - один цикл по цифрам числа.

    Если же вам большое число надо делить на большое, то там чуть сложнее: надо будет деление в столбик реализовать. Это не высшая математика, но чуть-чуть подумать придется.
    Ответ написан
  • В чем причина ошибки IndentationError: unexpected unindent?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    IndentationError: unexpected unindent
    означает, что форматирование файла кривое. Скорее всего, табы вместо пробелов или наоборот в 22 строке. При форматировании не то вставили. Выглядеть оно может правильно, но питону важно, чтобы все было идентично.

    В питоне количество пробелов/табов в начале строки управляет вложенностью конструкций.
    Имеет значение не только количество табов/пробелов в начале строки, а их точная последовательность.

    Поэтому рекомендуется во всем файле использоваать или только табы, или только пробелы.
    Ответ написан
    Комментировать
  • Как доказать, что a³+b³+c³=3?

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

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

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Нет. Ну, только если вы не будете заводить таблицу на 4 миллиарда с копейками элементов (2^32) и использовать тривиальную хеш-функцию.

    Потому что важно не столько количество элементов в таблице, а их значения. Их может быть 4 миллиарда различных. И даже только с 2 элементами я вам для любого меньшего размера таблицы найду 2 таких элемента, что у них хеш функция совпадет.

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

    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 вдоль луча и дальше получите то же самое квадратное уравнение.
    Ответ написан
    2 комментария
  • Как максимально быстро найти в диапазоне 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 вот дизайнеры этих кодов были довольно умные дяденьки, поэтому английский алфавит идет там по порядку одним блоком.
    Ответ написан
    Комментировать