12-е задание: «Алгоритмы с циклами и условиями» Уровень сложности — повышенный, Требуется использование специализированного программного обеспечения — нет, Максимальный балл — 1, Примерное время выполнения — 4 минуты.
Проверяемые элементы содержания: Умение анализировать результат исполнения алгоритма
До ЕГЭ 2021 года — это было задание № 14 ЕГЭ
Рекомендации по выполнению:
"Для выполнения задания на анализ алгоритма нужно найти закономерность, связывающую
исходные данные и результат работы алгоритма, для чего нужно выполнить несколько шагов алгоритма и проанализировать результат"
Типичные ошибки и рекомендации по их предотвращению:
"Не рекомендуется решение задачи «в лоб», т.е. выполнение алгоритма целиком для заданных в условии данных, поскольку это весьма трудоёмкий процесс, к тому же с высокой вероятностью ошибки по невнимательности"
ФГБНУ "Федеральный институт педагогических измерений"
* Некоторые изображения и примеры страницы взяты из материалов презентации К. Полякова
Алгоритм ветвление
Блок-схема разветвляющегося алгоритма выглядит следующим образом:
Полная форма ветвления
Что в словесной форме будет звучать так:
ввод a и b;
если a больше b, то переменной max присваиваем значение a, иначе переменной max присваиваем значение b;
вывод max.
Реализуем это в Паскале:
Ветвление в Паскале
Ветвление бывает неполное, в таком случае отсутствует блок «иначе»:
Неполная форма ветвления
На Паскале:
Неполная форма условного оператора
О сложных условиях в Паскале можно прочитать здесь.
📹 Учимся по видео (решения разного типа программным способом):
Какая строка получится?
12_4: ЕГЭ по информатике 2017 задание 12 ФИПИ вариант 3 (Крылов С.С., Чуркина Т.Е.):
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w)
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w.
Б) нашлось (v)
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка при этом не изменяется.
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 40 идущих подряд цифр 123? В ответе запишите полученную строку.
НАЧАЛО
ПОКА нашлось (12) ИЛИ нашлось (333)
ЕСЛИ нашлось (12)
ТО заменить (12, 3)
ИНАЧЕ заменить (333, 3)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
✍ Решение:
✎ Решение 1. Теоретическое:
Рассмотрим алгоритм: редактор будет выполнять команды только тогда, когда в строке встречается цепочка «12» или цепочка «333»;
если в строке есть «12», то тогда эта цепочка заменяется на «3»;
если в строке нет цепочки «12», но есть «333», то цепочка «333» заменяется на «3».
Теперь вернемся к условию нашей задачи. Условие цикла истинно, соответственно выполняем блок ЕСЛИ, т.е. делаем замену: в каждом из 40 чисел ‘123‘, заменяем 12 на 3. Получим 40 + 40 = 80 троек (40 троек было изначально и 40 добавилось);
123123123...123
↓ ↓ ↓ ↓
3 33 33 3...3 3
Так как больше чисел 12 у нас не встречается, то работает блок ИНАЧЕ. Сколько раз можно заменить в 80 подряд идущих тройках три тройки на одну? 80 делим на 3 получаем 26 раз + 2 тройки в остатке. Итого осталось 28 троек;
333 333 333 333... 333 3326 троек по три
получили:
3 3 3 3 ... 3 3326+ 2
Теперь из 28 троек сколько раз мы можем заменить три тройки на одну? 28 делим на 3 и получаем 9 раз + 1 тройка в остатке. Итого 10 троек;
Делаем то же самое: 10 делим на 3 получаем 3 раза + 1 тройка в остатке = 4 тройки
333 333 333 33 тройки по три+ 1
получили:
3 3 3 3
Последний раз делим 4 на 3, получаем 1 тройку + 1 = 2 тройки
3 3 3 3
↓
3 3
Результат: 33
✎ Решение 2. Программное: Pascalabc.net:
1
2
3
4
5
6
7
8
9
10
11
beginvar s :='123'*40;while('12'in s)or('333'in s)dobeginif'12'in s then
s := s.Replace('12','3',1)else
s := s.Replace('333','3',1);end;
print(s);end.
begin
var s := '123' * 40;
while ('12' in s) or ('333' in s) do
begin
if '12' in s then
s := s.Replace('12', '3', 1)
else
s := s.Replace('333', '3', 1);
end;
print(s);
end.
begin
var s := '123'*40;
var p1 := Pos('12',s);
var p2 := Pos('333',s);
while (p1 > 0) or (p2 > 0) do begin
if p1 > 0 then begin
Delete( s, p1, 2 );
Insert( '3', s, p1 );
end
else begin
Delete( s, p2, 3 );
Insert( '3', s, p2 );
end;
p1 := Pos('12',s);
p2 := Pos('333',s);
end;
write(s);
end.
Python:
s =40*'123'while"12"in s or"333"in s:
if"12"in s:
s = s.replace("12","3",1)else:
s = s.replace("333","3",1)print(s)
s = 40*'123'
while "12" in s or "333" in s:
if "12" in s:
s = s.replace( "12", "3", 1 )
else:
s = s.replace( "333", "3", 1 )
print(s)
#include<iostream>
using namespace std;
int main()
{
string s(40, '123');
cout << s << endl;
int p1 = s.find("12");
int p2 = s.find("333");
while( p1 != string::npos or p2 != string::npos ) {
if( p1 != string::npos )
s.replace( p1, 12, "3" );
else
s.replace( p2, 333, "3" );
p1 = s.find("12");
p2 = s.find("333");
cout << s << endl;
}
cout << s;
}
Результат: 33
Пошаговое решение данного 12 задания ЕГЭ по информатике также доступно в видеоуроке:
12_5: ЕГЭ по информатике 2017 задание 12 ФИПИ вариант 5 (Крылов С.С., Чуркина Т.Е.):
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w)
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w.
Б) нашлось (v)
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка при этом не изменяется.
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 71 идущих подряд четверок цифр 1122? В ответе запишите полученную строку.
НАЧАЛО
ПОКА нашлось (12) ИЛИ нашлось (222)
ЕСЛИ нашлось (12)
ТО заменить (12, 2)
ИНАЧЕ заменить (222, 2)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
✍ Решение:
✎ Решение 1. Теоретическое:
Для удобства решения сначала сократим исходную цепочку до одной группы цифр:
1122
Условие цикла истинно (ПОКА нашлось (12)), и условие в цикле истинно (ЕСЛИ нашлось (12)), значит, делаем замену: в первой группе цифр «1122«, заменяем 12 на 2:
1122 => 122
Затем опять возвращаемся к условию цикла: условие цикла истинно (ПОКА нашлось (12)), и условие в цикле истинно (ЕСЛИ нашлось (12)), делаем опять замену: в первой группе цифр «122«, заменяем 12 на 2:
122 => 22
Таким образом, получаем, что за две итерации цикла (2 шага), одна группа цифр превращается в две двойки.
Поскольку по условию имеем 71 группу цифр, то, чтобы узнать сколько двоек мы получим в результате выполнения условия ЕСЛИ нашлось (12), нам необходимо 71 умножить на 2 (кол-во двоек, получаемых из одной группы цифр):
71 * 2 = 142 двойки из 71 группы
То есть в итоге работы цикла и условия ЕСЛИ нашлось (12) мы получили всего 142 двоек.
Теперь работает условие ИНАЧЕ заменить (222, 2). Из 142 двоек каждые три заменяем на одну. Чтобы рассчитать итоговое количество двоек, необходимо 142 разделить на 3 (т.е. сколько раз можно заменять тройки двоек на одну двойку). Делить необходимо до тех пор, пока работает условие ИНАЧЕ заменить (222, 2):
beginvar s :='1122'*71;while('12'in s)or('222'in s)dobeginif'12'in s then
s := s.Replace('12','2',1)else
s := s.Replace('222','2',1);end;
print(s);end.
begin
var s := '1122' * 71;
while ('12' in s) or ('222' in s) do
begin
if '12' in s then
s := s.Replace('12', '2', 1)
else
s := s.Replace('222', '2', 1);
end;
print(s);
end.
begin
var s := '1122'*71;
var p1 := Pos('12',s);
var p2 := Pos('222',s);
while (p1 > 0) or (p2 > 0) do begin
if p1 > 0 then begin
Delete( s, p1, 2 );
Insert( '2', s, p1 );
end
else begin
Delete( s, p2, 3 );
Insert( '2', s, p2 );
end;
p1 := Pos('12',s);
p2 := Pos('222',s);
end;
write(s);
end.
Python:
s =71*'1122'while"12"in s or"222"in s:
if"12"in s:
s = s.replace("12","2",1)else:
s = s.replace("222","2",1)print(s)
s = 71*'1122'
while "12" in s or "222" in s:
if "12" in s:
s = s.replace( "12", "2", 1 )
else:
s = s.replace( "222", "2", 1 )
print(s)
#include<iostream>
using namespace std;
int main()
{
string s(71, '1122');
cout << s << endl;
int p1 = s.find("12");
int p2 = s.find("222");
while( p1 != string::npos or p2 != string::npos ) {
if( p1 != string::npos )
s.replace( p1, 12, "2" );
else
s.replace( p2, 222, "2" );
p1 = s.find("12");
p2 = s.find("222");
cout << s << endl;
}
cout << s;
}
Результат: 22
12_6: ЕГЭ по информатике 2017 задание 12 ФИПИ вариант 7 (Крылов С.С., Чуркина Т.Е.):
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w)
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w.
Б) нашлось (v)
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка при этом не изменяется.
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 200 идущих подряд цифр 7? В ответе запишите полученную строку.
НАЧАЛО
ПОКА нашлось (99) ИЛИ нашлось (777)
ЕСЛИ нашлось (777)
ТО заменить (777, 9)
ИНАЧЕ заменить (99, 7)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
✍ Решение:
Рассмотрим алгоритм: редактор будет выполнять команды только тогда, когда в строке встречается цепочка «99» или цепочка «777»;
если в строке есть «777», то тогда эта цепочка заменяется на «9»;
если в строке нет цепочки «777», но есть «99», то цепочка «99» заменяется на «7».
Теперь вернемся к условию нашей задачи. Условие цикла истинно, условие ЕСЛИ нашлось 777 тоже истинно, делаем замену:
сколько раз можно заменить в 200 семерках три семерки на одну девятку? 200 делим на 3 получаем 66 замен, т.е. 66 цифр «9» + 2 семерки в остатке;
777 777 ... 777 77
получили:
9...9 77
↓
66
После выполнения этих преобразований условие ЕСЛИ нашлось 777 ложно. Значит, выполняется блок ИНАЧЕ: Заменить 99 на 7:
Затем условие ЕСЛИ нашлось 777 опять становится истинным. Выполняется команда Заменить 777 на 9:
60 цифр777999...999 77
↓
9 999...999 77
61 цифра
Вернулись к той же «картине», что и после первого пункта. За эти шаги произошли преобразования, заменившие 66 девяток на 61 девятку, т.е. количество цифр «9» уменьшилось на 5 раз, а две цифры «77» так и остались в конце общей цепочки.
Чтобы рассчитать итоговое количество цифр «9», необходимо понять, сколько раз можно вычитать из 61 по 5 девяток:
61 : 5 = 12 раз
12 раз возможно отнять по 5 девяток и 1 девятка останется "в остатке"
Таким образом, после выполнения алгоритма, остается одна цифра «9» (в остатке) и в конце так и останутся две семерки: 977.
Результат: 977
Видео ЕГЭ по информатике 2017, подробное решение данного 12 задания:
12_7: Разбор 12 задания ЕГЭ по информатике 2019 г. «10 тренировочных вариантов для подготовки к ЕГЭ» Д.М. Ушаков:
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w)
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w.
Б) нашлось (v)
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка при этом не изменяется.
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 90 идущих подряд цифр 3 и в конце одной цифры 1? В ответе запишите полученную строку.
НАЧАЛО
ПОКА нашлось (331) ИЛИ нашлось (166)
ЕСЛИ нашлось (331)
ТО заменить (331, 16)
ИНАЧЕ заменить (166, 31)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
📹 Предлагаем посмотреть видео разбора (теоретическое):
✍ Решение:
✎ Решение 1. Программное: Pascalabc.net:
1
2
3
4
5
6
7
8
9
10
11
beginvar s :='3'*90+'1';while('331'in s)or('166'in s)dobeginif'331'in s then
s := s.Replace('331','16',1)else
s := s.Replace('166','31',1);end;
print(s);end.
begin
var s := '3' * 90 + '1';
while ('331' in s) or ('166' in s) do
begin
if '331' in s then
s := s.Replace('331', '16', 1)
else
s := s.Replace('166', '31', 1);
end;
print(s);
end.
begin
var s := '3'*90 + '1';
var p1 := Pos('331',s);
var p2 := Pos('166',s);
while (p1 > 0) or (p2 > 0) do begin
if p1 > 0 then begin
Delete( s, p1, 3 );
Insert( '16', s, p1 );
end
else begin
Delete( s, p2, 3 );
Insert( '31', s, p2 );
end;
p1 := Pos('331',s);
p2 := Pos('166',s);
end;
write(s);
end.
Python:
s =90*'3'+'1'while"331"in s or"166"in s:
if"331"in s:
s = s.replace("331","16",1)else:
s = s.replace("166","31",1)print(s)
s = 90*'3'+'1'
while "331" in s or "166" in s:
if "331" in s:
s = s.replace( "331", "16", 1 )
else:
s = s.replace( "166", "31", 1 )
print(s)
#include<iostream>
using namespace std;
int main()
{
string s(90, '3');
s+='1';
cout << s << endl;
int p1 = s.find("331");
int p2 = s.find("166");
while( p1 != string::npos or p2 != string::npos ) {
if( p1 != string::npos )
s.replace( p1, 331, "16" );
else
s.replace( p2, 166, "31" );
p1 = s.find("331");
p2 = s.find("166");
cout << s << endl;
}
cout << s;
}
Результат: 316
Сколько удалено?
12_8: Решение 12 задачи № 178 (с сайта К. Полякова):
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w)
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w.
Б) нашлось (v)
Дана программа для исполнителя Редактор:
ПОКА нашлось (555) ИЛИ нашлось (333)
ЕСЛИ нашлось (333)
ТО заменить (333, 5)
ИНАЧЕ заменить (555, 3)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
Дана строка, состоящая из 500 цифр 5. Сколько пятёрок было удалено за время обработки строки по этой программе?
📹 Смотрите разбор задания на видео (теоретическое):
✍ Решение:
✎ Решение 1. Теоретическое:
Выполним несколько итераций цикла ПОКА. Когда мы получим ту же самую последовательность цифр пять, за исключением их количества — остановимся:
5..5
500шт
1: Работает блок ИНАЧЕ (555->3):
35..5497шт
2: Работает блок ИНАЧЕ (555->3):
335..5494шт
3: Работает блок ИНАЧЕ(555->3):
3335..5491шт
4: Работает блок ЕСЛИ (333->5):
5..5492шт
Остановились, так как мы пришли к исходной последовательности цифр пять. Проанализируем действия программы за этот фрагмент выполнения: было удалено 9 пятерок и одна пятерка добавилась. Ключевой вывод: было удалено 9 пятерок.
Всего за выполнение этого фрагмента программы «ушло» 8 пятерок: 500 - 492 = 8. Посчитаем, сколько раз можно выполнить данный фрагмент:
500 : 8 = 62 и 4 в остатке
Т.е. 62 раза выполняется данный фрагмент и 4 цифр 5 еще остается (остаток = 4). Поскольку за одно выполнение фрагмента было удалено 9 цифр 5, посчитаем, сколько удалится за 62 выполнения:
62 * 9 = 558
558 цифр 5 было удалено. Посмотрим выполнение программы над оставшимися 4 цифрами 5:
Работает блок ИНАЧЕ(555->3):
5555 = 35
Итого получаем удаленных цифр 5:
558 + 3 = 561
Результат: 561
✎ Решение 2. Программное: Pascalabc.net:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
beginvar s :='5'*500;var k :=0;while('555'in s)or('333'in s)dobeginif'333'in s then
s := s.Replace('333','5',1)elsebegin
s := s.Replace('555','3',1);
k +=3;end;end;
print(k);end.
begin
var s := '5' * 500;
var k := 0;
while ('555' in s) or ('333' in s) do
begin
if '333' in s then
s := s.Replace('333', '5', 1)
else
begin
s := s.Replace('555', '3', 1);
k += 3;
end;
end;
print(k);
end.
begin
var k:= 0;
var s := '5'*500 ;
var p1 := Pos('555',s);
var p2 := Pos('333',s);
while (p1 > 0) or (p2 > 0) do begin
if p2 > 0 then begin
Delete( s, p2, 3 );
Insert( '5', s, p2 );
end
else begin
Delete( s, p1, 3 );
Insert( '3', s, p1 );
inc(k,3);
end;
p1 := Pos('555',s);
p2 := Pos('333',s);
end;
write(k);
end.
Python:
s =500*'5'
k=0while"555"in s or"333"in s:
if"333"in s:
s = s.replace("333","5",1)else:
s = s.replace("555","3",1)
k+=3;print(k)
s = 500*'5'
k=0
while "555" in s or "333" in s:
if "333" in s:
s = s.replace( "333", "5", 1 )
else:
s = s.replace( "555", "3", 1 )
k+=3;
print(k)
#include<iostream>
using namespace std;
int main()
{
string s(500, '5');
int k = 0;
cout << s << endl;
int p1 = s.find("555");
int p2 = s.find("333");
while( p1 != string::npos or p2 != string::npos ) {
if( p2 != string::npos )
s.replace( p2, 333, "5" );
else
{
s.replace( p1, 555, "3" );
k+=2;
}
p1 = s.find("555");
p2 = s.find("333");
cout << s << endl;
}
cout << k;
}
Чему равна сумма цифр?
12_13: Решение 12 задачи № 176 (с сайта К. Полякова):
Дана программа для исполнителя Редактор:
ПОКА нашлось (555) ИЛИ нашлось (333)
ЕСЛИ нашлось (555)
ТО заменить (555, 3)
ИНАЧЕ заменить (333, 5)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
Дана строка, состоящая из 200 цифр 5. Чему равна сумма цифр строки, полученной после обработки по этой программе?
✍ Решение:
✎ Решение 1. Программное: Pascalabc.net:
1
2
3
4
5
6
7
8
9
10
11
12
13
beginvar s :='5'*200;while('555'in s)or('333'in s)dobeginif'555'in s then
s := s.Replace('555','3',1)else
s := s.Replace('333','5',1)end;
println(s);var sum := s.CountOf('5')*5+ s.CountOf('3')*3;
print(sum)end.
begin
var s := '5' * 200;
while ('555' in s) or ('333' in s) do
begin
if '555' in s then
s := s.Replace('555', '3', 1)
else
s := s.Replace('333', '5', 1)
end;
println(s);
var sum := s.CountOf('5') * 5 + s.CountOf('3') * 3;
print(sum)
end.
На вход приведённой ниже программе поступает строка, начинающаяся с символа «>», а затем содержащая 10 цифр 1, 20 цифр 2 и 30 цифр 3, расположенных в произвольном порядке. Определите сумму числовых значений цифр строки, получившейся в результате выполнения программы.
Так, например, если результат работы программы представлял бы собой строку, состоящую из 50 цифр 4, то верным ответом было бы число 200.
НАЧАЛО
ПОКА нашлось (>1) ИЛИ нашлось (>2) ИЛИ нашлось (>3)
ЕСЛИ нашлось (>1)
ТО заменить (>1, 22>)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (>2)
ТО заменить (>2, 2>)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (>3)
ТО заменить (>3, 1>)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
beginvar s :='>'+'1'*10+'2'*20+'3'*30;var k :=0;while('>1'in s)or('>2'in s)or('>3'in s)dobeginif'>1'in s then
s := s.Replace('>1','22>',1);if'>2'in s then
s := s.Replace('>2','2>',1);if'>3'in s then
s := s.Replace('>3','1>',1);end;var sum := s.CountOf('1')+ s.CountOf('2')*2+ s.CountOf('3')*3;{или так:
for var i := 1 to s.Count do
if (s[i]='1') or (s[i]='2') or(s[i]='3') then
sum:=sum + StrToInt(s[i]);
}
print(sum)end.
begin
var s := '>' + '1' * 10 + '2' * 20 + '3' * 30;
var k := 0;
while ('>1' in s) or ('>2' in s) or ('>3' in s) do
begin
if '>1' in s then
s := s.Replace('>1', '22>', 1);
if '>2' in s then
s := s.Replace('>2', '2>', 1);
if '>3' in s then
s := s.Replace('>3', '1>', 1);
end;
var sum := s.CountOf('1') + s.CountOf('2') * 2 + s.CountOf('3') * 3;
{или так:
for var i := 1 to s.Count do
if (s[i]='1') or (s[i]='2') or(s[i]='3') then
sum:=sum + StrToInt(s[i]);
}
print(sum)
end.
begin
var s := '>' + '1' * 10 + '2' * 20 + '3' * 30;
var p1 := pos('>1', s);
var p2 := pos('>2', s);
var p3 := pos('>3', s);
while (p1 <> 0) or (p2 <> 0) or (p3 <> 0) do
begin
if p1 <> 0 then
begin
delete(s, p1, 2);
insert('22>', s, p1)
end;
if p2 <> 0 then
begin
delete(s, p2, 2);
insert('2>', s, p2)
end;
if p3 <> 0 then
begin
delete(s, p3, 2);
insert('1>', s, p3)
end;
p1 := pos('>1', s);
p2 := pos('>2', s);
p3 := pos('>3', s);
end;
println(s);
var sum : integer;
for var i := 1 to s.Count do
sum := s.CountOf('1') + s.CountOf('2') * 2 + s.CountOf('3') * 3;
{или так:
if (s[i]='1') or (s[i]='2') or(s[i]='3') then
sum:=sum + StrToInt(s[i]);
}
print(sum)
end.
Python:
1
С++:
1
Ответ: 110
Сколько цифр … в конечной строке?
12_10: 12 задание № 195 (с сайта К. Полякова):
Дана программа для исполнителя Редактор:
НАЧАЛО
ПОКА нашлось (12) ИЛИ нашлось (1)
ЕСЛИ нашлось (12)
ТО заменить (12, 2221)
ИНАЧЕ заменить (1,222222)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей одной единицы и 51 стоящих справа от неё цифр 2? В ответ, запишите, сколько цифр 2 будет в конечной строке.
✍ Решение:
✎ Решение 1. Программное: PascalABC.net:
1
2
3
4
5
6
7
8
9
10
11
beginvar s :='1'+'2'*51;while('12'in s)or('1'in s)dobeginif'12'in s then
s := s.Replace('12','2221',1)else
s := s.Replace('1','222222',1);end;
print(s.CountOf('2'))end.
begin
var s := '1' + '2' * 51;
while ('12' in s) or ('1' in s) do
begin
if '12' in s then
s := s.Replace('12', '2221', 1)
else
s := s.Replace('1', '222222', 1);
end;
print(s.CountOf('2'))
end.
begin
var s := '1' + '2' * 51;
var p1 := pos('12', s);
var p2 := pos('1', s);
while (p1 <> 0) or (p2 <> 0) do
begin
if p1 <> 0 then
begin
delete(s, p1, 2);
insert('2221', s, p1)
end
else
begin
delete(s, p2, 1);
insert('222222', s, p2)
end;
p1 := pos('12', s);
p2 := pos('1', s);
end;
print(s.CountOf('2'))
end.
Python:
1
С++:
1
Ответ: 159
Сколько цифр … в исходной строке?
12_14: 12 задание № 270 (с сайта К. Полякова):
Дана программа для Редактора:
ПОКА нашлось(01) ИЛИ нашлось(02) ИЛИ нашлось(03)
заменить(01, 30)
заменить(02, 3103)
заменить(03, 1201)
КОНЕЦ ПОКА
Известно, что исходная строка начиналась с нуля, а далее содержала только единицы, двойки и тройки. После выполнения данной программы получилась строка, содержащая 31 единицу, 24 двойки и 46 троек. Сколько троек было в исходной строке?
beginforvar n1 :=1to50doforvar n2 :=1to50doforvar n3 :=1to50dobegin// зададим исходную строкуvar s :='0'+ n1 *'1'+ n2 *'2'+ n3 *'3';// начинаем цикл перебора и заменыwhile('01'in s)or('02'in s)or('03'in s)dobegin
s := s.replace('01','30',1);
s := s.replace('02','3103',1);
s := s.replace('03','1201',1);end;// выведем результат, удовлетворяющий условию задачи (с - количество "3" в исходной строке)if(s.countOf('1')=31)and(s.countOf('2')=24)and(s.countOf('3')=46)thenbegin
print(n3);
exit;end;end;end.
begin
for var n1 := 1 to 50 do
for var n2 := 1 to 50 do
for var n3 := 1 to 50 do
begin
// зададим исходную строку
var s := '0' + n1 * '1' + n2 * '2' + n3 * '3';
// начинаем цикл перебора и замены
while ('01' in s) or ('02' in s) or ('03' in s) do
begin
s := s.replace('01', '30', 1);
s := s.replace('02', '3103', 1);
s := s.replace('03', '1201', 1);
end;
// выведем результат, удовлетворяющий условию задачи (с - количество "3" в исходной строке)
if (s.countOf('1') = 31) and (s.countOf('2') = 24) and (s.countOf('3') = 46) then
begin
print(n3);
exit;
end;
end;
end.
Python:
for n1 inrange(50):
for n2 inrange(50):
for n3 inrange(50):
# зададим исходную строку
s ='0' + n1*'1' + n2*'2' + n3*'3'# начинаем цикл перебора и заменыwhile('01'in s)or('02'in s)or('03'in s):
s = s.replace('01','30',1)
s = s.replace('02','3103',1)
s = s.replace('03','1201',1)# выведем результат, удовлетворяющий условию задачи (с - количество "3" в исходной строке)if s.count('1')==31and s.count('2')==24and s.count('3')==46:
print(n1)
exit()
for n1 in range(50):
for n2 in range(50):
for n3 in range(50):
# зададим исходную строку
s = '0' + n1*'1' + n2*'2' + n3*'3'
# начинаем цикл перебора и замены
while ('01' in s) or ('02' in s) or ('03' in s):
s = s.replace('01','30',1)
s = s.replace('02','3103',1)
s = s.replace('03','1201',1)
# выведем результат, удовлетворяющий условию задачи (с - количество "3" в исходной строке)
if s.count('1') == 31 and s.count('2') == 24 and s.count('3') == 46:
print(n1)
exit()
Pascal(2 способ, традиционный):
1
Ответ: 17
Укажите минимальную возможную длину входной строки
12_11: 12 задание № 280 (с сайта К. Полякова):
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.
заменить (v, w)
нашлось (v)
Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор.
Дана программа для Редактора:
ПОКА нашлось (555) ИЛИ нашлось (888)
заменить (555, 8)
заменить (888, 55)
КОНЕЦ ПОКА
Известно, что начальная строка состоит более чем из 300 цифр 5 и не содержит других символов. В ходе работы алгоритма получилась строка, содержащая одну цифру 5 и одну цифру 8. Укажите минимальную возможную длину входной строки.
✍ Решение:
✎ Решение 1. Программное: PascalABC.net:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
beginforvar i :=301to1000dobeginvar s :='5'* i;while('555'in s)or('888'in s)dobegin
s := s.Replace('555','8',1);
s := s.Replace('888','55',1);end;if(s.countOf('5')=1)and(s.countOf('8')=1)thenbegin
print(i);break;endend;end.
begin
for var i := 301 to 1000 do
begin
var s := '5' * i;
while ('555' in s) or ('888' in s) do
begin
s := s.Replace('555', '8', 1);
s := s.Replace('888', '55', 1);
end;
if (s.countOf('5') = 1) and (s.countOf('8') = 1) then
begin
print(i);
break;
end
end;
end.
begin
for var i := 301 to 1000 do
begin
var s := '5' * i;
var p1 := pos('555', s);
var p2 := pos('888', s);
while (p1 <> 0) or (p2 <> 0) do
begin
if p1 <> 0 then
begin
delete(s, p1, 3);
insert('8', s, p1);
end;
p2 := pos('888', s); // обязательно!
if p2 <> 0 then
begin
delete(s, p2, 3);
insert('55', s, p2);
end;
p1 := pos('555', s);
p2 := pos('888', s);
end;
if (s.countOf('5') = 1) and (s.countOf('8') = 1) then
begin
print(i);
break;
end
end;
end.
Python:
1
С++:
1
Ответ: 305
Какое наибольшее / наименьшее количество … могло быть в исходной строке?
12_12: 12 задание № 220 (с сайта К. Полякова):
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.
заменить (v, w)
нашлось (v)
Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор.
К исходной строке, содержащей не более 100 троек и не содержащей других символов, применили приведённую ниже программу:
НАЧАЛО
ПОКА нашлось (333)
заменить (333, 4)
заменить (4444, 3)
КОНЕЦ ПОКА
КОНЕЦ
В результате получилась строка 43. Какое наибольшее количество троек могло быть в исходной строке?
✍ Решение:
✎ Решение 1. Программное:
PascalABC.net (1 способ):
1
2
3
4
5
6
7
8
9
10
11
12
13
beginforvar i :=1to100dobeginvar s :='3'* i;while'333'in s dobegin
s := s.Replace('333','4',1);
s := s.Replace('4444','3',1);if(s ='43')then
print(i);end;end;end.
begin
for var i := 1 to 100 do
begin
var s := '3' * i;
while '333' in s do
begin
s := s.Replace('333', '4', 1);
s := s.Replace('4444', '3', 1);
if (s = '43') then
print(i);
end;
end;
end.
Вывод:
4 15 26 37 48 59 70 81 92
Python:
for i inrange(1,100):
s="3"*i
while"333"in s:
s=s.replace("333","4",1)
s=s.replace("4444","3",1)if s=="43":
print(i)
for i in range(1,100):
s="3"*i
while "333" in s:
s=s.replace("333","4",1)
s=s.replace("4444","3",1)
if s=="43":
print(i)
begin
for var i := 1 to 100 do
begin
var s:= '3' * i;
var p1 := pos('333', s);
var p2 := pos('4444', s);
while p1 <> 0 do
begin
if p1 <> 0 then
begin
delete(s, p1, 3);
insert('4', s, p1);
end;
p2 := pos('4444', s); // обязательно!
if p2 <> 0 then
begin
delete(s, p2, 4);
insert('3', s, p2);
end;
p1 := pos('333', s);
p2 := pos('4444', s);
if (s = '43') then
begin
print(i);
end
end;
end;
end.
Ответ: 92
Решение заданий прошлых лет (до 2021)
Исполнитель Робот
12_1: Решение 12 задания ЕГЭ по информатике (контрольный вариант № 2 экзаменационной работы 2018 года, С.С. Крылов, Д.М. Ушаков):
Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости, включает 4 команды-приказа и 4 команды проверки условия. Команды-приказы:
вверх вниз влево вправо
Другие четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:
сверху свободно
снизу свободно
слева свободно
справа свободно
Сколько клеток приведенного лабиринта соответствуют требованию, что, начав движение в ней и выполнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клетке (клетка F6)?
НАЧАЛО
ПОКА < снизу свободно ИЛИ справа свободно >
ЕСЛИ < справа свободно > ТО вправо КОНЕЦ ЕСЛИ
ПОКА < снизу свободно > вниз КОНЕЦ ПОКА
КОНЕЦ ПОКА
КОНЕЦ
✍ Решение:
Рассмотрим тело внешнего цикла и операторы, которые в нем находятся:
1. В цикле выполняется проверка ЕСЛИ справа свободно ТО вправо: что означает движение на один шаг вправо (если это возможно)
2. Затем располагается цикл с условием пока снизу свободно вниз: что означает движение до конца вниз (пока это возможно)
После чего внешний цикл повторяется.
Таким образом, отметим «тупиковые» клетки, т.е. те, которые не позволят двигаться роботу к цели:
Таких клеток получилось 15. Вычислим подходящие клетки (всего клеток 36):
36 - 15 = 21
Результат: 21
12_2: Решение 12 задания (К. Поляков, вариант № 52):
Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и выполнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клетке (клетка F6)?
НАЧАЛО
ПОКА < справа свободно ИЛИ снизу свободно >
ПОКА < снизу свободно >
вниз
КОНЕЦ ПОКА
ПОКА < справа свободно >
вправо
КОНЕЦ ПОКА
КОНЕЦ ПОКА
КОНЕЦ
Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться на (a, b), где a, b – целые числа. Эта команда перемещает Чертёжника из точки с координатами (x,y) в точку с координатами (x + a, y + b).
Например, если Чертёжник находится в точке с координатами (4, 2), то команда сместиться на (2, −3) переместит Чертёжника в точку (6, −1).
Цикл
ПОВТОРИ число РАЗ
последовательность команд
КОНЕЦ ПОВТОРИ
означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным).
Чертёжнику был дан для исполнения следующий алгоритм (число повторений и величины смещения в первой из повторяемых команд неизвестны):
НАЧАЛО
сместиться на (4, 6)
ПОВТОРИ … РАЗ
сместиться на (…, …)
сместиться на (4, -6)
КОНЕЦ ПОВТОРИ
сместиться на (-28, -22)
КОНЕЦ
В результате выполнения этого алгоритма Чертёжник возвращается в исходную точку. Какое наибольшее число повторений могло быть указано в конструкции «ПОВТОРИ … РАЗ»?
Здравствуйте. Последняя задача (Решение 14 задания ЕГЭ по информатике (контрольный вариант № 2 экзаменационной работы 2018 года, С.С. Крылов, Д.М. Ушаков)
B1, C1, D1 — не тупиковые клетки! Либо рисунок не тот? Либо условие. Но не может быть такого.
Нет, они тупиковые, т.к. по алгоритму делается 1 шаг вправо и вниз на сколько возможно, а потом снова 1 шаг вправо и снова вниз на сколько возможно. В итоге из B1 и С1 вы утыкаетесь в ограничение в клетке D2, а из D1 в E5.
Татьяна
B1?B2?
admin
На какую задачу вопрос?
Николай
Здравствуйте. Последняя задача (Решение 14 задания ЕГЭ по информатике (контрольный вариант № 2 экзаменационной работы 2018 года, С.С. Крылов, Д.М. Ушаков)
B1, C1, D1 — не тупиковые клетки! Либо рисунок не тот? Либо условие. Но не может быть такого.
ReiS
Нет, они тупиковые, т.к. по алгоритму делается 1 шаг вправо и вниз на сколько возможно, а потом снова 1 шаг вправо и снова вниз на сколько возможно. В итоге из B1 и С1 вы утыкаетесь в ограничение в клетке D2, а из D1 в E5.
Mike
в последнем задании , видеообъяснение не к этому заданию
admin
Спасибо:)! исправлено
Алёна
Здравствуйте! К последнему заданию приложено видео по совершенно другому номеру.
admin
Спасибо:)! исправлено