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

    @fireSparrow
    В модуле collections есть структура OrderedDict, которая является словарём, хранящим порядок элементов.
    Если заполнить его парами ключ-значение в порядке убывания длины ключа, то именно так их он и сохранит, и при итерации будет отдавать сначала длинные ключи.
    Единственное, что нужно помнить - после того, как такой словарь построен, при необходимости добавить новую пару, словарь нужно будет целиком заново перестраивать.
    Ответ написан
  • Как сложить строки как числа?

    @fireSparrow
    Если переписать на человеческий язык, то получится примерно так:

    Выполнять, пока в 'a' или 'b' ещё остались символы, или пока число 'c' не нулевое {
        Взять по одной цифре с конца из 'a' и 'b', сложить как числа и прибавить к 'c'
        Дописать к 'res' цифру, которая является остатком от деления 'c' на 10
            // То есть это попросту цифра, на которую заканчивается число 'c'
        Записать в 'c' boolean - было ли оно на этом шаге больше 9
           // Если было, то осталась необработанная цифра и нужно делать ещё итерацию
    }


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

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

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

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

    @fireSparrow
    Один вариант вам уже подсказали, а я бы сделал иначе, без забивания всего алфавита в код:
    key = lambda c: (c.lower(), c.islower())
    print(''.join(sorted(s, key=key)))
    Ответ написан
  • Какие инструменты, алгоритмы, методы есть для дополнения изображений?

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

    @fireSparrow
    0. Практика.
    1. Читай про ООП и паттерны проектирования.
    2. Изучай чужие хорошие архитектурные решения.
    3. Изучай приёмы рефакторинга и практикуйся рефакторить свой и чужой код.
    Например, очень ясно и подробно про рефакторинг написано здесь:
    https://refactoring.guru/ru/refactoring/what-is-re...
    Ответ написан
  • Алгоритм поиска паттерна в неупорядоченной последовательности?

    @fireSparrow
    С учётом вашего комментария к ответу x67:
    В этом случае можно попробовать проверять только каждый пятый байт. Если там ноль - от него шагаем по одному символу влево до тех пор пока не наткнёмся на не ноль. После чего отходим ещё на пару символов влево и уже с этого символа проверяем вхождение паттерна.
    Теоретически можно получить экономию почти в пять раз.
    Но это будет хорошо работать только если в массиве мало нулей, не являющихся частью паттерна. Если же в массиве много посторонних нулей - то может получится даже хуже, чем при линейном поиске.
    И всё-таки рекомендую попробовать реализовать этот вариант и замерить время работы по сравнению с линейным поиском.
    Ответ написан
  • Как можно фиксировать отказ потребителя?

    @fireSparrow
    1. Просматривать записи выборочно. Чаще делать это для тех менеджеров, по поводу которых есть подозрения. Регулярно доводить до сведения менеджеров, что запись ведётся. Если есть нарушения - устраивать показательную порку, чтобы неповадно было. Если нет нарушений - находить любые мелочи и устраивать их публичные разборы.
    Если менеджеры будут постоянно помнить, что большой брат следит за ними, этого уже может быть достаточно.

    2. Что-то не очень понял из описания - каким образом происходит оплата, что менеджер может её себе забрать. Можете пояснить?
    Ответ написан
  • Что почитать про геометрию в программировании?

    @fireSparrow
    Конкретно по первому вопросу:
    1. Перебираем все возможные тройки точек.
    2. Каждая тройка - это треугольник. Для него находим центр и радиус описанной окружности (конкретно для этой подзадачи алгоритм легко выгугливается).
    3. Проверяем - находятся ли все остальные точки внутри этого треугольника, и является ли эта окружность меньше, чем ранее найденные.

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

    @fireSparrow
    Трудно сказать что-то конкретное, не видя, как именно реализована изнутри структура, описывающая поле.

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

    Примечание: Я буду в ответе использовать термин "множество" в терминологии питона. Если у вас другой язык, воспользуйтесь аналогичной структурой из своего языка. Или используйте простой список, но перед добавлением в него элемента проверяйте, что такого элемента там нет. Иначе цикл никогда не завершится, а список будет разбухать, пока не съест всю память.

    Начинаете с одной любой ячейки.

    Создайте два пустых множества - назовём их 'currents' и 'visited'.
    В currents поместите ту ячейку, с который вы начинаете.

    Далее выполняете цикл, пока в currents есть хотя бы одна ячейка:
    1. Удалите из currents первую попавшуюся ячейку (далее её я называю "текущей ячейкой").
    2. Для этой текущей ячейки найдите всех её соседей.
    3. Для каждого соседа:
    3.1. Если он того же цвета, что и текущая, и не находится в множестве visited - добавьте его в currents
    3.2. Если он другого цвета - проведите границу между этим соседом и текущей ячейкой.
    4. Добавьте текущую ячейку в visited
    5. Повторять, пока currents не кончится.

    Граница нарисована!
    Ответ написан
  • Есть ли онлайн-сервис который нарисует блок схему по заданному тексту (не код)?

    @fireSparrow
    Вряд ли.
    Смысловой разбор произвольного текста - крайне неординарная задача. Для общего случая она пока не решена. Да и частные случаи, для которых она решена - весьма ограниченные и куцые.
    Гораздо проще научить человека писать понятный компьютеру код, чем научить компьютер разбирать понятный человеку текст.

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

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

    Но, имхо, самым лучшим будет просто написать свой класс, который будет предоставлять удобные интерфейсы для работы как со строками, так и со столбцами.

    Например, можно сделать так, чтобы в этом классе table.rows[0] отображало первую строчку, а table.cols[0] - первый столбец. Плюс, дополнительно прикрутить выборку по строкам и колонкам.
    Например, вот так table.select_cols(1,5)

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

    @fireSparrow
    Перечитал вопрос у удалил свой предыдущий коммент.

    Режем исходную строку на два списка.
    В первом - первое слово строки. Во втором - все остальные слова.

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

    @fireSparrow
    Имхо, универсального доказательства здесь не может быть.
    Только для каких-то конкретных категорий задач, для каждой - своим способом.
    Ответ написан