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

Теперь вам может быть интересно, зачем нам нужны алгоритмы для решения того или иного вопроса, разве мы не можем решить его, не изучив их, вы правы! Алгоритмы - это, в частности, метод, который может использовать решатель, который может помочь им в решении ряда вопросов. Хорошо, давайте погрузимся в 10 лучших алгоритмов.

1. Евклидов алгоритм.

Алгоритм Евклида основан на нахождении НОД (наибольшего общего делителя) двух чисел. Например: допустим, у нас есть два числа 15,20, и мы хотим узнать gcd этих двух чисел. Обычный метод говорит, что 15 имеет эти простые множители 3,5, а 20 - эти простые множители 2,5. Таким образом, наибольшее общее число (делитель) в обоих условиях равно 5. Теперь в соревновательном программировании у нас есть диапазон чисел от 10⁹ и выше, поэтому мы не можем найти простые множители этих больших чисел, это займет слишком много времени, нам нужен более быстрый и эффективный алгоритм, поэтому здесь идет алгоритм Евклида. В этом процессе мы начинаем с большего числа как B и меньшего числа как A, а затем мы берем модуль B% A, который будет нашим новым A, этот процесс будет продолжаться до тех пор, пока B не станет равным нулю. Обычно, когда итерации неизвестны, и мы знаем базовый случай, т.е. когда B равно 0, лучше выполнить рекурсию. Посмотрим на код.

2. Расширенный алгоритм Евклида.

Теперь есть еще что-то, известное как расширенный алгоритм Евклида, который используется для вычисления коэффициентов, так что он дает gcd (a, b)

ax + by = gcd(a, b)

Для этого мы выполним определенное количество шагов, помните, когда мы вычисляли GCD (a, b), ответы сохранялись в стеке (рекурсия), а затем, когда b было равно нулю, мы возвращали a, теперь мы можем сделать следующее: , во время этой серии шагов мы сохраним значения в 2 переменных и вернем 1-ю переменную в качестве ответа. Например:

Рассмотрим 16,10
НОД (16, 10) = НОД (10, 16% 10) = НОД (10, 6)
НОД (10, 6) = НОД (6, 10% 6) = НОД (6, 4)
НОД (6, 4) = НОД (4, 6% 4) = НОД (4, 2)
НОД (4, 2) = НОД (2, 4% 2) ) = НОД (2, 0)

Чаще всего расширенный алгоритм Евклида используется для вычисления модульного обратного числа, например, если вы хотите вычислить r / d, где r и d - очень большие числа, первое, что может вам прийти в голову, - это использовать mod, как мы это делаем в a * b = (a% mod * b% mod)% mod, но когда дело доходит до деления, это не так просто, как умножение, потому что вам нужно найти (r * инверсия d), которая является то же, что и (r% mod * x% mod)% mod, где x является модульным обратным к b, теперь, когда дело доходит до нахождения модульного обратного к x, мы можем сделать это, используя маленькую теорему Ферма, но проблема в том, что r & mod должен быть взаимно простыми друг с другом, теперь, если в постановке задачи они не упомянули, что r и x взаимно просты, тогда вам нужно использовать расширенный евклидов алгоритм, который даст вам значения x и y, где x является модульным обратным r.

3. Поиск в ширину (BFS) и поиск в глубину (DFS)

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

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

DFS, как и в случае с первым углубленным поиском, снова, как следует из названия, будет проходить в глубину текущего узла, пока не достигнет точки, где он заканчивается. Например, если у вас есть два маршрута от вашего дома, BFS будет проверять каждый маршрут, но когда дело доходит до DFS, он проверяет один маршрут, затем выбирает этот маршрут и углубляется, пока он не достигнет пункта назначения или конца. точка.

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

4. Алгоритм двоичного поиска

Алгоритм поиска - самый важный аспект соревновательного программирования. Если вам разрешено искать в массиве / векторе / списке, размер которого превышает 10¹⁸, вы будете выполнять линейный поиск, то есть проверять каждый элемент, а затем, если вы нашли данный элемент, верните его. Но при таком большом размере поиск потребует очень больших временных затрат, поэтому приходит двоичный поиск. Основной мотив этого алгоритма в том, что массив надо отсортировать, да !. Если массив отсортирован, можно выполнить поиск с временной сложностью O (n / 2), что намного лучше, чем линейный поиск.

Процедура двоичного поиска следующая, примите во внимание, что вам дан такой массив.

