Типовые алгоритмы в программировании

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

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

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

Инициализация переменной, отвечающей за экстремальное значение (максимум в данном случае) может быть осуществлена двумя способами. Первый - значение, которое заведомо меньше (или больше, если поиск минимума) чем все элементы массива.

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

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

Самый простой алгоритм сортировки называется сортировка «пузырьком». Рассмотрим решение задачи упорядочивания по возрастанию этим алгоритмом. Для данного массива происходит последовательное сравнение значений двух соседних элементов: a_iи а.₊₁. Если элемент a > a.₊₁, то они меняются местами.

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

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

Рассмотрим пример программы, которая осуществляет сортировку пузырьком по возрастанию.

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

В программировании также используется такой приём, как рекурсия. Рекурсия - это вызов функции самой себя на выполнение. Подход применяется в тех случаях, когда каждое новое значение для функции зависит от некоторого другого значения этой же функции. Классическим примером является вычисление факториала. Как известно - факториал числа - это произведение чисел от 1 до этого числа.

Например, для числа 5 5! = 1-2 • 3 • 4 • 5 = 5 • 4!
Аналогично 4! = 4 • 3!
3! = 3 • 2!
2! = 2 • 1!
1! = 1

Таким образом, терминальным условием вызова рекурсивной последовательности является вычисление значения факториала единицы - оно равно единицы. В общем виде зависимость вычисления факториала для числа n можно записать как

Если n > 1, то fact(n) = n • fact(n -1) иначе fact(n) = 1 Рассмотрим пример программы, которая реализует выше представленный алгоритм

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