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

    @Karpion
    Перцептивный хэш тем и хорош, что для слабо различающихся изображений он одинаковый.

    А ещё можно организовать БД с этими хешами так, чтобы каждый хэш содержал ссылки на все хэши, которые от него мало отличаются. Ну или можно по ходе дела сгенерировать все хэши, отличающиеся от данного на один бит, на два бита, на три бита, etc; ну и запросить БД по этим вариациям.
    Ответ написан
  • Где найти специалиста по теории алгоритмов?

    @Karpion
    Для начала хотелось бы знать, алгоритмы из какой области Вас интересуют. Универсального специалиста по всем областям трудно найти, и он, скорее всего, окажется менее полезным, чем тот, кто работает чисто по нужной области.

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

    @Karpion
    Ну, я могу предложить то же, что и Wataru : создать очередь со ссылками на пустые элементы массива. Есть даже более красивое решение:
    1. В пустом элементе хранится не "-1", а ссылка на следующий пустой элемент. А начало списка хранится в отдельной переменной.
    2. Соответственно, массив можно инициировать этими ссылками.
    Т.е. учёт занятости элементов массива ведётся в этом же массиве, в свободных элементах. Примерно так работает классическая файловая система Unix с дисковым пространством; с той только разницей, что в кластере файловой системы можно хранить много ссылок.

    И есть второй вариант:
    При каждом удалении элемента производить дефрагментацию свободного места. Сдвигать весь хвост массива слишком сложно, а вот переместить на освободившееся место последний элемент массива = самое то что нужно.
    Ответ написан
    Комментировать
  • Как понять и реализовать битовую карту?

    @Karpion
    Запись "HOVERED | FOCUSED" читается "HOVERED или FOCUSED". Однако, по-русски это должно говориться "HOVERED и FOCUSED" (аналог: крокодил - длинный и зелёный").
    Ещё это выражение можно записать "HOVERED + FOCUSED" - будет то же самое, и к тому же понятнее. Но эта форма записи плоха тем, что для двух одинаковых признаков "HOVERED | HOVERED == HOVERED", а вот при сложении будет не так.

    Допустим, переменная x содержит в себе статус кнопки. Работать с этой переменной надо так:
    • Кнопка попала в фокус: x|=FOCUSED
    • Кнопка вышла из фокуса: x&=~FOCUSED
    • Проверка, в фокусе ли кнопка: x&FOCUSED?в_фокусе:не_в_фокусе
    Это можно использовать бездумно, не зная о двоичном представлении чисел.
    Ответ написан
    2 комментария
  • Как обойти граф не зацикливаясь на связи одного узла с другим?

    @Karpion
    Алгоритм зависит от ситуации и от организации графа.

    Если нам надо выяснить наличие электричества с нуля для уже построенной сети:
    1. Все работающие электростанции считаются - имеют электричество.
    2. Перебираем линии, подключённые к работающим электростанциям; их надо собирать в отдельную очередь. Каждый дом на конце линии, который ещё не в списке - заносим в список имеющих электричество.
    3. При добавлении каждого дома - в очередь заносятся линии, подключённые к этим домам.
    4. Когда очередь стала пустой - список построен окончательно.


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

    Если включается электростанция - то запускаем поиск от неё.

    А вот если рвётся линия или отключается электростанция - то придётся строить список с нуля.

    PS: Есть алгоритмы динамической маршрутизации пакетов в сетях передачи данных (в т.ч. в Internet). Они умеют чётко обрабатывать добавление и удаление узлов и связей между узлами. Но они хранят намного больше информации - т.е. такие алгоритмы требуют больше памяти.
    Ну и надо добавить, что эти алгоритмы предназначены для распределённого выполнения на узлах, причём связь между узлами может отсутствовать.
    Ответ написан
    Комментировать
  • Случайные числа с заданной сумой, какой алгоритм?

    @Karpion
    Проблема в том, что сделать у всех трёх чисел равномерное распределение - не получится. Вы бы написали, зачем это нужно.

    Мне кажется, надо кинуть на отрезок длины 100 три точки, чтобы разделить его на четыре части. Полученные три числа - отсортировать.

    Проблема: числа могут получиться одинаковыми.
    Решение: Кидаем три точки на отрезок длиной 94=100-1-2-3. Сортируем отрезки. Потом к первому прибавляем 3, ко второму прибавляем 2, к третьему прибавляем 1 - это если нужны целые числа.
    Ответ написан
    Комментировать
  • Как ускорить функцию поиска подстроки на C?

    @Karpion
    У меня есть подозрение, что функции работы со строками пишутся на ассемблере и используют команды процессора типа REP SCAS - надеюсь, Вы знаете, что это такое.
    Проверить это можно на исходниках библиотек, благо в Linux они доступны.

    Навскидку я могу Вам посоветовать заменить m_0[0] на *m_0 - хотя это вряд ли что-то изменит.

    И я вообще не понял Вашего алгоритма. Такое ощущение, что Вы зачем-то сравниваете с конца.

    И ещё интересно, на каких примерах Вы это тестировали. Есть тонкость - многие алгоритмы поиска подстроки сильно зависят от данных. Если строка набита случайными символами - лучший подход один; если строка содержит повторяющиеся куски - лучший подход немного совсем другой.
    Ответ написан
  • Бот, понимающий смысл?

    @Karpion
    Сначала надо распарсить текст на подлежащие, сказуемые и остальные части предложений. И тут уже начинаются проблемы: "крокодил" - это подлежащее или сказуемое прошлого рода?

    Дальше будут иные сложности. Например, в тексте м.б. что-то типа

    Вася сказал:
    - Там был синий шар.
    Петя возразил:
    - Нет, шар был красный.
    Ваш бот должен понимать речь персонажей - и учитывать, что персонажи могут лгать.
    Или там чистое повествование, без прямой речи?

    Будут проблемы с пониманием местоимений - это в принципе неоднозначно.
    Ответ написан
  • Как остановить вращение в нужном месте?

    @Karpion
    Вы зря считаете угол по формуле типа "+=" - она накапливает ошибки. Лучше считать "angle = time * speed".

    Допустим, в момент начала остановки угловая скорость была speed, а остановиться надо через угол fi.
    Если скорость будет неизменной, то колесо пройдёт угол fi за время t1=fi/speed. Если скорость будет равномерно снижаться до нуля, то за это время колесо пройдёт угол fi/2.

    Допустим, в момент t0 колесо имеет угол angle0. И мы начинаем тормозить по формуле
    angle = angle0 + (time * speed) - (uskr * time^2 / 2)
    Колесо тормозится - ускорение отрицательное.

    Скорость обнулится в момент
    d_time1 = speed / uskr
    В этот момент угол angle1 будет равен - по формуле выше. И он д.б. такой, какой нам надо, т.е. он известен.

    angle1 = angle0 + (time1 * speed) - (uskr * time1^2 / 2)

    Подставляем time1 :
    angle1 = angle0 + (speed / uskr * speed) - (uskr * (speed / uskr)^2 / 2)
    angle1 = angle0 + (speed^2 / uskr) - (speed^2 / uskr / 2) = angle0 + (speed^2 / uskr /2)
    (speed^2 / uskr /2) = angle1 - angle0
    uskr = (speed^2 / 2 / (angle1 - angle0))

    Ну вот, вроде, всё. Вычисляем:
    angle0 = time0 * speed
    uskr = (speed^2 / 2 / (angle1 - angle0))
    d_time1 = speed / uskr
    if time < time0 then {
    angle = time * speed;
    } else if time < time0 + d_time1 then
    angle = angle0 + (time * speed) - (uskr * time^2 / 2)
    } else {
    angle = angle1
    }
    Как-то так...
    Ответ написан
    Комментировать
  • Как найти баланс чисел в массиве?

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

    @Karpion
    А что нужно-то? Постоянный шаг, равное расстояние между точками? Тогда угол надо брать обратно пропорционально радиусу - работает, если радиус больше шага.
    Ответ написан
    Комментировать
  • Бесконечный цикл или ненужная за циклом переменная?

    @Karpion
    В данном случае надо использовать не цикл-с-предусловием "while ...", а цикл-с-постусловием "repeat ... until" (иногда его пишут как "... while" или "do ... while", но условие стоит в конце цикла).
    Ответ написан
    Комментировать
  • Как считаете нужно, ли фронтендеру знать алгоритмы?

    @Karpion
    Можно жить и без этого. Но без этих знаний - можно круто накосячить.
    Ответ написан
    Комментировать
  • Проект Эйлера. Задача #37. Не понимаю постановку вопроса?

    @Karpion
    По моим ощущениям - Вы считаете "1" простым числом, а авторы задачи думают иначе.

    Вообще, считать ли "1" простым числом - зависит от волевого решения. Многие теоремы на тему простых чисел - не срабатывает на единице, поэтому её исключили из комсомола из списка простых чисел.

    Upd: Открыл ветку комментариев выше - оказывается, там это уже есть.
    Ответ написан
    Комментировать
  • Как разработать алгоритм для нахождения двух элементов, сумма которых дает x?

    @Karpion
    Сначала упорядочим множество (массив) S по возрастанию.
    Затем берём два крайних элемента, считаем их сумму. Допустим, сумма больше, чем нужно - тогда отбрасываем правый (самый большой) элемент; а если меньше - то самый левый (ну, не отбрасываем - а сдвигаем указатель к центру массива). И повторяем - пока не получится нужная сумма или пока элементы не закончатся.
    Ответ написан
    Комментировать
  • Алгоритмы быстрого возведения в степень?

    @Karpion
    Я распишу это так:
    13 = 8+4+1
    21^13 = 21^8 * 21^4 * 21^1

    Теперь вычисляем иксы так:
    x1=21
    x2=x*x1
    x4=x2*x2
    x8=x4*x4

    И вычисляем искомое
    21^13 = x8 * x4 * x1
    (x2 в произведении не участвует - он нужен для вычисления x4).

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

    @Karpion
    Пусть конечные точки имеют декартовы координаты {x0,y0,z0} и {x1,y1,z1}
    Берём отрезок прямой, соединяющий конечные точки (проходящий внутри сферы); координаты его точек будут:
    {x0+(x1-x0)*k,y0+(z1-z0)*k,z0+(z1-z0)*k}, где k пробегает все хначения от нуля до единицы.
    Переводим эти координаты в сферическую систему, а затем принудительно делаем радиус равным радиусу окружности (углы не меняются). Всё, мы имеем все точки нужно Вам дуги окружности.

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

    @Karpion
    Допустим, x1, y1, x2, y2 - целые.
    Пусть x1=y1=0 (достигается: x2=-x1; y2=-y1;).

    Ищем k=НОД(x2,y2) (там по ссылке есть алгоритмы).

    Делим x2 и y2 на к - это координаты первой точки.
    Умножаем координаты первой точки на 2,...,(k-1) - получаем все остальные точки (конечные точки и первая точка считаются уже найденными, их не выводим; если надо все - то ряд будет 0,1,...,k).
    Ответ написан
    Комментировать