Задать вопрос
Ответы пользователя по тегу Алгоритмы
  • Как получить минимальную рамку кривого контура по границам контура?

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

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

    Во-вторых, можно доказать (смотрите комментарии к этому ответу, спасибо Alexandroppolus за идею), что рамка обязательно проходит через хотябы сторону выпуклой оболочки. Иначе ее можно вращать, уменьшая площадь пока она не коснется стороны.

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

    Удобно это реализовывать, если взять углы наклона всех сторон оболочки, их же сдвинутые на 90, 180 и 270 градусов и отсортировать. Далее надо перебирать рамки с такими углами наклона певрой стороны (можно в пределах [0,90) градусов). Первую рамку найдите перебором, а дальше какие-то точки надо будет сдвигать.

    Итак, весь алгоритм:
    1) построить выпуклую оболочку
    2) добавить в массив углы всех сторон и их копии повернутые на 90, 180 и 270 градусов и отсортировать, но не добавлять углы не в [0,90).
    3) для первого угла в массиве найдите 4 точки касания рамки.
    4) Для каждого отрезка углов в отсортированном массиве проверить, а надо ли сдвинуть точки касания вперед (каждую из четырех точек со своим углом), потом найти площадь рамки в известных точках с известным наклоном.

    Вместо работы с углами, для чего нужны тригонометрические функции, можно работать с векторами на единичной окружности. На отрезке углов можно легко взять середину, просто сложив два вектора-границы и нормировав. Для тернарного поиска не обязательно брать 1/3 и 2/3 на отрезке, поэтому можно так же просто просуммировать вектора с коэффициентами 1 и 2 и опять нормировать (v1+2*v2). Сортировать по углу тоже можно сравнивая вектора через векторное произведение векторов (иногда его называют псевдоскалярным).

    Чтобы найти рамку с заданным углом на точках не надо ничего пересекать (кроме ответа в конце, если вам надо координаты рамки вывести, а не только площадь найти). Надо представить прямые в виде cosa*x + sina*y + c = 0. Отсюда, зная точку (x, y) и угол прямой (a), можно найти c. cosa и sina считать не надо - это координаты вектора, перпендикулярного к известному вектору наклона прямой. Когда вы нашли два значения c для двух параллельных сторон, эти коэффициенты можно сложить - это и будет расстояние между сторонами (надо складывать, потому что cosa и sina в этих двух прямых будут с разными знаками, ведь у одной прямой угол на пол оборота больше). Остается подсчитать это два раза для перпендикулярных прямых и перемножить.

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

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

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

    Во-первых, если всего спрайтов можно сгенерировать меньше 16, то просто генерируйте все.

    Далее будем генерировать сразу все 16 спрайтов. Текущие спрайты будут иметь первые K слоев заполнеными и сгруппированы в отрезки по совпадению. Далее для каждого отрезка длины L, если L больше количества вариантов в текущем слое (N), то разбивайте отрезко на N примерно одинаковых по длине кусков. Все куски будут длины floor(L/N) и L%N из них будут на 1 длиннее. Если L < N, то выбирайте случайно L спрайтов в текущем слое и получайте кучу отрезков длины 1.

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

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    До 15 точек можно полным перебором сделать. Вам надо перебрать все разбиения 3n точек на тройки. Таких разбиений (3n)!/(3!)^n/n! для n=5 - это чуть больше миллиона.

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

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

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

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

    Сначала полным перебором найдите суммы всех подмножеств. Если есть совпадения, возьмите минимальную сумму, которую можно набрать больше 1 раза. Вычтите из случайного заказа 1 копейку. Повторяйте процесс. Если цены правдоподобны, сильно больше 100 копеек и цены различаются, то даже для 20 заказов вам придется лишь несколько копеек вычесть.

    Правда, если куча заказов с одинаковой ценой, то тут придется также младшие биты менять.
    Ответ написан
    Комментировать
  • Как найти ВСЕ контуры на изображении?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Сначала какие-то алгоритмы машинного зрения (что-то связанное с контрастом и градиентами цветов, тут я не специалист) находят точки, которые являются границами. Дальше по ним можно построить граф (соседние точки соеденены ребром). Потом в графе надо выделить все области и внешние будут контурами объектов. Алгоритм выделения областей хорошо описан тут.
    Ответ написан
    Комментировать
  • Фибоначчи без использования BigInt на javascript?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Без BigInt - никак. Числа-то большие получаются. Если нет библиотеки, придется самостоятельно писать длинную арифметику. Просто храните цифры числа в массиве и длину рядом. Вам надо будет только сложение реализовывать, ну это делается столбиком одним циклом. Храните перенос с младших разрядов в переменной. Можно или исходники BigInt поискать, или вот тут посмотреть
    Ответ написан
    Комментировать
  • Проблема с оптимизацией сортировки методом Bubble sort. Как ускорить сортировку для списка из 100 тысяч элементов?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Никак не ускорить. Сортировка пузырьком - медленная. Имеет квадратичное время выполнения. для 100000 элементов там будет 5 миллиардов сравнений в худшем случае. Для случайных массивов в пару раз меньше в среднем. С учетом, что это питон - вам этих 2х миллиардов операций придется ждать минуту. А с учетом 10 повторений - все 10 минут.
    Ответ написан
    3 комментария
  • Как решать задачу используя динамическое программирование?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Какой-то идиот задачу составлял.
    Во-первых, для N<60 ответ помещается в 64-битный целочисленный тип, который есть сейчас практически во всех языках программирования. Тут не надо ничего придумывать для избегания переполнения.
    Во-вторых, чтобы избежать переполнения, в таких задачах обычно просят выдать ответ по какому-то большому модулю. И последнее, как ответ может получиться нецелым - это просто загадка. Пример решения явно неверен.

    А так, динамическое программирование тут простое: Пусть F(N,K) - сколько существует невзрывоопасных стопок длины N, таких что в конце есть ровно K опасных контейнеров (очевидно, 0 <= K < 4). Это не совсем прям то, что вам нужно в задаче, но количество опасных стопок - это количество всех стопок (2^N) минус количество невзрывоопасных, поэтому это ДП нам подходит.

    Пересчет очень прост:

    F(N,K>0) = F(N-K,0)
    F(N,0) = F(N-1,0)+F(N-1,1)+F(N-1,2)+F(N-1,3)


    Если на конце K плохих контейнеров, то до этого точно должен быть хороший контейнер. Если на конце стоит хороший контейнер - то до него может быть 0..3 плохих контейнера.

    База: F(0,0) = 1, F(0, K>0) = 0

    Ответ: 2^N - F(N,0)-F(N,1)-F(N,2)-F(N,3)
    Ответ написан
    2 комментария
  • Почему моё решение данной задачи неправильное?

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

    У 28 шесть делителей (1, 2, 4, 7, 14, 28). Среди них есть делители 1 и 2, которые отличаются меньше чем на d=3.
    Ответ написан
    1 комментарий
  • Как решить задачу про кузнечика путем динамического программирования?

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

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

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

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

    Есть куча статей и конференций на тему. Это активная область исследования и каких-то окончательных ответов тут человечество пока не придумало, но есть куча очень умных алгоримов.
    Ответ написан
    Комментировать
  • Как найти точки пересечения 2х фигур с++?

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

    upd: На этом же сайте есть все что нужно для проверки пересечения окружности и отрезков.
    Ответ написан
    2 комментария
  • Как найти наибольшее значение у такой функции?

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

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

    Но если функция может принимать одинаковые значения на произвольном промежутке, то никаких логарифмических алгоритмов поиска максимума тут нет. Если обе промежуточные точки выдадут одно и то же значение, то никак не определить, в каком из трех промежутков лежит максимум.
    Ответ написан
    6 комментариев
  • Почему не проходит решение?

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

    Но ваша логика решения мне не понятна. Вам следует в каждой вершине поддерживать счётчик соседей листьев и их список. Далее, имейте очередь вершин с более чем k листьев рядом. Удаляйте k листьев. Если текущая стала листом (нужны счётчики для степени вершин), то добавьте её в список к единственному соседу.

    Чтобы не возиться с удалением соседей, помещайте вершины удаленными и при обходе списка соседей удаляйте их
    Ответ написан
  • Как реализовать дерево на основе связного списка?

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

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

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

    Там можно искать нужный вам элемент через floor или ceiling. Поиск и удаление, если создатели библиотеки в java хоть что-то слышали про алгоритмы и структуры данных, работают за логарифм.
    Ответ написан
    Комментировать
  • Чему будет равна сложность этого алгоритма?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Зависит от размеров item. Если они там каждый O(N) размера, то ваша догадка правильная: O(n^2 log n).

    Если же все item суммарно не превосходят N, то ответ O(N log N). Потому что если их размеры a_i, то у вас сумма ai log ai. log(ai) можно сверху ограничить log(N) и вынести за скобки и потом заменить сумму в скобках на N.
    Ответ написан
    1 комментарий
  • Как найти максимально похожий цвет?

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

    Если надо работать очень быстро, то надо представить ваши именные цвета как точки в трехмерном пространстве, построить kd-дерево или r-дерево и уже в нем искать ближайшую к запрошенной точку.
    Ответ написан
    5 комментариев