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

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

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

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

Задача 1#7444

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

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

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

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

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

НАЧАЛО

ПОКА нашлось (*2) ИЛИ нашлось (*6) ИЛИ нашлось (*7)

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

ТО заменить (*2, *767)

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

ТО заменить (*6, *)

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

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

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

На вход приведённой программе поступает строка, начинающаяся с символа “*”, а затем содержащая 20 цифр 2, 100 цифр 6 и 42 цифры 7, расположенных в произвольном порядке. Определите сумму числовых значений цифр строки, получившейся в результате выполнения программы. Так, например, если результат работы программы представлял бы собой строку, состоящую из 50 цифр 2, то верным ответом было бы число 100.

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

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

Принцип действия данной программы можно воспринимать как фильтр, через который по очереди пропускаются одни числа, а выводятся другие (или не выводятся вообще). Этим фильтром служит знак “*”. При пропускании через фильтр цифры 6, она не выводится, т.е. каждая шестерка изначальной строки удаляется, после чего в конечной строке не будет ни одной шестерки.

Если проанализировать сам алгоритм программы, то можно понять, что каждая двойка преобразуется в две тройки, каждая семерка - в одну тройку. В результате конечная строка будет состоять лишь из одних троек.

Исходя из этого, программа преобразует 20 двоек в 40 троек, 42 семерки в 42 тройки, все шестерки будут удалены. Всего троек 82, их сумма равна 3 ⋅ 82 = 246.

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

s = ’*’ + ’2’ * 20 + ’6’ * 100 + ’7’ * 42

while ’*2’ in s or ’*6’ in s or ’*7’ in s:
    if ’*2’ in s:
        s = s.replace(’*2’, ’*767’, 1)
    elif ’*6’ in s:
        s = s.replace(’*6’, ’*’, 1)
    elif ’*7’ in s:
        s = s.replace(’*7’, ’3*’, 1)

s = s.replace(’*’, ’’)

sum_of_digits = sum(int(digit) for digit in s)
print(sum_of_digits)



Ответ: 246

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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