Задания
Версия для печати и копирования в MS Word
Тип Д12 № 9198
i

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

Цикл

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

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

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

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

 

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

    НА­ЧА­ЛО

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

        ПО­ВТО­РИ … РАЗ

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

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

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

        сме­стить­ся на (20, 30)

    КОНЕЦ

 

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

Спрятать решение

Ре­ше­ние.

Пусть x  — ко­ли­че­ство по­вто­ре­ний цикла, а (a, b)  — век­тор, на ко­то­рый сдви­га­ет­ся Чертёжник в цикле.

Тогда за время ра­бо­ты про­грам­мы Чертёжник сдви­нет­ся на век­тор  левая круг­лая скоб­ка 4 плюс x умно­жить на a минус x плюс 20, 6 плюс x умно­жить на b минус 2 умно­жить на x плюс 30 пра­вая круг­лая скоб­ка = левая круг­лая скоб­ка x умно­жить на левая круг­лая скоб­ка a минус 1 пра­вая круг­лая скоб­ка плюс 24, x умно­жить на левая круг­лая скоб­ка b минус 2 пра­вая круг­лая скоб­ка плюс 36 пра­вая круг­лая скоб­ка .

По усло­вию также из­вест­но, что этот век­тор равен (0, 0).

Таким об­ра­зом, имеем:

x умно­жить на левая круг­лая скоб­ка a минус 1 пра­вая круг­лая скоб­ка = минус 24, x умно­жить на левая круг­лая скоб­ка b минус 2 пра­вая круг­лая скоб­ка = минус 36

От­ве­том будет наи­боль­ший общий де­ли­тель чисел -24 и -36  — 12. (Не стоит за­бы­вать, что ответ  — счётчик в цикле, по­это­му не может быть от­ри­ца­тель­ным чис­лом)

Раздел кодификатора ФИПИ: 1.6.2 Вы­чис­ли­мость. Эк­ви­ва­лент­ность ал­го­рит­ми­че­ских мо­де­лей