Хорошо, как видите, данный массив отсортирован, и мы собираемся применить к нему следующую процедуру.

  1. Сохранить левый индекс (L) = 0 и правый индекс (R) = N - 1
  2. Теперь вычислите средний индекс L и R = ›L + (R - L) / 2.
  3. После этого проверьте, является ли данный элемент больше / меньше / равен заданному элементу индекса.
  4. Если данный элемент меньше среднего элемента индекса, измените R на m, иначе, если данный элемент больше среднего, измените L на M.
  5. Выполните указанные выше 4 шага в цикле while, пока не дойдете до индекса, в котором найден данный элемент, если нет, то верните -1.

Итак, вот как вы выполняете двоичный поиск и находите данный элемент во временной сложности O (N / 2).

5. Сито Эратосфена.

Это самый распространенный вопрос, который сейчас задают в Интервью в компаниях, предоставляющих услуги. Вопрос гласит: найдите n-е простое число или вычислите n простых чисел или вычислите простые числа в заданном диапазоне. Самым наивным решением было бы проверить от начального элемента, который равен 1, до n-го элемента, который необходимо проверить, и перебрать все элементы, лежащие в этом диапазоне, и если n делится на любое число, то оно не является простым, в противном случае данное число простое. Опять же, это займет почти O (n) временную сложность, но, как всегда, мы хотим уменьшить временную сложность, потому что она не может быть высокой. Итак, вот алгоритм сита. Этот алгоритм выглядит следующим образом.

Давайте проверим, сколько чисел являются простыми в диапазоне от 2 до 100, что мы сделаем следующим образом.

  1. Мы начинаем с 2, проверяем каждое число, которое делится на 2 до 100, и помечаем их как непростые числа, потому что они имеют более двух множителей.
  2. Затем мы обращаемся к числам, которые еще не отмечены как простые, и снова переходим от текущего числа к 100 и отмечаем каждое число, которое делится на это текущее число.
  3. Теперь очевидно, что мы не будем делать это для всех 100 элементов, что приведет вас к временной сложности O (N²), которая хуже, чем раньше, вместо того, чтобы просто пойти до квадратного корня (N), который будет включать все числа в диапазоне 1–100.
  4. Вот и все, теперь все неотмеченные числа - это те простые числа, которые нам нужны. И мы получили простые числа за O (квадратный корень (N)). Временная сложность.

6. Быстрое возведение в степень

Это алгоритм, который поможет вам практически с любой проблемой, с которой вы столкнетесь, почему ?! потому что в большинстве проблем, с которыми мы сталкиваемся, нам нужно будет вычислить степени, да !, вам может понадобиться возведение в степень, например 2³, 3¹⁰⁰⁰, 10¹²…. эти мощности определенно мы не можем вычислить в линейной временной сложности. Это слишком дорого. Нам нужно что-то лучше, вот и быстрый метод возведения в степень за O (Log (n)), да, вы не ослышались!

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

  1. Допустим, мы получили 5¹¹⁷, что нам нужно сделать, это разбить 117 на степени двойки, и теперь, как мы собираемся это сделать, мы собираемся представить 117 в двоичное число, которое сейчас составляет 111 0101, где когда-либо двоичная цифра 1, мы знаем, что он в степени 2, хорошо, теперь из этого разделите число.
  2. Круто !, так что после этой операции мы перешли от 117 умножений к 64, что составляет половину от оригинала, теперь, если данное число намного больше, чем это, например, предположим, 10¹², нам не нужно выполнять такие большие операции, мы будем траверс только до половины.
  3. И после всех этих умножений нам просто нужно сохранить его в переменной и взять мод, как обсуждалось ранее, почему это необходимо.

7. Алгоритм Дейкстры.

Теперь это более продвинутый алгоритм, чем мы обсуждали раньше, и в большинстве случаев его не задают прямо, вы получите смешанные вопросы, такие как Dijkstra + DP. Теперь это вопрос более высокого уровня. Итак, вот примечание: прежде чем двигаться дальше, убедитесь, что вы знаете теорию графов, потому что это необходимо.

