FFB86F — Черепаха, Чертёжник и Робот: ответ и решение

Впишите правильный ответ.

Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться на (a, b),
где a, b $-$ целые числа. Эта команда перемещает Чертёжника из точки
с координатами (x, y) в точку с координатами (x + a, y + b).

Например, если Чертёжник находится в точке с координатами (4, 2),
то команда сместиться на (2, −3) переместит Чертёжника в точку (6, −1).

Цикл

ПОВТОРИ число РАЗ

последовательность команд

КОНЕЦ ПОВТОРИ

означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным).

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

НАЧАЛО

сместиться на (4, -1)

ПОВТОРИ … РАЗ

сместиться на (…, …)

сместиться на (-4, 4)

КОНЕЦ ПОВТОРИ

сместиться на (-28, -17)

КОНЕЦ

В результате выполнения этого алгоритма Чертёжник возвращается
в исходную точку. Какое наибольшее число повторений могло быть указано в конструкции «ПОВТОРИ … РАЗ»?

СВОЙСТВА ЗАДАНИЯ

КЭС:

3.1 Формализация понятия алгоритма. Машина Тьюринга как универсальная модель вычислений

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

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

Тип ответа:

Краткий ответ

Номер: FFB86F

Статус задания: НЕ РЕШЕНО Ответить

Решение задания EGEINFFFB86F

Ответ: 6

Решение.
Обозначим число повторений через n, а неизвестное смещение через (u; v). По условию n — натуральное число, u и v — целые. Команды смещения складываются покоординатно.
Начальное смещение: (4; −1), известное смещение внутри цикла: (−4; 4), последнее: (−28; −17).
Один проход цикла даёт смещение (u + (−4); v + (4)). После n проходов обе координаты этого смещения умножаются на n.
Чтобы вернуться в исходную точку, суммарное смещение по каждой оси должно равняться нулю.
4 + n · (u + (−4)) + (−28) = 0.
−1 + n · (v + (4)) + (−17) = 0.
Отсюда n · (u + (−4)) = 24, n · (v + (4)) = 18.
Выражения в скобках целые. Следовательно, n должно делить одновременно 24 и 18. Наибольшее возможное n равно их НОД: НОД(24; 18) = 6.
Проверим достижимость: при n = 6 выбираем u = 8, v = −1. Оба значения целые, а один проход даёт смещение (4; 3).
Проверка по x: 4 + 6 · 4 + (−28) = 0.
Проверка по y: −1 + 6 · 3 + (−17) = 0.
Таким образом, указанное число повторений возможно. Большее число не может делить обе необходимые координаты смещения, поэтому максимум доказан.
Ответ: 6.

Помочь улучшить сайт

Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINFFFB86F.

Сообщение увидит только команда сайта: на странице оно не публикуется.

Задание EGEINFFFB86F: Черепаха, Чертёжник и Робот

Решение задания EGEINFFFB86F

Помочь улучшить сайт

Комментарии к решению