Форум » Выполнение и анализ алгоритмов для исполнителей » Задача 5647 » Ответить
Задача 5647
alexkovoron: [quote] (К. Багдасарян) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов. 1. заменить (v, w) 2. нашлось (v) Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Дана программа для исполнителя Редактор: НАЧАЛО ПОКА нашлось (>1) ИЛИ нашлось (>2) ИЛИ нашлось (>0) ЕСЛИ нашлось (>1) ТО заменить (>1, 20>) КОНЕЦ ЕСЛИ ЕСЛИ нашлось (>2) ТО заменить (>2, 00>) КОНЕЦ ЕСЛИ ЕСЛИ нашлось (>0) ТО заменить (>0, 10>) КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ На вход приведённой выше программе поступает строка, начинающаяся с символа «>», а затем k цифр «0», m цифр «1» и n цифр «2», расположенных в произвольном порядке. Известно, что 100 ≤ k ≤ 200, 100 ≤ m ≤ 200, 100 ≤ n ≤ 200. Определите значение k, при котором сумма числовых значений цифр строки, получившейся в результате выполнения программы, будет равно 599.[/quote] Добрый день, как можно ускорить решение данной программы? [pre2] for k in range(100,201): for m in range(100,201): for n in range(100,201): a = '>' + '0'*k + '1'*m + '2'*n while '>1' in a or '>2' in a or '>0' in a: if '>1' in a: a = a.replace('>1','20>',1) if '>2' in a: a = a.replace('>2','00>',1) if '>0' in a: a = a.replace('>0','10>',1) a = a.replace('>','') d = 0 for x in a: d+=int(x) if d==599: print(k) [/pre2]
Ответов - 5
bagkar: Эту задачу лучше решать без программирования. Попробуйте понять: 1) Сколько получится "1" и"2" в итоговой строке 2) Какая максимальная сумма возможна в принципе.
z1gor: так в этой же задаче несколько ответов возможно. задача составлена некорректно. ученики не смогут понять какое именно k выводить: наибольшее или наименьшее
Поляков: z1gor пишет: несколько ответов возможно. Нет, решение единственно.
ganilova: [pre2] for m in range(100, 201): for n in range(100,201): for k in range(100, 201): s = '>' + '0'* k + '1' * m + '2' * n #s = '>' + '1' * m + '2' * n + '0'* k while '>1' in s or '>0' in s or '>2' in s: if '>1' in s: s = s.replace('>1', '20', 1) if '>2' in s: s = s.replace('>2', '00', 1) if '>0' in s: s = s.replace('>0', '10', 1) if sum(list(map(int, list(s[:-1])))) == 599: print(k, m, n) exit() [/pre2]
Ж: Эта программа выдает верный ответ. Просто единиц и двоек берем по максимуму. [pre2] for n in range(100,201): s=list('1'*200+'2'*200+'*'*n) shuffle(s) s='>'+''.join(s) while '>1' in s or '>2' in s or '>*' in s: if '>1' in s: s=s.replace('>1','111>',1) if '>2' in s: s = s.replace('>2', '1>', 1) if '>*' in s: s = s.replace('>*', '%2*>', 1) if sum (int(c) for c in s if c in '123')==1190: print(n) break [/pre2]
полная версия страницы