Отправлено: 08.03.19 17:25. Заголовок: Задание 14, номер 200

Дана программа для исполнителя Редактор:
НАЧАЛО
ПОКА нашлось (222)
заменить (222, 1)
заменить (111, 2)
КОНЕЦ ПОКА
КОНЕЦ
Какая строка получится в результате применения приведённой программы к строке вида 1…12…2 (2019 единиц и 2019 двоек)?

Не могу разобраться в этом задании. Где я ошибаюсь?
Начало - встречаю три двойки, заменяю единицей. До конца строки единиц нет, замена трех единиц на двойку в начале строки. И так три раза подряд. Потом с начала строки замена трех двоек на единицу и трех единиц на двойку. Получается 121..1(2010)2..2(2010).
Два цикла замена двоек и единиц приводит к строке 12221.11(2006)2..2(2004).
Теперь замена трех двоек с начала строки, замена трех единиц. Получается 1121..1(2003)2..2(2004).
Через пять циклов получается строка 121..1(1992)2..2(1992).
Т.о. от 121..1(2010)2..2(2010) к 121..1(1992)2..2(1992) у нас поглощаются по 8 цифр.
2010/8 получаю 251 циклов + 2 цифры в остатке.
Беру на один цикл меньше, т.е. по 10 цифр "1" и "2". Это строка 1211111111112222222222. Повторяю программу. Получается 112212.

 Отправлено: 08.03.19 20:05. Заголовок: Ответ

Здравствуйте!

При решении таких задач нужно прежде всего определить какого вида строка повторяется.

В этой задаче будет повторяться не строка вида 1...12...2, а строка, которая получится после выполнения одного цикла, то есть строка вида 21...12...2.

Первоначально в этой строке будет в начале её одна 2, затем 2017 единиц, а после них 2016 двоек.

Добьемся того, чтобы этот вид строки вновь повторился. Количество "1" уменьшится на 6 и количество "2" после всех единиц уменьшится также на 6 (в начале строки будет еще одна "2").

2017 mod 6 = 1, а 2016 mod 6 = 0. Так как 2016 mod 6 = 0, то нужно "вернуться на один шаг", то есть рассмотреть строку 21111111222222, где после "2" идет 1+6 единиц, а после них 6 "2".

Применяя программу к строке 21111111222222, получим ответ 21.

Ответ: 21.

 Отправлено: 08.03.19 20:31. Заголовок: Спасибо за ответ! Но..

Спасибо за ответ! Но мне не все понятно.
"Первоначально в этой строке будет в начале её одна 2, затем 2017 единиц, а после них 2016 двоек." - это понятно.
Потом 221...12...2, где единиц будет 2015, а двоек 2013.
В следующем цикле 2221...12...2, где единиц 2013, а двоек 2010.
Но потом читаем строку сначала и заменяем первые три двойки на единицу и последующие три единицы на двойку. Получаем 121...12...2 единиц и двоек по 2010 штук.
Как "Добьемся того, чтобы вид строки 21...12...2 вновь повторился." у вас эта строка получилась?

 Отправлено: 29.11.19 22:34. Заголовок: ­polyakovss пишет: П..

*PRIVAT*

 Отправлено: 08.03.19 21:44. Заголовок: Ответ

Можно сообразить, что поскольку должна получиться строка 21111111222222, в которой после одной "2" идут 7 "1", а затем 6 "2", то такой же ответ 21 будет для исходной строки вида (7+6k+2) "1" и (6+6k+3) "2",
где k = 1, 2, 3, ....

Минимальное количество "1" и "2" - 15. Но возьмем 21, чтобы было более понятно.

1) 111111111111111111111222222222222222222222
2) 21111111111111111111222222222222222222 ("2"+ (21-2) "1" + (21-3) "2")

3) 21111111111111111111222222222222222222
222111111111111111222222222222 ("222"+15 "1" + 12 "2").
Теперь первые 222 заменяются на 1, а первые 111 (с учетом только что полученной "1") заменяются на 2. То есть 22211 заменяется на 2.
Получится
21111111111111222222222222 ("2" + 13 "1" + 12 "2"). По сравнению со строкой в пункте 2 количество "1" уменьшилось на 6, количество "2" после них также уменьшилось на 6.

4) 21111111111111222222222222
222111111111222222 ("222" + 9 "1" + 6 "2").
Теперь первые 222 заменяются на 1, а первые 111 (с учетом только что полученной "1") заменяются на 2. То есть 22211 заменяется на 2.
Получится
21111111222222 ("2" + 7 "1" + 6 "2"). По сравнению со строкой в пункте 3 количество "1" снова уменьшилось на 6, количество "2" после них также снова уменьшилось на 6.

5) Применяя программу к этой строке, получим ответ 21.

