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

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

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

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

Задача 1#6278

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

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

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

Первая команда заменяет в строке первое слева вхождение цепочки v  на цепочку w  . Если цепочки v  в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка      v  в строке исполнителя Панцирь. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь».

Дана программа для исполнителя Панцирь:

НАЧАЛО

ПОКА нашлось(5)  ИЛИ нашлось(77 )  ИЛИ нашлось(222 )

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

ТО заменить(5,77)

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

ТО заменить(77,7)

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

ТО заменить(222,5)

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Найдите число, которое будет получено в результате перемножения всех цифр строки, напечатанной после применения приведённой выше программы к строке 55 ...55 77...77 22...22 .
◟--◝◜--◞ ◟-◝◜--◞ ◟--◝◜--◞
   37       56       5

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

Аналитическое решение

Алгоритм заменит все пятерки на 77, пока они не окончатся. Получится строка из 74 + 56 = 130  семерок.

Далее алгоритм будет уменьшать количество семерок: 130 − >  65− >  33− >  17− >  9− >  5− > 3 − > 1  . Посмотрим, что происходит с двойками в получившейся строке: 722222 − >  7522− >  77722−  > 7722 − > 722  .

На этом алгоритм завершается. Произведение цифр - 28.

Программное решение:

s = ’5’*37 + ’7’*56 + ’2’*5
while ’5’ in s or ’77’ in s or ’222’ in s:
    if ’5’ in s:
        s = s.replace(’5’, ’77’, 1)
    elif ’77’ in s:
        s = s.replace(’77’, ’7’, 1)
    else:
        s = s.replace(’222’, ’5’, 1)
p = 1
for i in s:
    p *= int(i)
print(p)

Ответ: 28

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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