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

Определения и обозначения

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

Линейный алгоритм — алгоритм, в котором команды выполняются последовательно, одна за другой. Исполнитель не выбирает между вариантами и не возвращается к командам для повторения. Такое описание удобно, когда порядок и число действий заранее известны.

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

Исполнитель алгоритма — человек или устройство, выполняющее команды по заданным правилам. У исполнителя есть возможности и ограничения: он может выполнить одни действия, но не другие. Если учитывать их заранее, алгоритм получится выполнимым, а не только понятным автору.

Как это устроено

Сначала задачу построения лестницы нужно представить как цель: исполнитель должен пройти по заданному числу ступеней и оказаться в нужном месте. Затем определяют, какие действия он умеет выполнять, например подняться вверх или переместиться вперёд. Это нужно потому, что алгоритм может содержать лишь понятные исполнителю команды. Если цель и возможности не уточнены, нельзя решить, какие указания записывать.

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

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

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

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

Построение лестницы линейным алгоритмом

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

Разбор задач

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

1. Начать движение из исходного положения.
2. Выполнить команду «вверх».
3. Выполнить команду «вперёд».

Ответ: «вверх», «вперёд». Сначала исполнитель поднимается, а затем продвигается по ступени, поэтому порядок соответствует условию.

Задача 2. Составьте линейный алгоритм для построения лестницы из трёх одинаковых ступеней. Каждая ступень задаётся подъёмом и движением вперёд, значит, пара команд должна встретиться в записи три раза. Поскольку алгоритм линейный, пары записываем явно, а не заменяем командой цикла.

1. Для первой ступени записать: «вверх», «вперёд».
2. Для второй ступени добавить такую же пару.
3. Для третьей ступени добавить ещё одну пару.
4. Посчитать пары и убедиться, что их три.

Ответ: «вверх», «вперёд», «вверх», «вперёд», «вверх», «вперёд». Проверка числа пар помогает не пропустить ступень и не добавить лишнюю.

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

1. Разделить алгоритм на четыре пары команд для четырёх ступеней.
2. Проследить каждую пару, отмечая, где исполнитель сначала движется вперёд, а потом поднимается.
3. В ошибочной паре поменять порядок на «вверх», «вперёд».
4. Повторно пройти все команды и проверить четыре ступени.

Ответ: в паре с неверным порядком заменить «вперёд», «вверх» на «вверх», «вперёд». После исправления все четыре пары должны задавать одинаковый путь.

Типичные ошибки

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

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

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

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

Связь с другими темами

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

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

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

Что запомнить

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