Как решить задание обоснованно кодом?

Question

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

1. заменить (v, w) 
2. нашлось (v)

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

НАЧАЛО
ПОКА нашлось (900) или нашлось(8000) или нашлось(70)
  заменить(70, 8)
  заменить(900, 70)
  заменить(8000, 900)
КОНЕЦ ПОКА
КОНЕЦ

Известно, что на вход программы поступила строка из 71 символа. Определите минимальное четырехзначное число, которое может являться результатом работы исполнителя. Я решил это задание вот таким кодом

for i in ['7', '8', '9']:
    s = '100' + i + '0' * 67
    while '900' in s or '8000' in s or '70' in s:
        s = s.replace('70', '8', 1)
        s = s.replace('900', '70', 1)
        s = s.replace('8000', '900', 1)
    print(s)

Можно ли решить это задание другим способом, типо метода перебора и тд

Answer 1

Данную задачу можно решить методом перебора всех четырёхзначных чисел следующим образом:

# Функция преобразования строки (программа исполнителя Редактор)
def transform_string(s):
    # Выполнение замены, пока в строке есть хотя бы одна из цепочек
    while '900' in s or '8000' in s or '70' in s:
        if '70' in s:
            s = s.replace('70', '8', 1)
        if '900' in s:
            s = s.replace('900', '70', 1)
        if '8000' in s:
            s = s.replace('8000', '900', 1)

    return s

min_result = 10000 # максимально возможный диапазон четырёхзначного числа

# Перебор всех четырехзначных чисел (от 1000 до 9999)
for i in range(1000, 10000):
    # Создаем строку из числа и дополняем её нулями до длины в 71 символ
    s = str(i) + '0' * (71 - len(str(i)))
    # Преобразуем строку через "программу исполнителя Редактор"
    result = int(transform_string(s))

    if 1000 <= result < min_result:
        min_result = result

print(min_result)

На выводе будет интересующее нас число, которое равно:

Это число и есть

минимальное четырехзначное число, которое может являться результатом работы исполнителя

БЛОГ НА HUSL

Как решить задание обоснованно кодом?

Ответы (1 шт):