Задать вопрос
wataru

Wataru

Разработчик на С++, экс-олимпиадник.
Ответы

  • Кто и когда использует бинарные деревья и другие структуры данных?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Иногда вам может понадобится что-то не совсем стандартное. Например, возможность быстро вставлять элемент на k-ое место в структуре и находить, что лежит на k-ой позиции. Это делается деревом по неявному ключу, но, по моему, ни один язык не предоставляет стандартной структуры для этого.
    Ответ написан
    2 комментария
    2 комментария

  • Где собрать решение?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Есть такая штука: https://chromium.googlesource.com/infra/goma/server/

    Позволяет собирать большие проекты параллельно на куче машин. Да, эти 30 минут сборки все равно придется потратить. И никто вам бесплатно вычислительные мощности под это не даст. Придется свои сервера настраивать.

    Еще есть вариант переструктурировать ваш проект, что бы при небольших изменениях понадобилось бы собирать лишь малую часть объектников. И 2 гигабайта в одном файле - это какой-то перебор. Если вы тесты разобъете на много логически обособленных частей, то есть шанс, что сборка сильно ускорится. Да, придется запускать больше файлов, но это сделать просто.
    Ответ написан
    Комментировать
    Комментировать

  • Почему инициализация целочисленного указателя 0 или NULL не вызывает предупреждений, хотя 0 - это целочисленная константа?

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

    Но 0 - исключение. Потому что нулем принято обозначать пустой, ни на что не указывающий указатель. Обычно для этого в C используют NULL, чтобы разделять число 0 и пустой указатель в коде. Но NULL, фактически и есть 0.

    Компилятор ничего не приводит, а просто игнорирует присвоение 0, ибо это нормальная ситуация.
    Ответ написан
    1 комментарий
    1 комментарий

  • Как я могу использовать объект JavaScript в c++?

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

    Если же вы хотите эту конкретную (msg) структуру парсить, то возможно вам удасться превратить json в class в двумя string и одним int.
    Ответ написан
    Комментировать
    Комментировать

  • Как найти рекурсивным способом эйлеров путь в графе, из какой вершины начинать?

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

    Эйлеров путь существует от вершины с выходной степенью на 1 больше входной степени до вершины у которой входная степень на 1 больше, чем выходная. (Если граф неориентированный, то путь от одной нечетной вершины до другой). При этом все остальные вершины должны быть сбалансированны.

    Это элементарно доказать - путь в каждую вершину входит сколько-то раз и столько же раз выходит. Исключение - только начальная и конечная вершина, если они не совпадают.

    Соответственно, вам надо подсчитать степени всех вершин, проверить что все хорошо (максимум одна с in==out+1 и одна с in==out-1) и запустить или от любой или от той, у которой исходящих ребер больше.
    Ответ написан
    Комментировать
    Комментировать

  • Как замерить частоты тактов, отводимых на операцию в C?

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

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

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

  • Что здесь написано?

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

    Если итератору присвоить значение (it = 10;), то оно остается в памяти, при сдвигании итератора вперед (it++;) это значение записывается в выходной файл и следующее присвоение скормит итертору значение в следующей позиции. Этот итератор сделан, чтобы можно было писать в файл, как в C++ коллекцию (например, в вектор).

    Важно, что у этого итератора оператор * ничего не делает, возвращает сам итератор. Оператор присвоения, кстати, тоже возвращает сам итератор.

    Поэтому конструкция *(val%2 ? OddOut : EvenOut) вернет или итератор OddOut или EvenOut в зависимости от четности val. Далее, конструкция (... = val)++; запишет число val в один из выходных итераторов и сдвинет его на позицию вперед.

    Весь код выше создает 2 output_iterator, для двух заданных файлов. Потом for_each через оператор() у класса скармливает ему входные числа из cin (тут работает istream_iterator, который позволяет читать из файлов, как из вектора). А класс, пользуясь конструкцией выше, записывает числа в один из двух файлов в зависимости от четности.
    Ответ написан
    Комментировать
    Комментировать

  • Как Вы обходитесь без "if"?

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

    Но пока похоже, что вам нужена конструкция switch.
    Ответ написан
    Комментировать
    Комментировать

  • Как исправить ошибку в реализации перегруженных функций?

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

    Тут вы присваиваете переменной res1 значение true и потом смотрите на ее значение в условии.

    Это вызвано тем, что оператор присврения возвращает значение переменной. Т.е. (res1 = true) == true. Если это вставить в if, то это то же самое что if(true).

    Для сравнения нужно использовать "==".

    Но, вообще говоря, if(res1 == true) - очень плохой код. Правильно писать if (res1).
    Ответ написан
    Комментировать
    Комментировать

  • Почему не работают хеши?

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

    И xhash и gethash написаны с ошибками.

    Давайте посмотрим на xhash. Если l==r, то вернется s[l]*1. Вроде правильно. Если l+1=r, то ваша функция вернет s[l]*p^2+s[l]*p+s[r]. Вряд ли это то, чего вы хотели добиться. Или инициализация перед циклом неверная, или границы у цикла.
    Ответ написан
    17 комментариев
    17 комментариев

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

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Это известная и сотню раз решенная задача. Гуглите "exponential backoff" или "Экспоненциальная выдержка".
    Ответ написан
    4 комментария
    4 комментария

  • Какие есть алгоритмы сортировки и поиска с помощью деревьев?

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

    Теоретически, можно любое search tree использовать, но оно будет медленее, потому что структуры сложнее.
    Ответ написан

  • Где и как используют деревья в программировании?

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

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

    Еще деревья часто используются в алгоритмах на строки. Есть такая структура - бор (trie) - позволяет эффективно хранить кучу строк и искать: есть ли такая строка в структуре. Более продвинутые алгоритмы типа Ахо-Корасика, Укконена тоже строят некоторое дерево с дополнительными фишками и позволяют делать крутые вещи, типа искать кучу шаблонов в тексте разом, или моментально находить самую часто встречающуюся подстроку задонного размера.

    Куча (heap) используется для сортировки а так же реализации приоритетных очередей.

    Далее, деревья в смысле графов тоже используются, например, в сети. Маршрутизаторы строят остовное дерево и раздают команды по его ребрам.
    Ответ написан
    Комментировать
    Комментировать

  • Какую структуру данных выбрать для подсчета элементов?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Вам нужен std::map или std::unordered_map. Самому писать структуру данных не надо.

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

    В качестве ключа используйте пару {Тип транспорта, номер маршрута}. В качестве значения - счетчик остановок.

    Еще вам нужен еще один map из тип транспорта-> std::set или std::unordered_set номеров маршрутов.

    Для построения структур один раз приходитесь по всем остановкам и увеличивайте счетчик в первой структуре. Добавляйте маршрут к транспорту во второй структуре.

    Для поиска ответа пройдитесь циклом по всем элементам set из второго map - это все маршруты. Смотрите в первом map'е сколько остановок у этого маршрута и выбирайте максимум.
    Ответ написан
    2 комментария
    2 комментария

  • Алгоритм работает не правильно?

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

    Вы же как-то пытаетесь реализовать это только лишь с переменной mid. Если надо идти влево, то вы делите mid пополам, как будто бы текущий отрезок от начала массива (Но это не всегда так: после первого же шага вправо начало массива будет уже выкинуто из расмотрения), Потом, при переходе вправо, у вас какой-то бред написан.
    Math.floor((arr.length - mid) / 2) - это что вообще должно делать? Если mid=9, length = 10, вы вообще уйдете в начало массива, хотя должны идти вправо. Если вы хотели взять середину между mid и length, то там должен стоять "+" внутри.

    Но так все-равно не получится сделать. Заведите 2 переменные l и r, как во всех реализациях бинпоиска, считайте mid как середину отрезка, и при выбрасывании одной из половин просто переписывайте l или r на mid+1 или mid-1 (потому что сам mid элемет вы уже рассмотрели и он точно не нужен).
    Ответ написан
    1 комментарий
    1 комментарий

  • Как вычислить сумму первых N элементов ряда?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Вам уже дана формула n-го элемента.
    В формуле, похоже, опечатка. Должно быть -1 в начале (если подставить n=0).
    Но это не особо важно, все равно первые члены ряда считаются отдельно.

    Соответственно, можно считать текущий элемент через предыдущий, как вы пытались:
    a_k = a_(k-1)*(-x)*(2k+1)/(2k-1)/(2k-1)/(2k-2)

    Только она не работает для k=1. Поэтому 2 первых члена ряда надо прибавить руками, а остальное в цикле i=2..n-1

    Т.е. R вам не нужен, и в коде должно быть:
    u = 1+3*x;
