Тема 12. Алгоритмы – анализ сложных алгоритмов
12.02 Исполнитель «Чертежник»
Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела алгоритмы – анализ сложных алгоритмов
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#53432

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

Сместиться на (16, -21)

Повтори N раз

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

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

конец

Сместиться на (-60, -12)

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

Показать ответ и решение

Запишем два уравнения и составим из них систему. Система будет иметь такой вид:

(
{16 +n (a − 1)− 60 = 0
(− 21+ n(b− 2)− 12 = 0

Перенесём известную часть на правую сторону. Тогда получим:

(
{ n(a− 1) = 44

( n(b− 2) = 33

Поделим данные уравнения на n. Получим:

(        44
{ a− 1 = n-
( b− 2 = 33
         n

НОД для 44 и 33 равен 11. Ответ:11

Решение питоном:

 for n in range(100):
     for a in range(-100, 100):
         for b in range(-100, 100):
             x = y = 0
             x += 16
             y -= 21
             for i in range(n):
                 x += a
                 y += b
                 x -= 1
                 y -= 2
             x -= 60
             y -= 12
             if x == 0 and y == 0:
                 print(n)

 

Ответ: 11

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное обучение
в Школково

Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!