12 (повышенный уровень, время – 6 мин)

Тема: Выполнение алгоритмов для исполнителя.Что проверяется:Умение анализировать результат исполнения алгоритма.1.6.2. Вычислимость. Эквивалентность алгоритмических моделей (?).1.1.3. Умение строить информационные модели объектов, систем и процессов в виде алгоритмов (?).Что нужно знать:

• 
  правила выполнения линейных, разветвляющихся и циклических алгоритмов
  
• 
  основные операции с символьными строками (определение длины, выделение подстроки, удаление и вставка символов, «сцепка» двух строк в одну)
  
• 
  исполнитель – это человек, группа людей, животное, машина или другой объект, который может понимать и выполнять некоторые команды
  
• 
  в школьном алгоритмическом языке нц обозначает «начало цикла», а кц – «конец цикла»; все команды между нц и кц – это тело цикла, они выполняются несколько раз
  
• 
  запись нц для i от 1 до n обозначает начало цикла, в котором переменная i (она называется переменной цикла) принимает последовательно все значения от 1 до n с шагом 1
  

Пример задания:

Р-14. (Н. Титов) Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.заменить (v, w)Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку.нашлось (v)Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка при этом не изменяется.Дана программа для исполнителя Редактор:НАЧАЛОПОКА НЕ нашлось(00)заменить(01, 220)заменить(02, 3201)заменить(03, 2012)КОНЕЦ ПОКАКОНЕЦ Известно, что исходная строка начиналась с нуля и заканчивалась нулём, а между ними были только цифры 1, 2 и 3. После выполнения данной программы получилась строка, содержащая 0 единиц, 186 двоек и 26 троек. Выведите минимальную длину исходной строки.

---

Решение (Н. Титов):

1. 
   Во-первых, необходимо разобраться сколько цифр ‘1’, ‘2’ и ‘3’ дают строки ‘010’, ‘020’, ’030’. Реализовав предложенный алгоритм на любом из языков программирования, мы получим:
   

– строка ‘010’, а соответственно и цифра ‘1’, дает ноль цифр ‘1’, две цифры ‘2’ и ноль цифр ‘3’;– строка ‘020’, а соответственно и цифра ‘2’, дает ноль цифр ‘1’ три цифры ‘2’ и одну цифру ‘3’;– строка ‘030’, а соответственно и цифра ‘3’, дает ноль цифр’1’ шесть цифр ‘2’ и одну цифру ‘3’.

2. 
   Пример реализации алгоритма на языке Python:
   

while not '00' in s:s = s.replace('01', '220', 1)s = s.replace('02', '3201', 1)s = s.replace('03', '2012', 1)

3. 
   Записав полученный результат в виде системы уравнений, мы получим следующее:
   

, гдеПервое уравнение говорит о количестве цифр ‘1’ в результирующей строке, второе – о количестве цифр ‘2’ в результирующей строке, а третье – о количестве цифр ‘3’ в результирующей строке.

4. 
   Решение данной задачи сводится к решению системы трёх уравнений с тремя неизвестными. Его можно решать теоретически (например, методом исключения переменных) или с помощью программы на языке Python:
   

a = []for i in range(0,50):for j in range(0,50):for k in range(0,50):if (0*i + 0*j + 0*k == 0 and2*i + 3*j + 6*k == 186 and0*i + 1*j + 1*k == 26):a.append(i+j+k)print( min(a) )Для данного уравнения существует множество решений, из них мы выбираем решение с минимальным количеством цифр.

5. 
   В результате выполнения программы мы получим количество цифр ‘1’, ‘2’ и ‘3’ между двумя цифрами ‘0’. К этому нужно добавить 2, так как по краям строки были два нуля.
   
6. 
   Ответ: 43.
   

---

Ещё пример задания:

Р-13. Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.заменить (v, w)Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку.нашлось (v)Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка при этом не изменяется.Дана программа для исполнителя Редактор:НАЧАЛОПОКА нашлось (2222) ИЛИ нашлось (8888)ЕСЛИ нашлось (2222)ТО заменить (2222, 88)ИНАЧЕ заменить (8888, 22)КОНЕЦ ЕСЛИКОНЕЦ ПОКАКОНЕЦ Какая строка получится в результате применения приведённой программы к строке, состоящей из 70 идущих подряд цифр 8? В ответе запишите полученную строку.Решение (теоретическое):

1. 
   чтобы понять принцип работы алгоритма, сначала рассмотрим строку из 10 цифр 8:
   

8888888888

2. 
   поскольку цепочки 2222 пока нет, сначала заменяем 8888 на 22:
   

22888888

3. 
   цепочки 2222 снова нет, поэтому опять заменяем 8888 на 22:
   

222288

4. 
   теперь появилась цепочка 2222, которая согласно алгоритму заменяется на 88:
   

8888

5. 
   таким образом, в результате трёх замен цепочка восьмёрок укоротилась на 6 цифр
   
6. 
   посчитаем, сколько раз так можно сделать: 70 : 6 = 11,(6) – округляем вниз до 11
   
7. 
   после 11 таких укорачиваний удалено 66 цифр 8, осталось всего 4, которые заменяются на 22
   
8. 
   Ответ: 22.
   

Решение (программа):

1. 
   поскольку при сдаче ЕГЭ в компьютерной форме доступны среды программирования, проще всего написать программу, которая моделирует исполнителя Редактор; для этой цели лучше всего подходит язык Python, обладающий широким набором встроенных функций для обработки символьных строк
   
2. 
   в начале программы записываем в строковую переменную s 70 цифр 8:
   

s = '8'*70

3. 
   операция нашлось(2222) заменяется на
   

"2222" in s

---

