Исполнитель Чертежник

Чертежник является одним из возможных вариантов исполнителя встречающихся в задаче №14 единого государственного экзамена по информатике.

Система команд исполнителя ЧЕРТЕЖНИК содержит следующие команды:

  • сместиться на (a, b), где a, b – целые числа. Эта команда перемещает Чертёжника из точки с координатами (x, y) в точку с координатами (x + a; y + b).
  • Цикл
    • ПОВТОРИ число РАЗ
    •  последовательность команд
    • КОНЕЦ ПОВТОРИ
    означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным).

Рассмотрим задачу №14 из демонстрационного варианта ЕГЭ по информатике 2015 года.

Задача. Чертёжнику был дан для исполнения следующий алгоритм (буквами n, a, b обозначены неизвестные числа, при этом n > 1):

  • НАЧАЛО
  •  сместиться на (–3, –3)
  •  ПОВТОРИ n РАЗ
  •   сместиться на (a, b)
  •   сместиться на (27, 12)
  •  КОНЕЦ ПОВТОРИ
  •  сместиться на (–22, -7)
  • КОНЕЦ

Укажите наименьшее возможное значение числа n, для которого найдутся такие значения чисел a и b, что после выполнения программы Чертёжник возвратится в исходную точку.

Решение.

Для решения задачи введем систему координат:

  • Перемещение чертежника происходит на плоскости (изменяются две координаты).
  • Начало прямоугольной системы координат свяжем со стартовым положением Чертежника.
  • За положительное направление выберем направление вертикальной оси вверх и горизонтальной оси направо.

Построим перемещения Чертежника в соответствии с заданной программой:

  1. Первая инструкция «сместиться на (–3, –3)» - рис. 1(а).
  2. Последняя инструкция «сместиться на (–22, –7)»: так как исполнитель возвращается в точку, из которой начал движение, то выполнив указанную инструкцию Чертежник окажется в начале координат (рис. 1(б)).
  3. Между точками нц (начало цикла) и кц (конец цикла) Чертежник выполнял перемещения в цикле. Результирующие этих перемещений изображены на рис. 1 (в) пунктирной линией.

Траектория чертежника

  1. Нетрудно заметить, что сумма проекций перемещений Чертежника на соответствующие координатные оси равна 0, т. е.
    • для оси ох: –3 + (–22) + n (a + 27) = 0  (1)
    • для оси оу: –3 + (–7) + n (b + 27) = 0  (2), где n – количество шагов в цикле
  2. Решим полученную систему уравнений:
    • n (a + 27) = 25  (1)
    • n (b + 27) = 10  (2)
  3. Для того чтобы система уравнений была разрешима в целых числах относительно a и b, число n должно быть одновременно делителем чисел 25 и 10.
  4. Наименьший общий делитель для 25 и 10 равен 5.

Ответ. 5

В контрольно-измерительных материалах экзаменационной работы в задаче №14 могут встречаться следующие варианты исполнителей: