Его. Выполнение алгоритмов для исполнителя
Скачать 1.75 Mb.
|
© К. Поляков, 2009-2021 12 (повышенный уровень, время – 6 мин)Тема: Выполнение алгоритмов для исполнителя. Что проверяется: Умение анализировать результат исполнения алгоритма. 1.6.2. Вычислимость. Эквивалентность алгоритмических моделей (?). 1.1.3. Умение строить информационные модели объектов, систем и процессов в виде алгоритмов (?). Что нужно знать: правила выполнения линейных, разветвляющихся и циклических алгоритмов основные операции с символьными строками (определение длины, выделение подстроки, удаление и вставка символов, «сцепка» двух строк в одну) исполнитель – это человек, группа людей, животное, машина или другой объект, который может понимать и выполнять некоторые команды в школьном алгоритмическом языке нц обозначает «начало цикла», а кц – «конец цикла»; все команды между нц и кц – это тело цикла, они выполняются несколько раз запись нц для i от 1 до n обозначает начало цикла, в котором переменная i (она называется переменной цикла) принимает последовательно все значения от 1 до n с шагом 1 Пример задания:Р-13. Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр. заменить (v, w) Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. нашлось (v) Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка при этом не изменяется. Дана программа для исполнителя Редактор: НАЧАЛО ПОКА нашлось (2222) ИЛИ нашлось (8888) ЕСЛИ нашлось (2222) ТО заменить (2222, 88) ИНАЧЕ заменить (8888, 22) КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ Какая строка получится в результате применения приведённой программы к строке, состоящей из 70 идущих подряд цифр 8? В ответе запишите полученную строку. Решение (теоретическое): чтобы понять принцип работы алгоритма, сначала рассмотрим строку из 10 цифр 8: 8888888888 поскольку цепочки 2222 пока нет, сначала заменяем 8888 на 22: 22888888 цепочки 2222 снова нет, поэтому опять заменяем 8888 на 22: 222288 теперь появилась цепочка 2222, которая согласно алгоритму заменяется на 88: 8888 таким образом, в результате трёх замен цепочка восьмёрок укоротилась на 6 цифр посчитаем, сколько раз так можно сделать: 70 : 6 = 11,(6) – округляем вниз до 11 после 11 таких укорачиваний удалено 66 цифр 8, осталось всего 4, которые заменяются на 22 Ответ: 22. Решение (программа): поскольку при сдаче ЕГЭ в компьютерной форме доступны среды программирования, проще всего написать программу, которая моделирует исполнителя Редактор; для этой цели лучше всего подходит язык Python, обладающий широким набором встроенных функций для обработки символьных строк в начале программы записываем в строковую переменную s 70 цифр 8: s = '8'*70 операция нашлось(2222) заменяется на "2222" in s а заменить(2222, 88) – на s = s.replace( "2222", "88", 1 ) здесь третий аргумент (равный 1)– это количество замен, которые нужно выполнить приведём полную программу 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) аналогичная программа на языке PascalABC.NET: begin var s := StringOfChar('8', 70); var p2 := Pos('2222',s); var p8 := Pos('8888',s); while (p2 > 0) or (p8 > 0) do begin if p2 > 0 then begin Delete( s, p2, 4 ); Insert( '88', s, p2 ); end else begin Delete( s, p8, 4 ); Insert( '22', s, p8 ); end; p2 := Pos('2222',s); p8 := Pos('8888',s); end; write(s); end. программа на языке PascalABC.NET с использованием новых функций (М. Коротков): begin var s: string := '8' * 70; while (s.contains('2222')) or (s.contains('8888')) do begin if (s.contains('2222')) then s := s.replace('2222', '88', 1) else s := s.replace('8888', '22', 1); end; writeln(s); end. аналогичная программа на языке С++: #include using 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; } Ответ: 22. Решение (электронные таблицы, Б.С. Михлин): эту задачу несложно решить с помощью электронных таблиц; в ячейку C1 записываем исходную строку, применяя функцию ПОВТОР (в OpenOffice Calc:=REPT("8";70)) затем нужно определить, есть ли в этой строке сочетания символов «2222» и «8888»; для этого можно использовать функцию НАЙТИ (FIND) эта функция выдаёт ошибку, если образец не найден; эту ошибку мы можем перехватить, используя функцию ЕСЛИОШИБКА (только в Excel 2007+и LibreOfficeCalc); в случае ошибки выведем 0, а при обнаружении образца – его позицию (результат работы функции НАЙТИ); записывается это так (в ячейке A1): =ЕСЛИОШИБКА(НАЙТИ("2222";C1);0) ; аналогично в B1 записываем формулу для поиска строки 8888: =ЕСЛИОШИБКА(НАЙТИ("8888";C1);0) к сожалению, в OpenOfficeCalcнет встроенной функции ЕСЛИОШИБКА (IFERROR), и эти формулы приходится реализовывать через функции IF и ISERROR: А1: =IF(ISERROR(FIND("2222";C1));0;FIND("2222";C1)) В1: =IF(ISERROR(FIND("8888";C1));0;FIND("8888";C1)) теперь в ячейке 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")) аргументы при вызове функции ЗАМЕНИТЬ (REPLACE): 1: исходная строка 2: начальная позиция заменяемой подстроки 3: длина заменяемой подстроки 4: подстрока-замена формулы в диапазоне A2:C2 протягиваем вниз до появления сообщения об ошибке (оно означает, что не найден ни один образец, ни 2222, ни 8888; последняя строка перед ошибкой – это и есть ответ: Ответ: 22. Замечание: вместо вызовов функции ЗАМЕНИТЬ (REPLACE) можно использовать функцию ПОДСТАВИТЬ (SUBSTITUTE): ПОДСТАВИТЬ(С1; "2222";"88";1) и ПОДСТАВИТЬ(С1; "8888";"22";1) здесь четвертый аргумент (1) говорит о том, что нужно выполнить замену только 1 раз (для первого левого вхождения); кавычки в текстовых константах можно не ставить после получения строки с ответом (22) в следующих строках ответ просто повторяется (уже нет сообщения об ошибке, как при использовании функции ЗАМЕНИТЬ); в электронных таблицах (как и в языках программирования) числовое значение ноль в логических выражениях (ЕСЛИ и т.д.) рассматривается как ЛОЖЬ (FALSE), а другие числовые значения (не равные нулю) – как ИСТИНА (TRUE). |