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

Wataru

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

  • Почему не удаётся освободить память в деструкторе?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Проблема вот в этой строчке:
    int get_num_from_BigInteger(BigInteger big_int){

    Тут у вас идет передача по значению. У вас создается новая BigInteger переменная, со значением переданной. Поскольку вы конструктор копирования нигде не определили, компилятор сделал его вам сам, и там он тупо копирует все данные класса, включая указатель arr.
    В итоге у вас получается два экземпляра класса, в каждом из которых указатель на один и тот же массив. Потом каждый из двух экземпляров в деструкторе вызовет free для одного и того же указатенля, вот и получается двойной free и креш.

    Вам надо руководствоватся правилом трех(пяти). Доопределите конструктор копирования. Вообще, вам бы стоило его запретить (= delete;), ибо копировать такие большие числа - это плохо. А в функции ваши передавайте BigInteger по константной ссылке.

    Ну и в других функциях та же самая поблема.

    И еще, в C++ не стоит использовать malloc/free, используйте new/delete. А еще лучше, используйте std::vector.
    Ответ написан
    Комментировать
    Комментировать

  • Почему при полностью идентичном содержимом файлов (*.js, *.php, *.css) они могут иметь разный вес/размер?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Многие платформы поддерживают метаданные для файлов. В винде они называются потоками (file streams). Их не видно, если просто открыть файл, но всякие программы знают, как туда залезть и что-то там посмотреть. Например, все браузеры при скачивании файлов из интернета делают в этих потоках пометку, что файл-то скачан. И винда потом при попытке открыть такой экзешник обычно выдает предупреждение: "Ахтунг, файл из интернета, точно хотите открыть?"

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

    На линуксе похожая штука точно есть, но я не помню, как оно называется.

    Еще варант: не ошиблись ли вы с подсчетом размеров файлов? Может вы килобайты с кибибайтами перепутали?

    А гит скорее всего заметил измененные даты на файлах, но изменений в самих файлах не нашел. И да, гит эти потоки игнорирует.
    Ответ написан
    2 комментария
    2 комментария

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

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

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

    Есть еще тонкий момент: рассуждения получающие меньший элемент заданного иногда нельзя применить ко всем числам. Например, если вы работаете с целыми положительными, а предположенный минимальный у вас 1, то из 1 вы меньшее число никак не получите. Поэтому надо сначала проверить, принадлежит ли 1 к множеству и потом предполагать существование минимального элемента > 1.
    Ответ написан
    1 комментарий
    1 комментарий

  • What is the running time of insertion sort?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Квадратичное. При вставке каждого элемента в среднем отсортированная часть будет на треть состоять из 0, на треть и 1 и на треть и 2. Если текущий элемент 2, то вставка за O(1), если текущий элемент 1, то вы потратите i/3 операций. Если элемент 0, то 2/3i. В среднем i/3 операций на один элемент. Если просуммировать это от 1 до n, то получится n(n-1)/6. Значит общее количество операций O(n^2).
    Ответ написан
    2 комментария
    2 комментария

  • Как найти или показать существование цикла в ориентированном графе быстрее, чем за O(IVI+IEI)?

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

    Это можно доказать. Вам так или иначе придется посмотреть на все ребра. Допустим, есть алгоритм, который всегда может проверить цикл, смотря не все ребра. Рассморим какой-то граф без циклов. Алгоритм там какие-то ребра посмотрел и сказал, что циклов нет. А мы возьмем и скормим этому алгоритму почти такой же граф, только одно из ребер, которые он вообще не трогал, сделаем обратным какому-то другому ребру в графе, сделав таким образом цикл. Но алгоритм посмотрит на те же самые ребра, увидет все то же самое и сделает точно такой же вывод, что циклов нет, и ошибется. Все потому что мы допустили алгоритм, который всегда смотрит не все ребра. Значит таких алгоритмов нет и там всегда будет хотя бы O(|E|).
    Ответ написан
    2 комментария
    2 комментария

  • Почему выдается неправильный результат при операциях c long int в Си?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Проблема в выводе. Вы пытаетесь вывести переменную unsigned long long через спецификатор "%d". Надо использовать "%llu" какой-нибудь.
    Ответ написан
    Комментировать
    Комментировать

  • Возможно ли обнаружить сортировкой Кана изолированные узлы, сортировать сразу рёбра и не использовать степень?

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


    Без нее работает медленно. Смотрите алгоритм. В алгоритме надо брать вершину в которую не входит ни одно ребро, а также удалять вершины. Кончено, можно наивно брать все вершины, потом брать все ребра, смотреть, не удалено ли ребро и не ведет ли оно в эту вершину. Но это будет O(VE) для поиска одной вершины, а суммарно алгоритм будет O(V^2E). Когда как реализация с подсчетом степеней и очередью будет O(V+E).

    Есть ли возможность сортировать не узлы, а рёбра сразу?

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

    Можно ли таким образом обнаружить, что этот граф содержит изолированные узлы, которые могут быть соединены между собой?


    Можно. Изолированные узлы - это те в которые ни одно ребро не входит. В алгоритме Кана это те, которые можно вывести до удаления любой вершины.
    Ответ написан
    2 комментария
    2 комментария

  • Как записать DAG для прохода по ациклическому ориентированному графу, используя C#?

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

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

    Но все перечисленные тут алгоритмы являются примерно одинаково эффективными. Без бенчмарков нельзя сказать какой из них лучше, и на разных формах графов одни могут быть лучше других и наоборот.
    Ответ написан
    33 комментария
    33 комментария

  • Какой смысл использовать функцию эйлера в rsa?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Потому что теорема Эйлера. А в процессе шифрования значение для текста вовзводится в степень по модулю n. А для дешифровки возводится в еще одну степень. Поэтому показатель степени ищется по модулю Ф(n).
    Ответ написан
    Комментировать
    Комментировать

  • Почему программа не работает?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Проблема в том, что сначала пытаетесь вычислить a^(p-2), а потом взять его по модулю. В задаче числа до 10^9 и если вы попытаетесь вычислить что-то вроде 99999^1000005, то у вас int переменная переполнится, потому что там должны быть миллионы знаков в числе, а в int едва 10 влезает.

    Надо брать по модулю при каждом умножении в возведении в степень.

    Потому что (a*b)%p = (a%p)*(b%p) % p.

    Edit:

    Еще две ошибки: считать произведение надо в long long, потму что 10^9*10^9 в int не влезает.
    И fast_deg(a, deg/2) надо вызывать только один раз, а то у вас функция работает за O(n) вместо O(log n).
    Ответ написан
    2 комментария
    2 комментария

  • Какой смысл prime nulls в hungarian algorithm?

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

    По вашей ссылке звездочками отмечены нули, соответствующие ребрам в текущем паросочетании (потенциалы уже вычтены из всех значений в матрице, поэтому нули соответствуют жестким ребрам). "primed", т.е. отмеченные символом ' нули соответствуют ребрам, которые вы перебираете в удлинняющей цепи. Помеченные столбцы и строки - соответствуют обойденным вершинам.

    Смысл в том, что ' нули вытесняют какие-то * нули и в итоге у вас получается на 1 ноль больше в паросочетании.
    Ответ написан
    Комментировать
    Комментировать

  • Покрытие графа циклами?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Вы расписали то, что в доказательстве скрывается за "clearly, any 2-factor of G translates into a perfect matching of G' and vice versa". Можно было бы чуть поформальнее, но основная идея правильная. Или можно еще проще: разбиение на циклы равносильно перестановке, которая для каждой вершины задает следующую в цикле. Перестановка равнозначна максимальному паросочетанию.

    Действительно, полное парсочетание становится циклами. Да, если граф не ориентированный, или содержит "тривальные" циклы (длины 2), то они могут войти в покрытие. Если найдется не полное паросочетание, то в графе будут какие-то непересечающиеся циклы и возможно пути. Он может быть даже не весь покрыт при этом.
    Ответ написан
    3 комментария
    3 комментария

  • Как добавляются потенциалы тогда в Hungarian algorithm?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    вы ссылку-то свою вообще читали?
    ( $u[i]=v[i]=0$  for all  $i$ ),

    В начале. Вы начинаете с нулевых потенциалов, потом увеличиваете их как описанно в алгоритме, пока можете. Попутно обновляя множество H.

    Кстати, даже при нулевых потенциалах H может быть не пустым, если в матрице есть нули.
    Ответ написан
    4 комментария
    4 комментария

  • Как автоматизировать прохождение змейки на веб сайт через autohotkey?

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

  • Может ли такое быть, что менее продвинутый алгоритм сортировки выполняется быстрее?

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

  • Можно ли добиться постоянного O(nlogn) для квиксорта в любом случае?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Да, можно. Для этого надо в качестве pivot'а выбрать медиану. если это сделать за O(n) в худшем случае, то общая сложность QuickSort'а будет O(n log n).

    Для выбора медианы за O(n) есть, например, вот такой алгоритм. В каких-то источниках его еще называли алгоритмом кнута-пратта-мориса-ривеста-тарьяна. Кажется, но я их найти не могу, так что я какие-то фамилии напутал, но помню, что там было 5 великих информатиков.

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

  • Почему функция непрерывная?

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

  • Почему некорректно работает OpenGL?

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

    Еще надо задать в начале преобразование, чтобы координаты соответствовали экрану (один раз):
    glutCreateWindow("Game");
glMatrixMode( GL_PROJECTION );
glLoadIdentity();
gluOrtho2D( 0.0, 600.0, 400.0, 0.0 );
    Ответ написан
    Комментировать
    Комментировать

  • Почему появляется ошибка Uncaught Reference?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Смотрите внимательно, у вас точка с запятой после цикла. Следующая строка выполняется вне цикла, в котором i и объявлена.
    Ответ написан
    1 комментарий
    1 комментарий

  • Как из критерия унимодальности следует унимодальность функции?

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

    Вы доказали, что частичные разницы не возрастают. Тут могут быть 3 варианта:
    1) они все неотрицательные. Функция унимодальна (монтонность с максимумом в конце - частный случай унимодальности).
    2) они все неположительные. Монотонно убывающая функция.
    3) есть и положительные и отрицательные. Но раз разности не могут возрастать, после первого 0 могут идти только нули а после отрицательного только отрицательные. А заначит разности выглядят ровно так, как у унимодальной функции.
    Ответ написан
    Комментировать
    Комментировать