📖 Ключевые слова

• Следование — последовательное выполнение действий
• Линейный алгоритм — алгоритм, состоящий только из последовательных шагов
• Синтаксическая ошибка — неправильное написание команды
• Логическая ошибка — программа работает, но даёт неверный результат

💡 Интересный факт

Эти три основные алгоритмические конструкции (следование, ветвление, повторение) выдвинул и доказал нидерландский учёный Эдсгер Вибе Дейкстра (1930–2002) в 70-х годах прошлого века. Его идеи оказали огромное влияние на развитие компьютерной индустрии.

💡 Определение

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

📝 Алгоритм приготовления отвара шиповника

1. Столовую ложку сушёных плодов шиповника измельчить в ступке
2. Положить в кастрюлю
3. Залить стаканом кипятка
4. Кипятить 10 минут на слабом огне
5. Охладить
6. Процедить

🤔 Обрати внимание!

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

💻 Фрагмент линейного алгоритма

x := 2
y := x * x
y := y * y
x := y * x
s := x + y

Это запись на псевдокоде (упрощённом языке программирования). Здесь символ := означает «присвоить значение».

💡 Важно понимать

Составленная нами таблица моделирует работу исполнителя этого алгоритма. Такой процесс называется трассировкой алгоритма.

💰 Практический пример: Кассир выдаёт сдачу

Покажем, как с помощью этих операций можно реализовать алгоритм работы кассира, выдающего покупателю сдачу (s) наименьшим количеством банкнот по 1000, 500, 100 и 50 рублей:

k1000 := s div 1000
s := s mod 1000
k500 := s div 500
s := s mod 500
k100 := s div 100
s := s mod 100
k50 := s div 50

Как это работает? Представь, сдача — 1864 рубля:

• Сначала выделяем максимум тысячных купюр: 1864 div 1000 = 1 (одна купюра), остаток 1864 mod 1000 = 864
• Потом пятисотки из 864: получается одна, остаток 364
• Потом сотни: три штуки, остаток 64
• И наконец, пятидесятки: одна штука, остаток 14 (который мелочью и отдадут)

🤖 Условие задачи

У исполнителя Альфа есть две команды, которым присвоены номера:

1. прибавь 2
2. умножь на а (а — неизвестное натуральное число)

Выполняя первую команду, Альфа увеличивает число на экране на 2. Выполняя вторую, умножает это число на а.

Программа для исполнителя Альфа — это последовательность номеров команд. Известно, что программа 11211 переводит число 4 в число 100.

Необходимо определить значение а.

✅ Решение

Шаг 1. Запишем последовательность действий по преобразованию исходного числа 4 в соответствии с заданным алгоритмом:

(4 + 2 + 2) · а + 2 + 2 = 100

Шаг 2. Выполним преобразование левой части выражения:

8 · а + 4 = 100

Шаг 3. Решим линейное уравнение:

8 · а = 96
а = 12

Ответ: а = 12

🤖 Пример 5: Робот-художник

У исполнителя Робот есть четыре команды перемещения: вверх, вниз, влево и вправо. При выполнении каждой из них Робот перемещается на одну клетку в соответствующем направлении. По команде закрасить Робот закрашивает клетку, в которой он находится.

Запишем линейный алгоритм, исполняя который Робот нарисует на клетчатом поле следующий узор и вернётся в исходное положение:

алг узор
нач
    закрасить
    вправо
    вправо
    закрасить
    вниз
    влево
    закрасить
    влево
    вверх
кон

⚠️ Проблема!

А теперь подумайте: что произойдёт, если Робот приступит к выполнению этой же программы в обстановке, в которой между двумя клетками есть стена?

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

💡 Главный вывод об ограниченности линейных алгоритмов

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

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

🔧 Отладка программы

Все ошибки исправляются в процессе отладки программы. Это важный этап создания любого алгоритма или программы.