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

Wataru

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

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

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

  • Наиболее эффективная реализация алгоритмов преобразования BWT и MTF?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Вот тут посмотрите: https://stackoverflow.com/questions/7857674/whats-...

    Идея - построить суффиксный массив (что почти тоже самое, что BWT). Там рекомендуют libdivsufsort. Вроде как, его можно использовать и в node.js: https://www.npmjs.com/package/divsufsort
    Ответ написан
    Комментировать
    Комментировать

  • Как реализовать поиск общих элементов двух массивов с помощью суффиксного дерева?

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

    Если массивы не упорядочены, или очень хочется деревом, то
    1) Строим суффиксное дерево для массива a[].
    2) Проходим по всем элементам массива b[] и смотрим, сколько раз подстрока из этого 1 элемента встречается в строке a[]. Это стандартная операция для суф. дерева: надо просто взять количество листьев в поддереве вершины, которая читается искомой строкой (в нашем случае - это непосредственный ребенок корня, к которому ведет строка, начинающаяся с символа b[i]).

    Еще конкретнее - постройте дерево, найдите для каждой вершины количество листьев в поддереве (просто суммируя эти же значения для всех детей или рекурсивно или поднимаясь снизу-вверх). Потом просуммируйте эти значения для всех вершин, в которые из корня есть ребро начинающееся с символа b[i] для всех i.
    Ответ написан
    Комментировать
    Комментировать

  • Как проверяется принадлежность точки многоугольнику методом углов?

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

    Для этого нужно взять векторное и скалярные произведения векторов на точки - это будут синус и косинус угла, умноженные на длины векторов. Их, даже не деля на длины, можно передать в функцию atan2(), и она даст вам значение угла. уже с правильным знаком. Хотя можно подстраховаться - угол должен быть от -пи до +пи. Если он больше пи, то нужно вычесть из него 2пи, если меньше -пи, то прибавить.

    Все эти углы просто суммируем. Если точка лежит снаружи, то ответ будет 0. Если точка внутри, то ответ будет +-2пи. Если точка лежит на границе - то черт его знает, но этот случай легко обнаружить. Если какой-то из суммируемых углов равен +-пи, то точка на отрезке. Еще отдельно надо бы проверить случай, что точка совпала с одной из вершин многоугольника. Там будет нулевой вектор, и atan не сработает.
    Ответ написан
    Комментировать
    Комментировать

  • Какой алгоритм использовать для определения минимального числа перестановок карт в колоде?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Правильный ответ - 52-<длина наибольшей общей подпоследовательности>.
    Выводится он так:
    1) Ни одну карту нет смысла двигать 2 раза. Т.е. ответ 52-<количество неподвижных карт>
    2) Неподвижные карты находятся в том же порядке в обеих колодах, следовательно они образуют наибольшую общую подпоследовательность.

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

    F(i, j) - длина наибольшей общей подстроки у префиксов длины i у первой строки и длины j у второй.

    База F(0,*)=F(*,0)=0

    Переход: F(i,j) = max(F(i-1,j), F(i,j-1), F(i-1,j-1)+1). Третий вариант рассматривается только, если i-ый символ в первой строке и j-ый во второй равны.

    Ответ - 52-F(52,52) для вашей задачи

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

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

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

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

    Гораздо лучшая реализация была бы изначально зарезервировать первый элемент в массиве и записать туда очень маленькое число. А сами данные записывать после него. Тогда в цикле while не надо будет сравнивать index>0. Эта реализация будет гораздо быстрее дополнительного бинарного поиска.
    Ответ написан
    2 комментария
    2 комментария

  • Игры на алгоритмы

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