Задать вопрос
  • Можно ли восстановить дерево хаффмана с помощью стэка?

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

    Можно вместо рекурсии использовать стек вручную.

    Edit: а вручную будет примерно так: Читаем бит. Если 0, то кладем в стек 0. Если 1, то текущий стек - код симола по следующим 8 битам и удаляем из стека все 1 сверху до первого нуля. Нуль меняем на 1.
    Правда это даст не дерево а только коды символов. Чтобы получить дерево надо будет в стеке хранить указатели на вершины.
    Ответ написан
  • Как найти все завершённые пути на карте?

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

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

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

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

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

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

    Когда подберете параметры, функция будет вычислятся кусочно. Сначала найдите к какому отрезку относится текущее время (или тупо циклом или набором if-else, или, если сделаете отрезки одинаковым количеством часов, то можно поделить время на длину отрезка и округлить вниз, чтобы получить номер отрезка). Потом вычислите значение нужного сплайна, что будет просто вычислением полинома второй или третьей степени.

    Ну, или можете просто задать нексолько ключевых значений, и проинтерполировать полиномом лагранжа. Правда тут сложно будет заставить его идти именно как вам хочется. Через точки-то он точно пройдет, но вот между ними может иметь какие-то левые пики и изгибы. Так что придется поэксперементировать. Можно поиграться, например, в wolframalpha.com (введите "interpolating polynomial calculator", потом задайте значения функции в точках и получите и график и формулу. Ссылку дать не могу, qna ссылки на wolfram банит за одно со спамерскими ссылками по ошибке).
    Ответ написан
    Комментировать
  • Почему base64 увеличивает длину строки?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Почему при переходе из 16-значной системы в 64-значною длинна строки увеличилась, а не уменьшилась?


    Потому что на самом деле у вас переход из 256-ричной системы в 64-ричную. Base64 позволяет кодировать любые строки, а не только из 16 символов 0-9,a-f.

    Если вы хотите вашу строку интерпретировать как 16 запись, то вам надо ее сначала из hex записи раскодировать. Гуглите HexToBase64, hexToAscii или HexDecode. Какая нибудь такая функция наверняка есть в библиотеке. Или ее можно самостоятельно написать, превращая по 2 символа в 1.

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

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

    Это значит, что вы из какой-то функции раньше вернули указатель на локальную переменную и получили висячий указатель.
    Ответ написан
    1 комментарий
  • Как построить блок схему?

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

    Может вместо конструкций C++ типа cin, cout, printf надо использовать псевдокод. Типа "ввод x"
    Ответ написан
    5 комментариев
  • Как решить олимпиадную задачу с графами?

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

    Вам надо только понять какие вершины в цикле, а какие на черенке. Тут можно обходом в глубину или ширину это найти. Или даже тупо циклом. В графе есть одна вершина степени 1 - она же выезд. От нее надо идти к соседним, пока не дойдете до единственной вершины степени 3. Пройденные так вершины будут черенком. Остальные - в цикле.

    А дальше вам надо посчитать длины трех маршрутов и выбрать из них лучший.
    Ответ написан
    Комментировать
  • Как реализовать алгоритм экспайринга элементов в базе данных?

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

    По нормальному, это должен быть один поток с приоритетной очередью, который работает постоянно.

    Он должен спать, но при получении сообщения о новой таске просыпаться, добавлять время в которое истекает следющая таска в приоритетную очередь и потом засыпать на время до минимального в приоритетной очереди.

    Когда идет пробуждение по таймеру (или вообще в любое время), то надо посмотреть, а не пора ли уже какие-то таски удалить по времени и убрать из из приоритетной очереди.

    Обычно такое реализуется через какой-то примитив событий: не знаю, что там есть в go. Должна быть функция ожидания события с таймаутом. Вот там надо ждать события, которое выстреливает при добавлении новой таски пользователю, а таймаут должен браться из приоритетной очереди.

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

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Попробуйте константу ascii уведичить до 256. Русские буквы в cp1251 идут во второй половине алфавита.

    Edit, ну и тип строки unsigned char надо. А то к отрицательным индексам будет доступ.
    Ответ написан
  • Как специализировать метод родительского класса?

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

    Определите shader::construct и пометьте override.
    Ответ написан
  • Как использовать переменную из одной функции в другой, не запуская при этом работу второй функции?

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

    Вы там выделяете новую память и заполняете ее, но снаружи это нигде не видно.

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

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

    Поэтому симплекc метод тут никак не поможет. Это задача квадратичного программирования, в лучшем случае.

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

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    int index = std::distance(NUMBER.begin(), it);
    TYPE.erase(TYPE.begin() + index);
    PRICE.erase(PRICE.begin() + index);
    ...


    Вы же удаляете элемент по индексу равному значению удаляемого элемента.

    Я бы, правда, вместо кучи массивов завел один массив со структурами. Это сильно упростит код, хоть и может в некоторых крайних случаях работать чуть медленее.
    Ответ написан
    1 комментарий
  • Как объединить/увидеть пересечение множеств через цикл?

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

    Ну так для объединения надо вывести все множество B и только ту часть A, которая не в пересечении.
    Ответ написан
  • В чем преимущества процессов над потоками?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Главное приемущество: независимость процессов. Потоки делят между собой одну память и ресурсы системы (всякие хандлеры в винде, например).

    Если один из процессов завершится или, что чаще происходит, упадет - остальные не будут затронуты. Плюс эта независимость позволяет делать песочницы для безопасности. Так, все современные браузеры запускают js и вообще каждую вкладку в отдельном процессе. Даже если куллхацкер полностью взломает браузер через специальный сайт, он окажется в процессе, который особо прав никаких не имеет, библиотеки особо интересные туда не загружены, а все общение с внешним миром - через жестко прописанные протоколы ipc (inter-process communication). Так что злодею придется взламывать еще и их.

    Эта же независимость позволяет выполнять работу даже после завершения основного процесса. Так, если вы хотите сделать автообновятор программы, то после скачки/установки нового приложения, надо будет перезапустить основное приложение, чтобы перезаписать исполняемый файл (по крайней мере в винде). Но поток завершится вместе с программой и кто же тогда потом будет ее запускать? А вот процесс останется работать.

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

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

    Соответственно, чтобы вернуть пустой массив, надо вернуть массив длины 0. Ваша функция же как-то должна возвращать длину массива? Вот точно также, как если бы длина была 1, только 0. Или сразу первым элементом идет маркер конца массива. Или переменная длины, которую, скорее всего, придется сделать out параметром функции, будет содержать 0. Или можно NULL возвращать, как особый случай, что ничего нет.

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

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Он там не вызывается. Этот приватный конструктор используется в функции
    void lib::LinkedList<T>::push(const T&) [with T = Item<int>]
    , которая в шаблоне (там где вы создаете Node* tmp). При первом обращении к этой функции компилятор пытается ее инстанциировать и натыкается на эту проблему, о чем и сообщает вам. Пока эта функция вообще никак нигде не используется - программа компилируется.

    В приведенных вами примерах вы эту функцию так или иначе трогаете разными способами.

    lib::LinkedList<Item<int>> list = lib::LinkedList<Item<int>>()
    вызвает проблему пока у вас есть virtual метод в интерфейсе, потому что это тут вызывается конструктор копирования (сначала конструктор по умолчанию для временного lib::LinkedList<Item<int>>(), а потом это все копируется в конструируемый list).

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

    Если вы напишите lib::LinkedList<Item<int>> list() - то все скомпилируется, потому что конструктор по умолчанию, видимо, не требует знания о методе push. Также удаление virtual или наследования вылечит эту проблему.

    Далее, точно по этой же причине не скомпилируется list.push(a) - это прямой вызов этой запретной функции. Если же вы напишите list.push(Item<int>()), то оно скомпилируется потому что тут вызывается push с перемещением.

    Но для исправления этого кода вам надо прежде всего избавится от этой поломанной функции push.
    Ответ написан
    3 комментария
  • Какой open source проект написан на труъ Си++?

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

    Но вряд ли просмотр стороннего кода поможет вам понять, что именно коллегам не нравится в вашем коде. Тут надо все-таки коллег допытываться. Смотреть на ими написанный код.

    Если постоянные жалобы, то устройте код ревью в команде. Пусть ваш код хотя бы пару неделек кто-то постоянно будет проверять перед комитом и выдавать конкретные правки (а вообще код-ревью хорошо использовать всегда. Тот же github дает возможность это делать. Или есть опен сорсный gerrit).

    Возможно, вы используете классы только как структуры максимум с какими-то тривиальными действиями (типа get_sum, get_value, set_value и т.д.). Когда как в ООП объекты должны инкапсулировать в себе логику и уметь делать нетривиальные вещи. Сама программа должна состоять из взаимодействующих объектов.

    Еще использование stl. Стоит избегать массивов - используются std::vector. Так же вместо char* стоит использовать std::string. Ну и там куча алгоритмов есть: от выбора максимума в массиве до сортировки.
    Ответ написан
    Комментировать
  • Как получить элементы структуры?

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

    Можно облегчить себе жизнь и использовать IDE. Тогда после написания "car_1." любая достаточно хорошая IDE подскажет вам список всех членов этой структуры. Но это по сути просто автоматизация действия "посмотреть в исходник".
    Ответ написан
    Комментировать