Задача к ЕГЭ по информатике на тему «исполнитель «чертежник»» №1

Просмотров 7 Комментарии 0

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

Цикл

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

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

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

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

Исполнителю $M$ был дан для исполнения следующий алгоритм:

НАЧАЛО

сместиться на $(− 47,− 19)$

ПОВТОРИТЬ $N$ раз

cместиться на $(31,9)$

cместиться на $(a,b)$

КОНЕЦ

сместиться на $(82,− 23)$

КОНЕЦ

Определите минимальное натуральное значение $N > 1 » class=»math» width=»auto»>, для которого найдутся такие значения чисел <img decoding=$ и $b$ , что после выполнения программы $M$ возвратится в исходную точку.

Решение руками

Запишем систему для координат $x$ и $y$ , учитывая, что исполнитель вернулся в исходную точку:

( { -47 + N (31 + a) + 82 = 0 ( -19 + N (9 + b) -23 = 0

Перенесем выражения с N в одну сторону, а числа в другую:

( { N (31 + a) = -35 ( N (9 + b) = 42

Найдем НОД (наибольший общий делитель) чисел $35$ и $42$ .
Получим ответ: $7$

Решение программой

def find_min_n():
    for n in range(2, 100):
        if (-35 % n == 0) and (42 % n == 0):
            a = (-35 // n) - 31
            b = (42 // n) - 9
            x = -47 + n * (31 + a) + 82
            y = -19 + n * (9 + b) - 23
            if x == 0 and y == 0:
                return n
    return None

print(find_min_n())

Ответ: 7