Обратите внимание, что под циклом здесь нужно понимать не цикл программы, а цикл приведения строки к прежнему виду 21...12...2.
В этом разборе мы прошли такой цикл дважды - в пункте 3 и в пункте 4.

Вы пишете:

цитата:

Но потом читаем строку сначала и заменяем первые три двойки на единицу и последующие три единицы на двойку.

Это ошибка.
Правильно так: читаем строку сначала и заменяем первые три двойки на единицу, а эту единицу и последующие две единицы заменяем на двойку, то есть 22211 заменяем на 2.

 Отправлено: 09.03.19 09:44. Заголовок: Доброе утро! Спасибо..

Доброе утро!
Спасибо за ответ!
"Теперь первые 222 заменяются на 1, а первые 111 (с учетом только что полученной "1") заменяются на 2. " - разве машина, прочитав первые три двойки, заменив их на 1 возвращается к началу строки? В моем понимании, в цикле должно быть последовательное прочтение: заменив три двойки на единицу, следующие три единицы машина меняет на двойку. Значит здесь я не права? Получается, что после каждой замены мы должны учитывать цифру, которую получили? И эта цифра будет считаться первой в прочтении?

 Отправлено: 09.03.19 11:02. Заголовок: Ответ

Здравствуйте!

В условии задачи сказано:

цитата:

Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов. заменить (v, w) нашлось (v) Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w.

Поэтому каждая команда "заменить" заменяет в строке первое слева вхождение цепочки v на цепочку w.

 Отправлено: 09.03.19 11:12. Заголовок: Спасибо! Теперь у ме..

Спасибо!
Теперь у меня пошло. 201 номер получился:)

 Отправлено: 04.08.19 14:29. Заголовок: Здравствуйте. Подска..

Здравствуйте. Подскажите, пожалуйста. Почему из строки 2 1111111 222222 мы получаем 21? В условии задачи сначала стоит команда заменить(222,1) и только потом заменить(111,2).
21111111222222---2211111222---222111---12.
Да, если сначала применить команду заменить(111,2), то получаем 21. Почему не влияет порядок команд в условии? Я никак не пойму.

 Отправлено: 04.08.19 15:11. Заголовок: Ответ

Здравствуйте!

Вы пишете:

цитата:

21111111222222---2211111222---222111---12.

Вы пишете:

цитата:

В условии задачи сначала стоит команда заменить(222,1) и только потом заменить(111,2).

Верно.


Поэтому

222111 --- 1111
1111 --- 21


Замечание

При входе в цикл для строки 222111 условие "ПОКА нашлось (222)" выполняется.

Поэтому последовательно в указанном у условии порядке выполняются ОБЕ команды

заменить (222, 1)
заменить (111, 2)

уже без проверки нашлось ли (222).

 Отправлено: 04.08.19 15:13. Заголовок: Потому что 111 111 1..

Потому что
111 111 111 111 222 222 222 222 -> 2 111 111 111 1 222 222 222 -> 2 2 111 111 1 1 222 222 -> 2 2 2 111 1 1 222 222 -> 1 111 1 1 222 222 (стало на шесть единиц и двоек меньше!)
336 раз вычитаем по шесть единиц и двоек, получим 111 222 ->21

 Отправлено: 04.08.19 15:53. Заголовок: Спасибо большое. С в..

Спасибо большое. С вами все понятно)

 Отправлено: 04.08.19 16:43. Заголовок: Вопрос для cabanov.alexey

Здравствуйте, Алексей Михайлович!

Вы пишете:

цитата:

111 111 111 111 222 222 222 222 -> 2 111 111 111 1 222 222 222 -> 2 2 111 111 1 1 222 222 -> 2 2 2 111 1 1 222 222 -> 1 111 1 1 222 222 (стало на три единицы и двойки меньше!)

Для примера Вы рассмотрели строку 111 111 111 111 222 222 222 222.

1) Для этой строки в результате работы алгоритма будет получено 2211, а не 21.

2) Любое одинаковое количество "1" и "2" для примера в этой задаче брать нельзя.
Посмотрите здесь (polyakovss Сообщение: 135)

2) В этой задаче нет повторения строки, в которой сначала все "1", а затем все "2".
Посмотрите здесь (polyakovss Сообщение: 134)

3) Вы пишете:

цитата:

2 2 111 111 1 1 222 222 -> 2 2 2 111 1 1 222 222 -> 1 111 1 1 222 222 (стало на три единицы и двойки меньше!)

Нет. Цикл не закончился. В нем выполняется еще команда "заменить (111, 2)".
Поэтому
22 111 111 11 222 222 -> 222 111 111 222 -> 21111222

4) Вы пишете:

цитата:

