27. Два исполнителя - одна дорога

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

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

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

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

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

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

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

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

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

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

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

Движение двух исполнителей по общей дороге

Используйте таблицу как памятку: сначала заполните начальные условия для каждого исполнителя, затем заносите результаты после одинакового числа шагов. В строке «условие встречи» проверьте, совпали ли положения в один момент. Если команды повторяются, добавьте номера шагов и отмечайте повторение состояний.

Разбор задач

Задача 1. Два исполнителя стоят на дороге в разных местах. Первый находится в точке 2 и делает один шаг вправо, второй находится в точке 7 и делает один шаг влево. Определим их положения после одного шага. Координаты выбраны для наглядности: каждый шаг перемещает на одну точку.

1. Запишем начальные положения: у первого координата 2, у второго — 7. Это важно, потому что команда применяется к собственной точке старта каждого исполнителя. Оба выполняют по одной команде.

2. Первый движется вправо, поэтому получает координату 2 + 1 = 3. Второй движется влево, значит, его координата становится 7 − 1 = 6. Направления учитываем отдельно.

3. Ответ: после одного шага первый исполнитель находится в точке 3, второй — в точке 6. Их положения не совпадают, значит, после этого шага встречи нет. Для проверки достаточно сравнить полученные координаты.

Задача 2. Исполнители начинают движение навстречу друг другу: первый стартует в точке 0 и каждый шаг идёт вправо, второй стартует в точке 6 и каждый шаг идёт влево. Проверим, окажутся ли они в одной точке после трёх шагов. Оба выполняют по одному шагу за один и тот же промежуток времени.

1. После первого шага положения равны 1 и 5. Они ещё не совпали, поэтому продолжаем проверку. Записывать оба результата рядом удобно: так не перепутаются моменты движения.

2. После второго шага первый находится в точке 2, а второй — в точке 4. Координаты опять разные. После третьего шага получаем 3 у первого и 3 у второго.

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

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

1. После первого шага первый находится в точке 1, второй — в точке 4. После второго шага оба возвращаются в начальные положения: 0 и 5. На этих шагах координаты не совпали.

2. Теперь повторилось полное состояние: оба снова в исходных точках, а команды начинаются с первого действия цикла. Значит, следующие шаги повторят уже проверенную пару положений. Новых вариантов для встречи не появится.

3. Ответ: встречи не будет. Доказательство опирается не на бесконечный перебор, а на повтор цикла и отсутствие совпадения в нём. Если бы положения совпали на одном из шагов цикла, это была бы встреча.

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

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

Ошибка 2 — путать направление движения и знак изменения положения. Это часто происходит, когда один объект движется навстречу другому и направления кажутся взаимными. Сначала задайте, какая сторона считается положительным направлением, затем отмечайте изменение координаты для каждого исполнителя.

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

Ошибка 4 — при повторении команд забыть проверить состояние в начале цикла. Из-за этого можно пропустить первую встречу или ошибочно продолжать перебор. Записывайте положения и место в последовательности команд до повторения, а затем проверяйте все шаги цикла, включая его начальное состояние.

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

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

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

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