• Так сколько шариков для гольфа действительно поместится в школьный автобус?

    Прочитал недавно заметку «15 Вопросов на собеседовании в Google, из-за которых вы можете почувствовать себя глупым» в интернете и самый же первый ответ на самый первый вопрос мне не понравился. Человек я дотошный, поэтому решил математически вычислить количество тех самых шариков для гольфа.

    image

    Там читатель берет объем автобуса, делит на объем шарика и получает количество шаров. Вычитает, правда, какое-то количество, учитывая, что там есть «сиденья и прочая ерунда, занимающая свободное место, а также сферическая форма мяча означает, что будет достаточно много свободного места между ними». Правильно ли он учел?

    Давайте разберемся.
    Читать дальше →
  • Поиск подстроки и смежные вопросы

    Здравствуйте, уважаемое сообщество! Недавно на Хабре проскакивала неплохая обзорная статья о разных алгоритмах поиска подстроки в строке. К сожалению, там отсутствовали подробные описания каких либо из упомянутых алгоритмов. Я решил восполнить данный пробел и описать хотя бы парочку тех, которые потенциально можно запомнить. Те, кто еще помнит курс алгоритмов из института, не найдут, видимо, ничего нового для себя.
    Читать дальше →
  • Двадцать вопросов, которые помогают разработать алгоритм

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

      На самом деле решение любой задачи сводится к сбору информации о наблюдаемом объекте. Причем этот принцип применим как для решения самых сложных научно-исследовательских задач, так и для решения прикладных задач. Работа изобретателя напоминает не столько работу волшебника, сколько путешествие первооткрывателя по неизведанной территории. Главное качество хорошего изобретателя – умение собирать информацию.

      Если вы хотите решить сложную задачу, собирайте информацию в самых разных направлениях. Ответив на следующие 20 вопросов, вы легко выстроите план работы над задачей.
      Читать дальше →
    • Вычисление редакционного расстояния


        Редакционное расстояние, или расстояние Левенштейна — метрика, позволяющая определить «схожесть» двух строк — минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую. В статье излагается метод вычисления редакционного расстояния при использовании небольшого объема памяти, без существенной потери скорости. Данный подход может быть применен для больших строк (порядка 105 символов, т.е. фактически для текстов) при получении не только оценки «схожести», но и последовательности изменений для перевода одной строки в другую.
        Читать дальше →
      • Быстрое умножение многочленов при помощи преобразования Фурье — это просто

          Добрый вечер.
          Этот пост посвящён быстрому преобразованию Фурье. Будут рассмотрены прямое и обратное преобразования (в комплексных числах). В следующей части я планирую рассмотреть их применения в некоторых задачах олимпиадного программирования (в частности, одна задача про «похожесть» строк), а также рассказать про реализацию преобразования в целых числах.
          БПФ — это алгоритм, вычисляющий значения многочлена степени n=2k в некоторых n точках за время O(n⋅logn) («наивный» метод выполняет ту же задачу за время O(n2)). За то же время можно выполнить и обратное преобразование. Так как складывать, вычитать и умножать массивы чисел гораздо легче, чем многочлены (особенно умножать), БПФ часто применяется для ускорения вычислений с многочленами и длинными числами.
          Читать дальше →
        • Алгоритм Карацубы для умножения двух чисел

            Как-то раз пришлось реализовывать умножение длинных чисел, через половинки их представления на C++. 128-битные числа были представлены как пара 64-битных. Оказалось что перемножить два 128-битных числа и получить все 256 бит результата по сложности сравнимо с 4-мя произведениями 64-битных половинок. Как же это работает…

            Читать дальше →