111 111 111 111 222 222 222 222 -> 2 111 111 111 1 222 222 222 -> 2 2 111 111 1 1 222 222 -> 2 2 2 111 1 1 222 222 -> 1 111 1 1 222 222 (стало на три единицы и двойки меньше!)

Почему "стало на три единицы и двойки меньше!", если в Вашем варианте рассуждений их сначала было по 12, а осталось по 6?

 Отправлено: 04.08.19 20:11. Заголовок: 1) Пример нужен чтоб..

Пример нужен чтобы понять, сколько единиц и двоек будет убираться из строки.
Распишу. Берём строку из 12 единиц и двоек (число произвольно).
1 итерация: 111 111 111 111 222 222 222 222 -> 2 111 111 111 1 222 222 222
2 итерация: 2 111 111 111 1 222 222 222 -> 2 2 111 111 1 1 222 222
3 итерация: 2 2 111 111 1 1 222 222 -> 2 2 2 111 1 1 222 222 -> 1 111 1 1 222 222
Получили строку, подобную начальной! Но на 6 единиц и двоек меньше.
Перенесёмся в оригинальный пример. По аналогии после 3 итераций будут пропадать по 6 единиц и двоек. Это будет продолжаться 2019:3=336.5 раз. Половинки не считаем, значит 336 раз, за которые пропадут 2016 цифр в каждой группе. В конце получим 111 222 -> 21.

 Отправлено: 04.08.19 21:24. Заголовок: Ответ

Вы пишете:

цитата:

1 итерация: 111 111 111 111 222 222 222 222 -> 2 111 111 111 1 222 222 222 2 итерация: 2 111 111 111 1 222 222 222 -> 2 2 111 111 1 1 222 222 3 итерация: 2 2 111 111 1 1 222 222 -> 2 2 2 111 1 1 222 222 -> 1 111 1 1 222 222

Так будет, если в цикле сначала выполняется команда "заменить (111, 2)", а затем команда "заменить (222, 1)".

Но по условию:

цитата:

НАЧАЛО ПОКА нашлось (222) заменить (222, 1) заменить (111, 2) КОНЕЦ ПОКА КОНЕЦ

Поэтому
3 итерация:

2 2 111 111 1 1 222 222 -> 2 2 111 111 111 222 -> 222 111 111 222

4 итерация:

222 111 111 222 -> 111 111 1 222 -> 2 111 1 222

Строка, подобная начальной, не повторяется!

Повторяется строка вида 2 1...1 2...2.

Замечание

Если в цикле сначала выполняется команда "заменить (111, 2)", а затем команда "заменить (222, 1)",
то в результате работы алгоритма получится 12, а вовсе не 21,
хотя первые 3 итерации будут именно такими, как Вы указали, и количество "1" и "2" уменьшается на 6.

 Отправлено: 23.01.21 19:59. Заголовок: гораздо более просто..

гораздо более простое и лаконичное решение на питоне с выводом всех проходов алгоритма для подобной задачи

 l=(2018*'1' + 2019*'2') 
 k=0 
 while l.find('111') != -1: 
 	l=l.replace('111','2',1) 
 	l=l.replace('222','1',1) 
 	k+=1 
 	print('Prohod #',k, ':  ',l, '\n') 
 print('OTVET: ',l)

 Отправлено: 23.01.21 23:48. Заголовок: Обратите внимание

StupNum пишет:

цитата:

гораздо более простое и лаконичное решение на питоне с выводом всех проходов алгоритма для подобной задачи

Сообщения, к которым относится это утверждение, датированы мартом и августом 2019 года.
В это время использовать на экзамене системы программирования не разрешалось.

 Отправлено: 06.02.21 21:17. Заголовок: Задание 211

Добрый вечер. вопрос по заданию 211. Ответ 123, у меня получается 213. Не могу понять в чем моя ошибка.
НАЧАЛО
ПОКА нашлось (11)
заменить (11, 2)
заменить (22, 3)
заменить (33, 1)
КОНЕЦ ПОКА
КОНЕЦ
Какая строка получится в результате применения приведённой программы к строке вида 1…12…23….3 (13 единиц, 13 двоек и 13 троек)?
1111..2222..3333
Получила
1111111 222222222 11 333333333
далее
122222 1111 33333
Проверяла на Редакторе Visual_C#. До этого момента все совпадает, а далее нет.
Мое решение
13222 11111 333 1332 111111 3 11 2 11111 333 3 1111113 3211113 322113 33113 1113 213

 Отправлено: 07.02.21 16:04. Заголовок: s = 13*'1' ..

 s = 13*'1' + 13*'2' + 13*'3' 
  
 while '11' in s: 
   print('*') 
   s = s.replace( '11', '2', 1 ) 
   print(s) 
   s = s.replace( '22', '3', 1 ) 
   print(s) 
   s = s.replace( '33', '1', 1 ) 
   print(s)