Автор | Сообщение |
|
Отправлено: 25.05.21 13:18. Заголовок: 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
[только новые]
|
|
|
| Администратор
|
Сообщение: 2836
|
|
Отправлено: 31.05.21 20:56. Заголовок: Дондокова пишет: Не ..
Дондокова пишет: цитата: | Не пойму из каких символов состоит исходная строка? |
|
Именно это и предстоит определить. Известно, что там все цифры.
|
|
|
|
Отправлено: 23.11.21 22:58. Заголовок: Идея
Можно ли идти от обратного? перебирать все 4-х значные числа и применять к ним алгоритм с обратной заменой (8 на 70 и т.д.) и если строка после замен имеет длину 71 знак, то найти мин
|
|
|
|
| Администратор
|
Сообщение: 3030
|
|
Отправлено: 23.11.21 23:09. Заголовок: Anna1915 пишет: Можн..
Anna1915 пишет: цитата: | Можно ли идти от обратного? перебирать все 4-х значные числа и применять к ним алгоритм с обратной заменой (8 на 70 и т.д.) и если строка после замен имеет длину 71 знак, то найти мин |
|
Не получится, потому что у вас цикл с условием, количество повторений неизвестно.
|
|
|
|
Отправлено: 24.11.21 19:11. Заголовок: Это мухлеж или это н..
Это мухлеж или это норм.решение? 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
|
|
|
|
| Администратор
|
Сообщение: 3033
|
|
Отправлено: 24.11.21 19:26. Заголовок: Anna1915 пишет: Это ..
Anna1915 пишет: цитата: | Это мухлеж или это норм.решение? |
|
Это мухлеж, потому что вы использовали известный вам ответ.
|
|
|
|
Отправлено: 24.11.21 19:33. Заголовок: там же 4-х значные, ..
там же 4-х значные, написано, я перебираю их, не подгоняю к 1008. Решение от обратного.
|
|
|
|
| Администратор
|
Сообщение: 3034
|
|
Отправлено: 24.11.21 19:50. Заголовок: Anna1915 пишет: Реш..
Anna1915 пишет: Если вы идете от обратного, то и порядок замен нужно поменять (наоборот). Проблема в том, что каждая из замен может сработать или не сработать (если нет заменяемого образца). То есть нужно учитывать оба варианта. То, что в данном случае ответ получился верный, не гарантирует, что так можно делать для любой задачи. Чтобы уверенно использовать такой прием, нужно доказать его правильность.
|
|
|
|
Отправлено: 24.11.21 20:01. Заголовок: вот так? s1= for i..
вот так? 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
|
|
|
|
| Администратор
|
Сообщение: 3035
|
|
Отправлено: 24.11.21 20:03. Заголовок: Anna1915 пишет: вот ..
Anna1915 пишет: Да. Но теперь осталось доказать, что это работает в общем виде. Для меня это пока не очевидно.
|
|
|
|
Отправлено: 01.12.21 18:01. Заголовок: Обратный метод
Задача 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. Проверим на программе от обратного: 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 обратный работает?
|
|
|
|
| Администратор
|
Сообщение: 3057
|
|
Отправлено: 01.12.21 18:15. Заголовок: Anna1915 пишет: обра..
Anna1915 пишет: Вам повезло, что 1) такая строка (s='2'*199+'3'*2) действительно может быть результатом работы алгоритма и 2) вы получили нужный вариант на одной из первый итераций цикла. Резюме: на ЕГЭ для получения правильного ответа можно использовать все, что угодно, но в качестве обоснованного метода с гарантированным результатом я бы такой подход никому не рекомендовал.
|
|
|
|
|
Отправлено: 01.12.21 18:22. Заголовок: Эти рассуждения верн..
Эти рассуждения верные для 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."
|
|
|
|
| Администратор
|
Сообщение: 3058
|
|
Отправлено: 01.12.21 18:26. Заголовок: Anna1915 пишет: итог..
Anna1915 пишет: цитата: | итого 199 двоек и 2 тройки |
|
Вы не доказали, что такая строка действительно может быть получена в результате работы этого алгоритма.
|
|
|
|
Отправлено: 13.01.22 01:36. Заголовок: Если добавить в расс..
Если добавить в рассуждения, которые написала Anna1915 следующее: 1. количество троек в строке не меняется. 2. если единички стоят перед тройками, то они заменяются на двойки. можно написать программу и проверить для данного алгоритма. 3. так как два символа заменяются другими двумя, изначальная длина строки не меняется, т.е. если было допустим в строке 30 символов, то 30 символов и останется, и поэтому, если мы хотим, чтобы исходная строка была максимальной длины, то нужно, чтобы в итоговой строке было как можно больше двоек (как и написано у Anna195). т.е. в нашем случае 199 двоек и 2 тройки. 4. такая строка может быть получена, если в исходной строке 199 единичек и две тройки (следует из пункта 2).
|
|
|
|
Отправлено: 11.01.22 16:26. Заголовок: Программа 12.272
А такая программа для 12.72 подойдет? .. #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 . ,
|
|
|
Ответов - 18
, стр:
1
2
All
[только новые]
|
|