Портал:ЕГЭ и ОГЭ/Информатика/ЕГЭ/Программирование. Стандартные алгоритмы

Материалы

Поможем подготовиться к ЕГЭ/ОГЭ

Проведена экспертиза
Российской Академией Наук

Программирование. Стандартные алгоритмы

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

Основная цель программного алгоритма — принять входные данные, обработать их и предоставить ожидаемый результат.

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

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

Ниже приведён список таких задач

Список

• Нахождение минимума и максимума двух, трех, четырех данных чисел без использования массивов и циклов.
• Нахождение всех корней заданного квадратного уравнения.
• Запись натурального числа в позиционной системе с основанием, меньшим или равным 10. Обработка и преобразование такой записи числа.

Нахождение сумм, произведений элементов данной конечной числовой последовательности (или массива).

• Использование цикла для решения простых переборных задач (поиск наименьшего простого делителя данного натурального числа, проверка числа на простоту и т. д.).

Поиск

• Линейный поиск: последовательно проверяются все элементы один за другим до достижения искомого элемента или конца массива/списка. Этот метод прост в реализации, но может быть неэффективным для больших массивов/списков.
• Бинарный поиск: используется только для упорядоченных (отсортированных) массивов/списков. Элементы проверяются путем деления интервала на каждом шаге и сравнения с элементом-целью. Поэтому бинарный поиск является очень эффективным и выполняется за логарифмическое время. Однако, требуется предварительная сортировка списка/массива.
• Интерполяционный поиск: этот метод используется для равномерно распределённых и упорядоченных массивов/списков. Он использует линейную интерполяцию между началом и концом интервала для прогнозирования положения элемента. Хотя интерполяционный поиск может быть эффективным, его сложность может быть сильно увеличена для неравномерно распределённых данных.
• Поиск с использованием хэш-функции: этот метод используется для быстрого поиска элементов в хэш-таблицах, где элементы хранятся по индексам, вычисленным с использованием хэш-функции. Поиск происходит через константное время O(1), что делает его эффективным. Однако, хэш-функции должны быть эффективными и предотвращать коллизии (ситуации, когда два разных элемента имеют одинаковый хэш-код).
• Поиск с использованием деревьев: в данном случае используются структуры данных, такие как двоичные деревья поиска, AVL-деревья, B-деревья и т. д. Эти структуры данных обеспечивают эффективный поиск, вставку и удаление элементов. Деревья основаны на принципе разделения интервала и позволяют уменьшить количество сравнений для поиска элемента.

Графы

• Обход в глубину: алгоритм, использующий стек для поиска в глубину всех вершин графа, связанных с текущей вершиной.
• Обход в ширину: алгоритм, использующий очередь для поиска в ширину всех вершин графа, связанных с текущей вершиной.
• Алгоритм Дейкстры: граф представляется в виде списка смежности, где каждой вершине соответствует список смежных с ней вершин, а каждому ребру соответствует его вес.

Массивы

• Заполнение элементов одномерного и двумерного массивов по заданным правилам.
• Операции с элементами массива. Линейный поиск элемента. Вставка и удаление элементов в массиве. Перестановка элементов данного массива в обратном порядке. Суммирование элементов массива. Проверка соответствия элементов массива некоторому условию.
• Нахождение второго по величине (второго максимального или второго минимального) значения в данном массиве за однократный просмотр массива.
• Нахождение минимального (максимального) значения в данном массиве и количества элементов, равных ему, за однократный просмотр массива.
• Операции с элементами массива, отобранных по некоторому условию (например, нахождение минимального четного элемента в массиве, нахождение количества и суммы всех четных элементов в массиве).
• Слияние двух упорядоченных массивов в один без использования сортировки.

Сортировка массива

• Пирамидальная сортировка: алгоритм сортировки на основе сравнения, который строит пирамиду из входных элементов, а затем многократно извлекает её максимальный элемент и помещает его в конец отсортированного выходного массива.
• Сортировка пузырьком: алгоритм, основанный на попарном сравнении элементов, их перестановке и повторении данного процесса до полной сортировки.
• Сортировка выбором: алгоритм, основанный на нахождении минимального элемента в массиве и его перемещении на первую позицию, затем нахождении следующего минимального элемента и т. д.
• Быстрая сортировка: алгоритм, основанный на принципе «разделяй и властвуй», который разделяет массив на подмассивы, сортирует их отдельно и объединяет в один отсортированный массив.
• Сортировка слиянием: Алгоритм сортировки слиянием — это алгоритм «разделяй и властвуй», который делит массив на две части, сортирует две половины, а затем снова объединяет их.

Строка

• Обработка отдельных символов данной строки. Подсчет частоты появления символа в строке.
• Работа с подстроками данной строки с разбиением на слова по пробельным символам. Поиск подстроки внутри данной строки, замена найденной подстроки на другую строку.