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

12.02 Исполнитель «Редактор» – строка с произвольным порядком цифр

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

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

Задача 1#11769

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в которых v  и w  обозначают последовательности цифр:

   А) заменить (v,w ).

Эта команда заменяет в строке первое слева вхождение последовательности v  на последовательность w.

Например, выполнение команды заменить (333,3)  преобразует строку 1333572  в строку 13572.

Если в строке нет вхождений последовательности v,  то выполнение команды заменить (v,w)  не меняет эту строку.

   Б) Наш лось (v).

Эта команда проверяет, встречается ли последовательность v  в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина»  , в противном случае возвращает значение «ложь»  . Строка исполнителя при этом не изменяется.

Цикл

   П ОК А усл овие

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

   К ОН ЕЦ ПО КА

Выполняется, пока условие истинно.

Какая строка получится в результате применения приведённой ниже программы к строке, содержащей 40  цифр     4  , 40  цифр 8  и 50  цифр 2  , расположенных в произвольном порядке. Запишите без разделителей символы, которые имеют порядковые номера 25,71,105  (отсчет идет с 1  ).

Н АЧА ЛО

   П ОК А нашлось(28) И ЛИ наш лось(84) ИЛИ нашлось(24)

   ЕС ЛИ наш лось(24)

      Т О заменить(24,42)

   И НАЧ Е ЕСЛ И наш лось(84)

      Т О заменить(84,48)

   И НАЧ Е ЕСЛ И наш лось(28)

      Т О заменить(28,82)

   К ОН ЕЦ ЕС ЛИ

   К ОН ЕЦ ПО КА

К ОНЕ Ц

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

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

Так как цифры расположены в произвольном порядке, то мы можем поставить их в любом порядке. Пусть наша строка будет иметь вид 4 ...4 8...8 2...2
◟-◝4◜0 ◞ ◟ ◝4◜0 ◞ ◟ ◝5◜0 ◞

Начнем работу нашего алгоритма. Так как в исходной строке мы не находим ни одной из подстрок 28,84,24,  то в цикл мы не заходим, тогда строка не изменится, значит, нужно лишь определить элементы, порядковые номера которых нам даны в условии. Так как порядковые номера начинаются с 1  , а индексы в строке с 0  , то, чтобы верно определить нужные нам индексы, мы вычтем из порядковых номеров 1  . Получим индексы 24,70,104.  Осталось лишь определить, какие это элементы в строке)) Так как первые 40 элементов (индексы от 0 до 39) — это 4  , то первый элемент — 4  . Далее на отрезке [40, 79] расположены 8  , так как 40 ≤ 70 ≥ 79  , то второе число — 8  . Последнее расположено в промежутке 80 ≤ 104 ≥ 129  , а это число 2  .

Найденные цифры запишем в ответ без пробелов, то есть ответ — 482.

Решение прогой:

s = "4" * 40 + "8" * 40 + "2" * 50
while "28" in s or "84" in s or "24" in s:
    if "24" in s:
        s = s.replace("24", "42", 1)
    elif "84" in s:
        s = s.replace("84", "48", 1)
    elif "28" in s:
        s = s.replace("28", "82", 1)
print(s[25 - 1], s[71 - 1], s[105 - 1], sep=’’)

Ответ: 482

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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