. Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды. Команда нашлось (u) проверяет, встречается ли цепочка u в строке, поданной на вход исполнителя. Команда заменить (u, w) заменяет в строке первое слева вхождение цепочки u на цепочку w. Дана программа для исполнителя Редактор: НАЧАЛО ПОКА нашлось (33) ИЛИ нашлось (22) ЕСЛИ нашлось (33) ТО заменить (33, 2) ИНАЧЕ заменить (22, 3) КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ Какая строка получится в результате применения приведённой выше программы к строке, состоящей из: 1) 500 идущих подряд цифр 3; 2) 500 идущих подряд цифр 2; 3) 300 идущих подряд цифр 3 и следующих за ними 200 идущих подряд цифр 2.
Чтобы понять, как будет работать программа Редактора, давайте проанализируем каждую из предоставленных строк по отдельности. Программа использует цикл, который проверяет наличие последовательностей "33" и "22", и в зависимости от этого заменяет "33" на "2" или "22" на "3".
- Для строки из 500 идущих подряд цифр 3:
Строка будет выглядеть так: 333...3 (500 раз).
На первой итерации цикла команда "нашлось (33)" вернёт истину, так как "33" присутствует в строке.
Команда "заменить (33, 2)" заменит первое встреченное "33" на "2". После первой замены строка станет:
33233...3(398 раз 3).На второй итерации команды "нашлось (33)" снова вернёт истину, и повторится процесс замены:
32233...3(397 раз 3).
Этот процесс будет продолжаться, где на каждой итерации будет заменяться одно "33" на "2", вплоть до тех пор, пока не останется "33" в строке.
Таким образом, после 250 циклов, строка превратится в:
22222222...2 (250 раз 2).
В конечном итоге, останется строка из 250 двоек.
- Для строки из 500 идущих подряд цифр 2:
Строка будет выглядеть так: 222...2 (500 раз).
На первой итерации цикла команда "нашлось (22)" вернёт истину, так как "22" присутствует в строке.
Команда "заменить (22, 3)" заменит первое встреченное "22" на "3". После первой замены строка станет:
33222...2(498 раз 2).На второй итерации команды "нашлось (22)" снова вернёт истину, и повторится процесс замены:
33322...2(497 раз 2).
Этот процесс будет продолжаться, и на каждой итерации программа будет заменять одно "22" на "3".
Таким образом, после 250 циклов, строка превратится в:
33333333...3 (250 раз 3).
В конечном итоге, останется строка из 250 троек.
- Для строки из 300 идущих подряд цифр 3, за которыми следуют 200 идущих подряд цифр 2:
Строка будет выглядеть так: 333...3222...2 (300 раз 3 и 200 раз 2).
На первой итерации цикла команда "нашлось (33)" вернёт истину, и произойдет замена:
33233...3222...2(299 раз 3 и 200 раз 2).На следующей итерации команда снова подтвердит наличие "33", и произойдет замена:
32233...3222...2(298 раз 3 и 200 раз 2).
Этот процесс будет продолжаться, пока не останется "33".
Когда число троек станет достаточно малым, например после 100 итераций, оставшиеся последние 100 троек будут заменены на двойки, а на их место в строке будут возникать тройки.
Таким образом, к моменту завершения программы останется строка, в которой будет:
222222...222 (300 раз 2 и 200 раз 3).
В конечном итоге, будет строка из 200 двоек и 300 троек, где каждого элемента останется ровно столько, сколько мы подали на вход.
Резюмируя:
- 250 двоек;
- 250 троек;
- В итоге 200 двоек и 300 троек полное преобразование строки.