Предположим, у вас есть разные маршруты от дома до колледжа, но они стоят вам разных монет, например, маршрут 1 стоит 60 / - где маршрут 2 стоит 100 / - а маршрут 3 стоит 80 / - что является наиболее очевидным выбором Вы бы взяли, дешевле, не так ли ?. Хорошо, то же самое здесь, то, что Дейкстра скажет вам, является кратчайшим и экономичным маршрутом от вашего дома до колледжа, покупайте, рассчитывая разные монеты, которые вам понадобятся на станциях. Теперь этот алгоритм более классифицирован, если монеты / затраты положительны, но если он отрицательный, результаты могут быть неверными. Хорошо, давайте погрузимся в алгоритм.

Исходная точка начинается с момента, когда вы хотите достичь z, вам даны затраты от источника до другого источника, и вы хотите найти кратчайший маршрут от a до z. Итак, процедура выглядит следующим образом.

  1. Сначала убедитесь, что вы сохраняете исходный узел как значение 0, потому что от исходного узла до самого себя стоимость равна нулю, и сохраняете все остальные вершины как бесконечность, потому что сейчас мы не знаем, какие затраты.
  2. Затем начните с исходного узла и сохраните каждую вершину как значение от исходной до текущей стоимости узла. В приведенном выше условии b, e и h теперь будут иметь стоимость 3, 5 и 4, хорошо, теперь рассмотрим следующую вершину, скажем, f, для f есть 3 входящих маршрута, теперь, если мы рассчитаем стоимость каждого маршрута, мы будем получить из b = 10, e = 9, h = 9. Теперь замените значение бесконечности на 9, потому что это намного эффективнее, чем бесконечность. Это называется расслаблением, потому что вы снижаете стоимость с более высокой до более низкой.
  3. Завершите 2-й шаг для каждой вершины, пока не достигнете z, что даст вам значение z, которое является конечной стоимостью, которая вам нужна, которая указывает кратчайший путь от источника до z. Здорово, что вам удалось узнать этот алгоритм.

8. Алгоритм Рабина-Карпа.

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

Хорошо, поскольку вы можете видеть то, что вы хотите знать в приведенном выше примере, а именно поиск данной строки CDD, если она соответствует данной строке. Теперь, как мы собираемся это сделать, назначить все уникальные символы, присутствующие в данном массиве со значениями, превышающими предыдущие значения, вот так.

Круто, теперь, когда у нас есть уникальные символы в нашем массиве, мы будем использовать технику хеширования для массива с этой формулой.

hash value for pattern(p) = Σ(v * dm-1) mod 13

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

  1. Сначала вы вычисляете хеш-значение для требуемой строки и сохраняете его в переменной, затем вы начинаете с индекса 0 до n и вычисляете значение хеширования для длины m. Значение хеширования для второй строки - 6.
  2. Например, у нас есть вторая строка длиной 3, и мы собираемся вычислить значение хеширования для ABC, оно дает нам 6, тогда как BCC дает нам 12, и так далее. Теперь нам не нужно 12, нам нужно 6, поэтому мы собираемся сохранить все символы индекса в нашем списке, что даст нам значение 6.
  3. Следующий шаг - просто перебрать список и проверить, совпадает ли строка со строками в наших списках.
  4. Вот и все, что мы нашли подходящую строку, и временная сложность уменьшилась меньше, чем раньше.

9. Алгоритм выпуклой оболочки.

Что ж, мы находимся на алгоритме, который встречается редко, но чрезвычайно полезен, когда вы занимаетесь более высоким рангом в конкурентных платформах программирования. Вопросы, касающиеся выпуклой оболочки, задавались и на конкурсе code jam. Так что сначала будет немного сложно понять, но как только вы попрактикуетесь с этим, будет легче использовать. Таким образом, алгоритм выпуклой оболочки используется для определения самого короткого многоугольника, который может быть построен в наборе точек, который будет содержать все точки в нем. Теперь у самого короткого многоугольника будет наименьшее количество сторон.

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

  1. Начните с точки, найдите крайнюю правую точку (по часовой стрелке) и отметьте ее как конечную точку.
  2. Теперь вершина, от которой вы расположили крайнюю правую точку, будет вашей начальной вершиной, а следующим шагом будет определение местоположения всех остальных точек.
  3. Что ж, в этом случае начните с исходной вершины и теперь вычислите крайнюю левую точку (направление против часовой стрелки) и отметьте ее как источник сейчас, и повторяйте шаги, пока не дойдете до точки, где крайняя левая точка будет конечная точка.
  4. Вот и все, вы нашли вершины, которые будут частью многоугольника, и когда вы соедините эти вершины, вы получите нужный многоугольник.