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

12.01 Исполнитель «Редактор» – известная строка

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

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

Задача 1#23401

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

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

2. наш лось(v)

Дана программа для исполнителя ХИ-ХИ:

Н АЧА ЛО

   П ОК А нашлось(10) И ЛИ наш лось(11) ИЛИ нашлось(330)

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

         Т О заменить(10,1)

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

         Т О заменить(11,3)

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

         Т О заменить(330,100)

      К ОН ЕЦ ЕС ЛИ

   К ОН ЕЦ ПО КА

К ОНЕ Ц

Найдите произведение цифр строки, для полученной в результате применения приведённой выше программы к строке

11 ...1100 ...0033 ...33.
◟--◝1◜-◞◟--◝10◜0-◞◟--◝3◜-◞

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

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

Начнем работу нашего алгоритма. Так как в исходной строке мы нашли 10  , то заменим 10  на 1  .

Получим строку 10 ...0333
 ◟-◝9◜9 ◞

На данной итерации цикла строка больше меняться не будет, идем дальше. Вновь встречаем 10  , можем заметить, что если встречается 10  , то количество 0  уменьшается на один, а количество 1  остается неизменным, тогда можем выполнить это дейстие еще 99 раз, пока у нас не закончатся 0  .

Получим строку 1333

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

Запишем в ответ произведение элементов полученной после работы алгоритма строки: 1⋅3⋅3 ⋅3 = 27  . Запишем в ответ данное значение.

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

s = "1" * 1 + "0" * 100 + "3" * 3
while "10" in s or "11" in s or "330" in s:
    if "10" in s:
        s = s.replace("10", "1", 1)
    elif "11" in s:
        s = s.replace("11", "3", 1)
    elif "330" in s:
        s = s.replace("330", "100", 1)
arr = [int(i) for i in s]
for i in range(len(arr) - 1):
    arr[i + 1] *= arr[i]
print(arr[-1])

Ответ: 27

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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