"Информатика (углублённый уровень)", Калинин И.А., Самылкина Н.Н.
Типовые алгоритмы помогают решать часто встречающиеся задачи без разработки решения с нуля для каждого набора данных. К ним относятся поиск максимума или минимума, поиск заданного элемента и сортировка последовательности. Алгоритм выбирают с учётом устройства данных: линейный поиск работает и без упорядочения, а бинарный требует отсортированной последовательности. Понимание этих приёмов помогает писать понятные программы и выбирать более эффективный способ обработки данных.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Типовой алгоритм — алгоритм, который решает часто встречающуюся задачу и подходит для разных исходных данных. Например, один и тот же способ поиска максимума можно применить к оценкам, температурам или результатам измерений. Это удобно: достаточно один раз продумать общий порядок действий, а затем использовать его в похожих программах.
Поиск элемента — определение, есть ли заданное значение в последовательности и, если есть, где оно расположено. Позицию элемента часто задают его индексом — номером в последовательности, который в программе может начинаться с нуля или единицы. Поиск нужен, чтобы проверить наличие данных или обратиться к найденному элементу.
Сортировка — упорядочение элементов последовательности по выбранному признаку, например по возрастанию. После сортировки проще находить нужные значения, сравнивать элементы и представлять данные в понятном порядке. Значения при этом сохраняются, изменяется только их расположение.
Линейный поиск — поиск, при котором элементы последовательно сравнивают с заданным значением. Его выполняют от начала последовательности к концу, пока не найдут совпадение или не закончатся элементы. Такой приём полезен, когда данные не упорядочены или список невелик.
Типовые алгоритмы полезны потому, что многие задачи повторяются при работе с разными наборами данных. Если каждый раз строить решение заново, легко упустить важный шаг или допустить ошибку. Общий алгоритм отделяет способ решения от конкретных значений: меняются входные данные, а последовательность действий остаётся прежней.
Чтобы найти максимум или минимум, сначала берут первый элемент за текущий экстремум, то есть наибольшее или наименьшее из уже просмотренных значений. Затем по очереди сравнивают с ним остальные элементы и обновляют текущий результат, если найдено более подходящее значение. Так после каждого сравнения результат верен для просмотренной части последовательности, а в конце — для всей. Начальное значение берут из данных, чтобы алгоритм работал и тогда, когда все числа отрицательные.
Линейный поиск проверяет элементы по одному и сравнивает каждый с искомым значением. Если совпадение найдено, алгоритм может запомнить позицию и завершиться; если дошёл до конца, значит, значения в последовательности нет. Этот способ не использует предположений о порядке элементов, поэтому подходит и для неупорядоченного списка. Его недостаток в том, что иногда приходится проверить каждый элемент.
Упорядоченность позволяет искать быстрее: в бинарном поиске сначала проверяют элемент в середине диапазона. Если искомое значение меньше него, в отсортированном по возрастанию списке можно оставить только левую половину; если больше — только правую. Поэтому после каждого сравнения возможная область поиска сокращается примерно вдвое. Этот вывод верен лишь при известном порядке данных, иначе отброшенная часть может содержать ответ.
Сортировка приводит элементы к заданному порядку — например, по возрастанию или убыванию. Общая идея состоит в том, чтобы последовательно переставлять элементы, пока их расположение не будет соответствовать выбранному правилу. Способы сортировки отличаются тем, какие элементы сравнивают и как именно меняют их местами. Поэтому для конкретной задачи учитывают не только требуемый порядок, но и выбранный алгоритм.
Таблица помогает быстро сопоставить задачу с её основной идеей, требованиями к данным и ожидаемым результатом. Перед выбором алгоритма проверьте, подходят ли ему исходные данные, особенно если планируете бинарный поиск. Так можно избежать способа, который выглядит быстрым, но не даёт верного ответа.
| Задача | Основная идея | Требования к данным | Результат |
|---|---|---|---|
| Нахождение максимума или минимума | Взять первый элемент за текущий экстремум и сравнить с остальными | Последовательность должна содержать хотя бы один элемент | Наибольшее или наименьшее значение |
| Поиск элемента | Сравнивать элементы с заданным значением; для упорядоченных данных можно применить бинарный поиск | Для линейного поиска порядок не важен; для бинарного данные должны быть упорядочены | Наличие значения и его позиция либо сообщение «не найдено» |
| Сортировка | Переставлять элементы, чтобы расположить их по выбранному правилу | Нужно задать признак и направление упорядочения | Та же последовательность элементов в новом порядке |
Условие. Дан список оценок, требуется найти наибольшую. Нельзя заранее считать, что в нём есть оценка выше нуля или что оценки расположены по порядку. Поэтому будем просматривать список и хранить лучший результат среди уже проверенных значений.
Ответ. Алгоритм возвращает наибольшую оценку списка. Если список может быть пустым, это нужно отдельно проверить: у пустой последовательности нет максимума.
Условие. В списке чисел нужно определить, есть ли заданное число, и вывести его позицию, если оно найдено. Порядок списка неизвестен, поэтому нельзя исключать элементы на основании их величины. Подойдёт проверка всех значений по очереди.
Ответ. Программа выдаёт позицию найденного числа либо сообщает, что его нет. Отдельный результат для отсутствия не позволит принять неподходящий индекс за правильный ответ.
Условие. Список чисел упорядочен по возрастанию, требуется найти позицию заданного числа, не просматривая каждый элемент подряд. Поскольку порядок известен, после сравнения можно понять, в какой части списка может находиться ответ. Для этого применим бинарный поиск.
Ответ. Алгоритм возвращает позицию числа либо сообщает, что оно отсутствует. На каждом шаге рассматривается примерно вдвое меньше элементов, чем на предыдущем.
При поиске максимума иногда начинают с нуля, потому что это кажется удобным начальным значением. Но если все числа отрицательные, ноль окажется больше каждого элемента и не будет правильным ответом. Начинайте с первого значения, а перед запуском проверьте, не может ли последовательность быть пустой.
После совпадения при поиске можно продолжить проверку без необходимости или не предусмотреть случай отсутствия значения. Обычно это происходит, когда условие завершения и результат для каждого исхода не продуманы заранее. Проверьте два случая отдельно: элемент найден и весь список просмотрен без совпадения.
Бинарный поиск иногда применяют к неупорядоченным данным, принимая сравнение с серединой за достаточное основание отбросить половину списка. Однако без порядка нельзя определить, в какой части искать, и ответ может оказаться в отброшенном диапазоне. Перед применением убедитесь, что последовательность отсортирована в известном направлении.
При сортировке можно перепутать условие сравнения элементов и направление упорядочения. Тогда программа переставит значения, но выдаст порядок, противоположный требуемому, или не упорядочит их полностью. Проверьте правило на небольшой последовательности, например на трёх разных числах, и сравните результат с нужным порядком.
Для работы с типовыми алгоритмами нужно уметь задавать последовательности и массивы, обращаться к элементам по индексам, использовать циклы и условия. Цикл обеспечивает повторение проверки, а условие помогает выбрать действие при сравнении значений. Эти приёмы пригодятся при обработке таблиц и массивов, где поиск и сортировка применяются к большому числу записей. Позже сравнение алгоритмов по эффективности помогает оценить, как растёт время работы при увеличении объёма данных.
Чем типовой алгоритм отличается от алгоритма для одной конкретной задачи?
Типовой алгоритм описывает общий способ решения целого класса похожих задач. В него можно подставить разные данные, если сохраняются условия задачи.
Почему при поиске максимума не следует начинать с нуля?
Если все элементы отрицательные, ноль окажется больше любого из них и не будет значением из последовательности. Поэтому начальный максимум нужно взять из первого элемента.
Когда можно использовать бинарный поиск?
Бинарный поиск применяют, когда элементы уже упорядочены и направление упорядочения известно. Без этого сравнение с серединой не позволяет правильно отбросить половину данных.
Что делать, если линейный поиск не нашёл нужный элемент?
Нужно проверить, что просмотрены все элементы, и вывести или вернуть отдельный результат «не найдено». Например, программа может сообщить об отсутствии значения, а не выдавать случайную позицию.
Меняются ли значения элементов при сортировке?
Нет, сортировка переставляет элементы, но не меняет их значения. После неё набор остаётся тем же, меняется только порядок.
§ 19. Типовые алгоритмы
