Задание №12: Исполнитель Редактор и преобразование строк
Основные типы и прототипы задания №12:
Исполнитель Редактор
Циклы 'пока нашлось'
Поиск простых чисел в строке
Условие задания
На ленте исполнителя МТ в соседних ячейках записано двоичное представление целого положительного числа без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей справа от последовательности ячейке. Программа для исполнителя:
Команды движения каретки: L – влево, R – вправо, N – отсутствие сдвига, S – стоп. После выполнения программы на ленте оказалась двоичная запись числа 156. Определите десятичное значение наибольшего числа, меньшего, чем 10000, которое могло быть записано на ленте до начала работы программы.
Команды движения каретки: L – влево, R – вправо, N – отсутствие сдвига, S – стоп. После выполнения программы на ленте оказалась двоичная запись числа 156. Определите десятичное значение наибольшего числа, меньшего, чем 10000, которое могло быть записано на ленте до начала работы программы.
Ответ:
8035
Решение на Python: Перебор: какое число было на ленте
table = { ("q0", "λ"): ("λ", "L", "q1"), ("q1", "0"): ("1", "L", "q1"), ("q1", "1"): ("0", "L", "q1"), ("q1", "λ"): ("λ", "S", "q1"), } answer = 0 for n in range(1, 10000): tape = ["λ"] * 20 + list(bin(n)[2:]) + ["λ"] * 20 head = 20 + len(bin(n)[2:]) state = "q0" while True: new_symbol, move, state = table[(state, tape[head])] tape[head] = new_symbol if move == "L": head -= 1 elif move == "R": head += 1 elif move == "S": break result = "".join(tape).replace("λ", "") if int(result, 2) == 156: answer = n print(answer)
Этот код разобран по шагам в разборе задания №12: там же типичные ошибки и лайфхаки.