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

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

    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 миллиарда айпишников в отдельные записи - вообще не работающая идея.
    Ответ написан
    Комментировать