Введение в алгоритмы
Алгоритм - это последовательность шагов, описывающая, как можно решить проблему. Каждая компьютерная программа, которая заканчивается результатом, в основном основана на алгоритме. Однако алгоритмы не ограничиваются использованием в компьютерных программах, их также можно использовать для решения математических задач и во многих вопросах повседневной жизни. Основываясь на том, как они функционируют, мы можем разделить алгоритмы на несколько типов. Давайте посмотрим на некоторые из важных.
Типы алгоритма
Существует много типов алгоритмов, но основными типами алгоритмов являются:
1) Рекурсивный алгоритм
Это один из самых интересных алгоритмов, поскольку он называет себя с меньшим значением в качестве входных данных, которые он получает после решения для текущих входных данных. Проще говоря, это алгоритм, который вызывает себя несколько раз, пока проблема не будет решена.
Такие проблемы, как Ханойская башня или DFS графа, могут быть легко решены с помощью этих алгоритмов.
Например, вот код, который находит факториал с использованием алгоритма рекурсии:
Факт (у)
Если у 0
возврат 1
return (y * Fact (y-1)) / * здесь происходит рекурсия * /
2) Разделяй и властвуй Алгоритм
Это еще один эффективный способ решения многих проблем. В алгоритмах «Разделяй и властвуй» разделяйте алгоритм на две части, а первые части разбивают имеющуюся проблему на более мелкие подзадачи того же типа. Затем, во второй части, эти более мелкие проблемы решаются, а затем складываются (объединяются) для получения окончательного решения проблемы.
Сортировка слиянием и быстрая сортировка могут быть выполнены с помощью алгоритмов «разделяй и властвуй». Вот псевдокод алгоритма сортировки слиянием, чтобы дать вам пример:
MergeSorting (ar (), l, r)
Если г> л
- Найдите среднюю точку, чтобы разделить данный массив на две половины:
средний m = (l + r) / 2
- Вызов сортировки слиянием для первой половины:
Вызов слиянияСортировка (ар, л, м)
- Вызвать сортировку слиянием для второй половины:
Вызов слиянияСортировка (ar, m + 1, r)
- Объедините половинки, отсортированные на шаге 2 и 3:
Вызов слияния (ar, l, m, r)
3) Алгоритм динамического программирования
Эти алгоритмы работают, запоминая результаты прошлого запуска и используя их для поиска новых результатов. Другими словами, алгоритм динамического программирования решает сложные проблемы, разбивая его на несколько простых подзадач, а затем решает каждую из них один раз, а затем сохраняет их для будущего использования.
Последовательность Фибоначчи является хорошим примером для алгоритмов динамического программирования, вы можете увидеть, как она работает в псевдокоде:
Фибоначчи (N) = 0 (для n = 0)
= 0 (для n = 1)
= Фибоначчи (N-1) + Финачи (N-2) (для n> 1)
4) Жадный алгоритм
Эти алгоритмы используются для решения задач оптимизации. В этом алгоритме мы находим локально оптимальное решение (без учета каких-либо последствий в будущем) и надеемся найти оптимальное решение на глобальном уровне.
Метод не гарантирует, что мы сможем найти оптимальное решение.
Алгоритм имеет 5 компонентов:
- Первый - это набор кандидатов, из которого мы пытаемся найти решение.
- Функция выбора, которая помогает выбрать наилучшего кандидата.
- ТЭО, которое помогает решить, можно ли использовать кандидата для поиска решения.
- Целевая функция, которая присваивает значение возможному решению или частичному решению.
- Функция решения, которая сообщает, когда мы нашли решение проблемы.
Кодирование Хаффмана и алгоритм Дейкстры - два основных примера использования алгоритма Жадности.
В кодировании Хаффмана алгоритм проходит сообщение и, в зависимости от частоты символов в этом сообщении, для каждого символа назначает кодирование переменной длины. Чтобы выполнить кодирование Хаффмана, нам сначала нужно построить дерево Хаффмана из входных символов, а затем пройти через дерево, чтобы назначить коды для символов.
5) Алгоритм перебора
Это один из самых простых алгоритмов в концепции. Алгоритм перебора вслепую перебирает все возможные решения для поиска одного или нескольких решений, которые могут решить функцию. Думайте о грубой силе как об использовании всех возможных комбинаций чисел, чтобы открыть сейф.
Вот пример последовательного поиска, выполненного с использованием грубой силы:
Алгоритм S_Search (A (0..n), X)
A (n) ← X
я ← 0
В то время как A (i) ≠ X делают
я ← я + 1
если я вернусь
иначе вернуть -1
6) Алгоритм возврата
Возврат - это метод, позволяющий найти решение проблемы с помощью постепенного подхода. Он рекурсивно решает проблемы и пытается найти решение проблемы, решая одну часть проблемы за раз. В случае сбоя одного из решений мы удаляем его и возвращаемся, чтобы найти другое решение.
Другими словами, алгоритм обратного отслеживания решает подзадачу и, если ему не удается решить проблему, он отменяет последний шаг и снова начинает поиск решения проблемы.
Проблема N Queens - хороший пример того, как можно увидеть алгоритм возврата в действии. Проблема N Королевы гласит, что на шахматной доске есть N фигур Королевы, и мы должны расположить их так, чтобы никакая королева не могла напасть на любую другую королеву на организованной доске.
Теперь давайте рассмотрим алгоритм SolveNQ и функции Check Valid для решения этой проблемы:
CheckValid (Шахматная доска, строка, столбец)
Начало
Если слева от текущего столбца есть Королева, верните false
Если королева находится в левом верхнем углу, верните false
Если королева находится в нижней левой диагонали, верните false
Верните истину
Конец
SolveNQ (доска, колонка)
Начало
Если все столбцы заполнены, вернуть true
Для каждого ряда, присутствующего в шахматной доске
Делать
Если CheckValid (доска, х, столбец), то
Установите королеву в ячейку (x, столбец) на доске
Если SolveNQ (доска, столбец + 1) = True, тогда верните true.
В противном случае удалите ферзя из клетки (столбец x) с доски.
Выполнено
Вернуть ложь
Конец
Вывод - Типы алгоритмов
Алгоритмы стоят за большинством впечатляющих вещей, которые могут делать компьютеры, и они лежат в основе большинства вычислительных задач. Улучшение работы с алгоритмами не только поможет вам стать успешным программистом, но и станет более эффективным.
Рекомендуемые статьи
Это было руководство по типам алгоритмов. Здесь мы обсуждаем 6 основных типов алгоритмов с их функциями. Вы также можете просмотреть наши другие предлагаемые статьи, чтобы узнать больше -
- Введение в алгоритм
- Алгоритм в программировании
- Алгоритм Интервью Вопросы
- Факториал в Python | методы
- Алгоритмы быстрой сортировки в Java
- Топ 6 Алгоритм сортировки в JavaScript