ЕГЭ-2015 задание 14.

Анализ и выполнение алгоритмов для исполнителя

Теория

Для решения данного задания необходимо знать:

  • правила выполнения линейных, разветвляющихся и циклических алгоритмов
  • исполнитель – это человек, группа людей, животное, машина или другой объект, который может понимать и выполнять некоторые команды
  • в школьном алгоритмическом языке нц обозначает «начало цикла», а кц – «конец цикла»; все команды между нц и кц – это тело цикла, они выполняются несколько раз
  • запись нц для i от 1 до n обозначает начало цикла, в котором переменная i (она называется переменной цикла) принимает последовательно все значения от 1 до n с шагом 1

Задача

Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться на (a, b), где a, b – целые числа. Эта команда перемещает Чертёжника из точки с координатами (x, y) в точку с координатами (x + a; y + b). Например, если Чертёжник находится в точке с координатами (4, 2), то команда сместиться на (2, −3) переместит Чертёжника в точку (6, −1).

Цикл
ПОВТОРИ число РАЗ
  последовательность команд
КОНЕЦ ПОВТОРИ

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

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

НАЧАЛО
 сместиться на (90, –40)
 ПОВТОРИ n РАЗ
    сместиться на (a, b)
    сместиться на (18, 14)
 КОНЕЦ ПОВТОРИ
 сместиться на (–9, -2)
 сместиться на (–6, -3)
КОНЕЦ

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

Решение

Запишем общее изменение координат Чертёжника в результате выполнения этого алгоритма:

Δx = 90 + n • (a+18) - 9 - 6 = 75 + n • (a+18)
Δy = -40 + n • (b+14) - 2 - 3 = -45 + n •(b+14)

Поскольку Чертёжник должен вернуться в исходную точку, эти величины должны быть равны нулю; следовательно, нужно найти наименьшее натуральное n, при котором система уравнений

n • (a+18) = -75
n • (b+14) = 45

разрешима в целых числах относительно a и b

Несложно заметить, что для этого число n должно быть одновременно делителем чисел 45 и 75

Наименьшее общее кратное чисел 45 и 75 равно 3

Правильный ответ: 3.

Яндекс.Метрика