а заменить(2222, 88) – на s = s.replace( "2222", "88", 1 ) здесь третий аргумент (равный 1)– это количество замен, которые нужно выполнить

4. 
   приведём полную программу
   

s = 70*'8'while "2222" in s or "8888" in s:if "2222" in s:s = s.replace( "2222", "88", 1 )else:s = s.replace( "8888", "22", 1 )print(s)

5. 
   аналогичная программа на языке PascalABC.NET:
   

beginvar s := StringOfChar('8', 70);var p2 := Pos('2222',s);var p8 := Pos('8888',s);while (p2 > 0) or (p8 > 0) do beginif p2 > 0 then beginDelete( s, p2, 4 );Insert( '88', s, p2 );endelse beginDelete( s, p8, 4 );Insert( '22', s, p8 );end;p2 := Pos('2222',s);p8 := Pos('8888',s);end; write(s);end.

6. 
   программа на языке PascalABC.NET с использованием новых функций (М. Коротков):
   

beginvar s: string := '8' * 70;while (s.contains('2222')) or (s.contains('8888')) dobeginif (s.contains('2222')) thens := s.replace('2222', '88', 1)elses := s.replace('8888', '22', 1);end;writeln(s);end.

7. 
   аналогичная программа на языке С++:
   

#includeusing namespace std;int main(){string s(70, '8'); cout << s << endl;int p2 = s.find("2222");int p8 = s.find("8888");while( p2 != string::npos or p8 != string::npos ) {if( p2 != string::npos ) s.replace( p2, 4, "88" ); else s.replace( p8, 4, "22" ); p2 = s.find("2222");p8 = s.find("8888");cout << s << endl;}cout << s;}

8. 
   (П. Финкель) Решение не школьном алгоритмическом языке (Кумир):
   

использовать Строкиалгначлит сссс:=""нц 70 разсс := сс + "8" |формируем строку из 70 "8"кцнц пока поз("2222",сс)<>0 или поз("8888",сс)<>0если поз("2222",сс)<>0 то заменить(сс,"2222","88",нет)иначе заменить(сс,"8888","22",нет)всекцвывод сскон

9. 
   Ответ: 22.
   

Решение (электронные таблицы, Б.С. Михлин):

1. 
   эту задачу несложно решить с помощью электронных таблиц; в ячейку C1 записываем исходную строку, применяя функцию ПОВТОР (в OpenOffice Calc:=REPT("8";70))
   

2. 
   затем нужно определить, есть ли в этой строке сочетания символов «2222» и «8888»; для этого можно использовать функцию НАЙТИ (FIND)
   
3. 
   эта функция выдаёт ошибку, если образец не найден; эту ошибку мы можем перехватить, используя функцию ЕСЛИОШИБКА (только в Excel 2007+и LibreOfficeCalc); в случае ошибки выведем 0, а при обнаружении образца – его позицию (результат работы функции НАЙТИ); записывается это так (в ячейке A1): =ЕСЛИОШИБКА(НАЙТИ("2222";C1);0) ; аналогично в B1 записываем формулу для поиска строки 8888: =ЕСЛИОШИБКА(НАЙТИ("8888";C1);0)
   

---

4. 
   к сожалению, в OpenOfficeCalcнет встроенной функции ЕСЛИОШИБКА (IFERROR), и эти формулы приходится реализовывать через функции IF и ISERROR:
   

А1: =IF(ISERROR(FIND("2222";C1));0;FIND("2222";C1))В1: =IF(ISERROR(FIND("8888";C1));0;FIND("8888";C1))

5. 
   теперь в ячейке C2 строим изменённую строку: если в A2 не ноль, меняем 2222 на 88, иначе меняем 8888 на 22:
   

=ЕСЛИ(A2;ЗАМЕНИТЬ(C1;A2;4;"88");ЗАМЕНИТЬ(C1;B2;4;"22"))OpenOffice Calc:=IF(A2;REPLACE(C1;A2;4;"88");REPLACE(C1;B2;4;"22"))

6. 
   аргументы при вызове функции ЗАМЕНИТЬ (REPLACE):
   

1: исходная строка2: начальная позиция заменяемой подстроки3: длина заменяемой подстроки4: подстрока-замена

7. 
   формулы в диапазоне A2:C2 протягиваем вниз до появления сообщения об ошибке (оно означает, что не найден ни один образец, ни 2222, ни 8888; последняя строка перед ошибкой – это и есть ответ:
   

8. 
   Ответ: 22.
   
9. 
   Замечание: вместо вызовов функции ЗАМЕНИТЬ (REPLACE) можно использовать функцию ПОДСТАВИТЬ (SUBSTITUTE):
   

ПОДСТАВИТЬ(С1; "2222";"88";1) и ПОДСТАВИТЬ(С1;"8888";"22";1)здесь четвертый аргумент (1) говорит о том, что нужно выполнить замену только 1 раз (для первого левого вхождения); кавычки в текстовых константах можно не ставить

10. 
    после получения строки с ответом (22) в следующих строках ответ просто повторяется (уже нет сообщения об ошибке, как при использовании функции ЗАМЕНИТЬ);
    
11. 
    в электронных таблицах (как и в языках программирования) числовое значение ноль в логических выражениях (ЕСЛИ и т.д.) рассматривается как ЛОЖЬ (FALSE), а другие числовые значения (не равные нулю) – как ИСТИНА (TRUE).
    

---

Смотрите также файлы

• Лекция 4 Кафедра фтизиатрии кгма им. И. К. Ахунбаева План лекции 1.pdf

• Конспект ору с набивным мячом (тема) фио студента.docx

• Фи дата i вариант Соедини части слова с их обозначением.docx

• Методы изучения.pdf

• Создание содержания книги.docx