Форум » Выполнение и анализ алгоритмов для исполнителей » 12 задание, задача 260 » Ответить
12 задание, задача 260
Дондокова: 260) (Е. Джобс) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редак-тор может выполнять две команды, в обеих командах v и w обозначают цепочки символов. заменить (v, w) нашлось (v) Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если це-почки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Дана программа для Редактора: ПОКА нашлось (900) или нашлось(8000) или нашлось(70) заменить(70, 8) заменить(900, 70) заменить(8000, 900) КОНЕЦ ПОКА Известно, что на вход программы поступила строка из 71 символа. Определите минимальное четырехзначное число, которое может являться результатом работы исполнителя. Не пойму из каких символов состоит исходная строка? В ответе 1008.
Ответов - 18, стр:
1 2 All
Поляков: Дондокова пишет: Не пойму из каких символов состоит исходная строка? Именно это и предстоит определить. Известно, что там все цифры.
Anna1915: Можно ли идти от обратного? перебирать все 4-х значные числа и применять к ним алгоритм с обратной заменой (8 на 70 и т.д.) и если строка после замен имеет длину 71 знак, то найти мин
Поляков: Anna1915 пишет: Можно ли идти от обратного? перебирать все 4-х значные числа и применять к ним алгоритм с обратной заменой (8 на 70 и т.д.) и если строка после замен имеет длину 71 знак, то найти мин Не получится, потому что у вас цикл с условием, количество повторений неизвестно.
Anna1915: Это мухлеж или это норм.решение? [pre2] s1=[] for i in range(1000,10000): s1=str(i) k=0 while '900' in s1 or '8' in s1 or '70' in s1: s1=s1.replace('8','70',1) if len(s1)==71: print(i) break s1=s1.replace('70','900',1) if len(s1)==71: print(i) break s1=s1.replace('900','8000',1) if len(s1)==71: print(i) break [/pre2]
Поляков: Anna1915 пишет: Это мухлеж или это норм.решение? Это мухлеж, потому что вы использовали известный вам ответ.
Anna1915: там же 4-х значные, написано, я перебираю их, не подгоняю к 1008. Решение от обратного.
Поляков: Anna1915 пишет: Решение от обратного. Если вы идете от обратного, то и порядок замен нужно поменять (наоборот). Проблема в том, что каждая из замен может сработать или не сработать (если нет заменяемого образца). То есть нужно учитывать оба варианта. То, что в данном случае ответ получился верный, не гарантирует, что так можно делать для любой задачи. Чтобы уверенно использовать такой прием, нужно доказать его правильность.
Anna1915: вот так? [pre2] s1=[] for i in range(1000,10000): s1=str(i) while '900' in s1 or '8' in s1 or '70' in s1: if '900' in s1: s1=s1.replace('900','8000',1) if len(s1)==71: print(i) break if '70' in s1: s1=s1.replace('70','900',1) if len(s1)==71: print(i) break if '8' in s1: s1=s1.replace('8','70',1) if len(s1)==71: print(i) break [/pre2]
Поляков: Anna1915 пишет: вот так? Да. Но теперь осталось доказать, что это работает в общем виде. Для меня это пока не очевидно.
Anna1915: Задача 272. Известно, что начальная строка состоит только из цифр 1 и 3. В ходе работы алгоритма получилась строка, не содержащая единиц. Укажите максимальную длину входной строки, если известно, что после выполнения алгоритма сумма всех цифр в полученной строке равна 404. мысли: так как на выходе получаем строку без 1, т.е. состоящую из 2 и3. и мы знаем, что сумма цифр строки=404. нам нужну найти мак.длину строки (из 2 и 3). Максимальной она будет, если будет больше 2. если 404-3=401, но сумма двоек не м.б. 401 (т.к. не делится на 2), значит вычитаем еще одну тройку 401-3=398. 398 уже делится на 2 и получаем 199 двоек. итого 199 двоек и 2 тройки. т.о. длина строки 199+2=201. Проверим на программе от обратного: [pre2] import itertools s1=[] s2=[] s='2'+'3' g=0 for k in range(199,1,-1): for m in range(2,1,-1): s='2'*k+'3'*m for i in itertools.permutations(s): s1=''.join(i) s2 = [int(x) for x in s1] if sum(s2)==404: while '12' in s1 or '13' in s1: if '23' in s1: s1=s1.replace('23','13',1) if '23' in s1: s1=s1.replace('23','31',1) if '21' in s1: s1=s1.replace('21','12',1) print(len(s1)) break if sum(s2)==404: break if sum(s2)==404: break [/pre2] обратный работает?
Поляков: Anna1915 пишет: обратный работает? Вам повезло, что 1) такая строка (s='2'*199+'3'*2) действительно может быть результатом работы алгоритма и 2) вы получили нужный вариант на одной из первый итераций цикла. Резюме: на ЕГЭ для получения правильного ответа можно использовать все, что угодно, но в качестве обоснованного метода с гарантированным результатом я бы такой подход никому не рекомендовал.
Anna1915: Эти рассуждения верные для 272? "Известно, что начальная строка состоит только из цифр 1 и 3. В ходе работы алгоритма получилась строка, не содержащая единиц. Укажите максимальную длину входной строки, если известно, что после выполнения алгоритма сумма всех цифр в полученной строке равна 404. мысли: так как на выходе получаем строку без 1, т.е. состоящую из 2 и3. и мы знаем, что сумма цифр строки=404. нам нужну найти мак.длину строки (из 2 и 3). Максимальной она будет, если будет больше 2. если 404-3=401, но сумма двоек не м.б. 401 (т.к. не делится на 2), значит вычитаем еще одну тройку 401-3=398. 398 уже делится на 2 и получаем 199 двоек. итого 199 двоек и 2 тройки. т.о. длина строки 199+2=201."
Поляков: Anna1915 пишет: итого 199 двоек и 2 тройки Вы не доказали, что такая строка действительно может быть получена в результате работы этого алгоритма.
zarema_s@mail.ru: Если добавить в рассуждения, которые написала Anna1915 следующее: 1. количество троек в строке не меняется. 2. если единички стоят перед тройками, то они заменяются на двойки. можно написать программу и проверить для данного алгоритма. 3. так как два символа заменяются другими двумя, изначальная длина строки не меняется, т.е. если было допустим в строке 30 символов, то 30 символов и останется, и поэтому, если мы хотим, чтобы исходная строка была максимальной длины, то нужно, чтобы в итоговой строке было как можно больше двоек (как и написано у Anna195). т.е. в нашем случае 199 двоек и 2 тройки. 4. такая строка может быть получена, если в исходной строке 199 единичек и две тройки (следует из пункта 2).
aln1947: А такая программа для 12.72 подойдет? [pre2].. #12.272 m=0 for x in range(1,300): for y in range (1,10): s='1'*x+'3'*y while '12' in s or '13' in s: s=s.replace('12','21',1) s = s.replace('31', '23', 1) s = s.replace('13', '23', 1) if s.count('1')==0: summ=s.count('2')*2+s.count('3')*3 if summ==404: m=max(m,x+y) print(m) # Rez = 201, t = 3 min .[/pre2],
полная версия страницы