• Как сделать дерево объектов из массива?

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

    Заведите мап объектов, которые будете собирать. Ключи будудт айдишники, а значения - объекты. У объектов заполните uid, parentUID, пустой Map children и пустой список children_list. Так же запомните куда-то id, у которого null отец.

    Потом еще одним проходом по списку всех элементов заполните children_list у всех обхектов в Map из прошлого шага (кладите текущий id в список для parentUID).

    Потом еще одним проходом по всем элементам этого Map соберите дерево: обойдите список детей и в Map children кладите 'id' => объект из внешнего Map'а по данному ключу. После прохода можно children_list удалить.

    Если я правильно понимаю, как работает JS, то у вас будет не копироваться объект а его ссылка. В итоге в Map будут осодержаться вообще все поддеревья ссылыющееся друг на друга. Можно потом вырвать оттуда объект по ключу id корня и Map удалить.
    Ответ написан
    Комментировать
  • Является ли хорошей практикой использование Stack Trace библотек в дебаг сборке?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Это нормальная практика. Например, ваш браузер скорее всего именно таким инструментом пользуется (если он на хромиуме основан).
    Ответ написан
    9 комментариев
  • Есть ли алгоритм разложения матрицы?

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

    Единственная проблема - надо переставлять строчки местами. Тут вам поможет класический пазл о помене двух чисел без использования вспомогательных переменных:
    a = a + b;
    b = a - b;
    a = a - b;


    Эти три операции поменяют местами a и b. При чем они уже выглядят как трансвекции - только вторая операция не совсем вида a += b*k.

    Но можно чуть чуть поменять:
    a = a + b;
    b = b - a;
    a = a + b;


    Тут три трансвекции и строки меняются местами, только одна из них домножается на -1. Но это домножение метод гауса нисколько не меняет.

    Вот и ваш алгоритм.
    Ответ написан
    Комментировать
  • Трёхмерный массив с разными размерами внутренних массивов?

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

    Еще можно хранить ваши массивы как указатели в одном массиве указателей. Ведь эти сишные массивы - это по сути и есть указатели на начало. Вот только в таком виде вам придется как-то где-то помнить их размеры и вручную высчитывать индексацию в виде a[i*6+j], b[i*7+j].
    Ответ написан
    1 комментарий
  • На чём написан язык программирования C?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Учтите, что язык программирования - это просто набор спецификаций и правил. Он написан на английском языке.

    Если же вас интересует на чем запрограммированы компиляторы языка С, то самые популярные нынче развивающиеся компиляторы написаны на C и C++ соответственно:
    gcc: https://github.com/gcc-mirror/gcc
    clang: https://github.com/llvm/llvm-project/tree/main/clang

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

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

    А так, наверно, есть куча неподдерживаемых устаревших компиляторов Си на всевозможных языках.
    Ответ написан
    2 комментария
  • Как посчитать значение счетчика со сбросом?

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

    Один вариант решения - прибавлять к текущему числу 65536, пока оно меньше предыдущего. Можно обойтись арифметикой:

    a[i] += ceil((a[i-1]-a[i])/65536)*65536

    Только проверьте, что в вашем языке ceil(-0.5) даёт 0, иначе надо отдельно проверять случай, когда последовательность возрастает в начале и прибавлять ничего не надо. И ещё, тут считается, что числа в неурезанной последовательности могут повторяться. Если нет, то надо отдельно рассмотреть случай равных чисел в итоге и ещё раз прибавить 65536.
    Ответ написан
    Комментировать
  • Почему программа постоянно выводит 0? Как исправить?

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

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

    Работать это будет O(nm) - быстрее никак.
    Ответ написан
    Комментировать
  • Как переопределить операторы != и == в с++ для структуры?

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

    Но вообще-то раз вы итерируетесь по списку, вы сравниваете итраторы, а не структры. Поэтому достаточно просто использовать страндартную конструкцию:
    for (auto it = requests->begin(); it != requests->end(); ++it)


    И не надо ничего переопределять. Вы перепутали end и back. Первый возвращает итератор, а второй - элемент.
    Ответ написан
    2 комментария
  • Как найти сумму чисел на нечетных позициях после сортировки массива?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Никак. Есть методы получить число, которое будет стоять на заданной позиции (или числа на отрезке) в отсортированном массиве быстрее сортировки (алгоритм QuickSelect). Как-то быстрее сортировки найти все числа на нечетных позициях - нельзя.

    Edit: Если стандартная сортировка не работает и L большое, то стоит посмотреть в сторону radix sort. Если бы L было относительно небольшим - то лучший вариант был бы сортировка подсчетом.
    Ответ написан
  • Как можно найти центроид четырёх точек ( Quadrilateral ), зная координаты этих вершин?

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

    Сначала надо триангулировать четырехугольник. Потом, центр масс каждого треугольника - среднее арифметическое координат. Далее, остается найти центр масс двух точек - центров масс треугольников, где в каждой точке лежит масса равная площади треугольника.

    Чтобы это работало и с невыпуклыми многоугольниками надо считать площадь треугольников через векторное произведение сторон, разрешая таким образом отрицательные площади у треугольников снаружи вашей фигуры.

    Итоговая фромула (в векторах):
    C = ((p1+p2+p3)/3*(p1p2*p1p3)+(p3+p4+p1)/3*(p1p3*p1p4))/((p1p2*p1p3)+(p1p3*p1p4))


    Тут pi - i-ая вершина четырехугольника, pipj - вектор между точками i и j. pipj*pkpl - векторное произведение двух векторов.
    Ответ написан
    Комментировать
  • Не получается найти пересечения multiset, в чем проблема?

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

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

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

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Если бы вы использовали нормальные имена переменных, то вам бы сразу стало очевидно, какую одну строчку (даже один символ!) надо изменить, чтобы стали удалятся слова без буквы, вместо слов с буквами.

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

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Перебирайте a и b. Потом смотрите, какие значения может принимать c, чтобы ограничения выполнялись. Это будет отрезок чисел. Их не надо перебирать - можно их сразу все подсчитать. Например, если вы видите, что c<=10 удовлетворяет ограничения, то троек с текущими a, b - десять штук.
    Ответ написан
  • Как сделать компилятор СИ на джаве?

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

    Нужно понимать ассемблер, иметь знания по теории компиляторов (есть много книг), теории языков.

    Если же вам надо просто прикрутить компиляцию к вашему редактору, то, как многие другие IDE, вам надо будет лишь запускать сторонний компилятор (будь то gcc, clang, visual studio или что-то другое).

    У всех них есть консольное приложение которому можно передать файлы в качестве аргументов в коммандной строке. Вам остается лишь разобраться, как запускать приложения на Java.
    Ответ написан
    3 комментария
  • Как в vector на си вставлять элемент на конкретное место?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Сначала через memmove надо сдвинуть элементы с i по count-1 на позиции i+1...count. Потом чуть изменить memcopy, чтобы записать новв элемент на позицию i, а не count.
    Ответ написан
  • Как реализовать битовую матрицу оптимально по памяти?

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

    Для матрицы NxM бит (i,j) будет лежать в (i*N+j)/8 ячейке массива. Номер бита - надо взять остаток от деления на 8.

    Можно получить любой бит и можно что угодно делать с матрицей.
    Ответ написан
    Комментировать
  • Последнюю строку массива мне выводит очень много раз, в чем проблема?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Если вы повнимательнее посмотрите на свой код, то заметите, что там вывод массива a происходит в цикле while(n>k). Где именно ошибка - непонятно, ибо неясно, что ваш код должен делать. Или вы вывод массива вставили не туда, или GetComb делает что-то не то и цикл исполняется больше раз, чем должен.
    Ответ написан
  • Как определить класс, которому принадлежит вызываемый метод, из C++ кода?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Попробуйте __pretty_function__ в gcc и __FUNCSIG__ в visual studio.
    Ответ написан
    1 комментарий