Линейные алгоритмы

Линейные алгоритмы

Линейный алгоритм — это алгоритм, в котором все команды выполняются строго одна за другой, в том порядке, в каком они записаны. В нём нет ни проверки условий, ни повторений: исполнитель просто идёт по списку команд от первой до последней и нигде не сворачивает с прямого пути. Поэтому такую структуру и называют линейной.

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

Свойства линейного алгоритма

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

Запись и блок-схема

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

Разобранный пример

Составим линейный алгоритм вычисления периметра прямоугольника со сторонами a и b:

нач

ввод a, b

P := 2 · (a + b)

вывод P

кон

Здесь три действия идут подряд: ввод исходных данных, вычисление по формуле и вывод результата. Ни одно из них не повторяется и не зависит от какого-либо условия — это и есть признак линейности алгоритма.

Второй пример

Алгоритм обмена местами двух чисел тоже линейный, хотя и хитрый. Чтобы поменять значения переменных a и b, заводят вспомогательную переменную c:

c := a; a := b; b := c

Все три команды выполняются по очереди, и порядок здесь принципиален. Если убрать вспомогательную переменную и написать a := b; b := a, то прежнее значение a будет потеряно, и обе переменные станут равны b.

Где встречаются линейные алгоритмы

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

Частая ошибка: менять местами команды, забывая про их зависимость друг от друга. Нельзя вывести значение P раньше, чем оно вычислено, и нельзя вычислять сумму до ввода чисел a и b. Порядок команд в линейном алгоритме часто строго обязателен.

Кратко о главном

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