...
  u *= (-x)*(2i+1)/(2i-1)/(2i-1)/(2i-2);
  summa += u;


    Да, еще стоит разобрать крайние случаи, если n =0, то надо отдельно вывести 1 (или -1, если мы исправляем опечатку).
    Ответ написан
    4 комментария
    4 комментария

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

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник. 
    print ([("small" if a < 20 else "medium") if a <=30 else "large" for a in a_random])
    Ответ написан
    5 комментариев
    5 комментариев

  • Как построить симуляцию луча?

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

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

    Отражения, если вам так хочется, можно делать через вектора. Есть у вас вектор вдоль луча, и вектор вдоль зеркала и нормаль внутрь. Через скалярное произведение можно разложить вектор луча на перпендикуляр и паралледьный к зеркалу. Потом надо развернуть вектор перпендикуляр и сложить их.

    Но в этой задаче это вам не поможет никак - ибо симулировать эти 100500 отражений и квантилионы возможных начальных углов никакого времени не хватит.
    Ответ написан
    2 комментария
    2 комментария

  • Как перебрать ходы в двухмерном пространстве?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Можно. Задача решается за O(n^2) динамическим программированием.

    Считайте F(x,y) - лучшую возможную сумму, чтобы закончить в ячейке (x, y).

    База: в левом нижнем углу ответ - число в этой ячейке; за границами - ответ минус бесконечно плохое число (плюс бесконечность, если ищем минимум, например).

    Пересчет F(x,y) = a[x,y] + min(F(x+1,y), F(x,y-1)) - выбираем, с какой стороны выгоднее прийти в эту ячейку.
    Ответ написан
    Комментировать
    Комментировать

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

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Вам надо сделать виртуальное ethernet устройство. Пришедшие на него пакеты надо оборачивать в какой-то ваш протокол, шифровать и посылать дальше на сервер. Сервер же полученные пакеты распаковывает и посылает на внешний интерфейс, подменяя IP адрес отправителя и порт на свои собственные. Пришедшие на этот адрес/порт пакеты сервер оборачивает, подменяет там адрес с портом и посылает назад клиенту. Клиент распаковывает и выдает в систему через виртуальное устройство.
    Ответ написан
    1 комментарий
    1 комментарий