Тема 12. Алгоритмы – анализ сложных алгоритмов

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

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

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

Задача 1#26064

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

Начало

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

Повтори N  раз

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

   Сместиться на (15,− 9)

Конец повтори

Сместиться на (2,− 10)

Конец

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

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

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

Запишем систему:

(
{30 + N * (a + 15) + 2 = 0
(30 + N * (b + (-9)) + (- 10) = 0

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

(
{ N * (a + 15) = -32

( N * (b -9) = -20

Найдем НОД (наибольший общий делитель) чисел 32  и 20  .
Получим ответ: 4

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

max_n = 0
for n in range(1, 33):
    if (-32 % n == 0) and (-20 % n == 0):
        a = (-32 // n) - 15
        b = (-20 // n) + 9
        x = 30 + n * (a + 15) + 2
        y = 30 + n * (b - 9) - 10
        if x == 0 and y == 0:
            max_n = n
print(max_n)

Ответ: 4

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

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

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

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

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

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

Бесплатное онлайн-обучение

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

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

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

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

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

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

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

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