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

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

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

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

Задача 1#62827

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

Цикл

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

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

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

Означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным). Ручке был дан для исполнения следующий алгоритм:

НАЧАЛО

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

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

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

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

   КОНЕЦ

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

КОНЕЦ

Определите минимальное натуральное значение N > 1, для которого найдутся такие значения чисел a и b, что после выполнения программы Ручка возвратится в исходную точку?

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

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

Составим 2 уравнения. Так как робот должен вернуться в исходную точку, то сумма всех его перемещений равна нулю:

− 47+ n(a+ 31)+ 82 = 0  по оси X

− 19+ n(9+ b)− 23 = 0  по оси Y

n(a +31) = − 35

n(9 +b) = 42

Теперь наша задача найти число на которое делится 42 и 35 нацело, так как числа a, b у нас целые. Такое число одно - это 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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