Пользователь пока ничего не рассказал о себе

Достижения

Все достижения (3)

Наибольший вклад в теги

Все теги (24)

Лучшие ответы пользователя

Все ответы (90)
  • Как решить задачу на сложность алгоритмов ниже?

    wataru
    @wataru
    г) не правильно подсчитано.

    Составьте уравнение. Вот есть у вас функция времени для n входных данных f(n) на компе B. На компе A время выполнения будет - f(n)/100, ведь он в 100 раз быстрее.

    Теперь обозначьте за x объем данных на компе A, который надо найти. Тогда у вас f(x)/100 = f(n). Подставьте нужную функцию вместо f() и найдите x. Спойлер, будет похоже, но не то, что у вас в вопросе указано.
    Ответ написан
  • Очень быстрый алгоритм умножения длинных чисел, куда копать?

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

    wataru
    @wataru
    Это классическая задача о рюкзаке.

    Можно составить такое ДП: F(c, k) - максимальное количество страниц, которые можно набрать из первых k книг общей стоимостью ровно c.

    База: F(0,0) = 0, F(0,*) = F(*,0) = -infinity.
    Пересчет:
    F(c, k) = max(F(c-cost[k], k-1) + pages[k], F(c,k-1))


    Это ДП приведено в википедии, например. Ответ - максимум по всем c F(c,k).

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

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

    wataru
    @wataru
    Вот пример такого хеша:

    int hash(string s) {
      return 42;
    }


    Можно вместо 42 возвращать другое число, но обязательно, всегда одно и то же.
    Это все потому, что множества слов с ошибками перекрываются. Например, строки "aaaa" и "aabb" должны давать одинаковый хеш. Но точно так же сроки "bbbb" и "aabb" должны давать одинаковый хеш. В итоге получается, что все возможные строки должны давать одинаковый хеш.

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

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

    wataru
    @wataru
    В общем виде, когда надо найти функцию любого вида (предположительно самую короткую) - задача не решается. Тут нужен искусственный интеллект. Настоящий, а не машин лёрнинг.

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

    Тут можно решить систему из n линейных уравнений (обозначаете неизвестными коэффициенты полинома, подставляете известные значения x и y для всех эталонов, гоните метод Гаусса).

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

    Формально, задача будет решена, но практического смысла в этом нет совсем. Формулы будут огромными и страшными.
    Ответ написан