Задание №14.
Умение исполнить алгоритм для конкретного исполнителя с фиксированным набором команд. Уровень сложности задания - повышенный, максимальный балл за выполнение - 1, примерное время выполнения задания - 6 минут.
Знать: алгоритмы с циклами. Эквивалентность алгоритмических моделей.
Уметь: интерпретировать результаты, получаемые в ходе моделирования реальных процессов.
Пример задания.
Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w.
Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.
В конструкции
ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно).
Дана программа:
НАЧАЛО
ПОКА нашлось (11)
ЕСЛИ нашлось (112)
ТО заменить (112, 6)
ИНАЧЕ заменить (11, 3)
КОНЕЦ ПОКА
КОНЕЦ
Исходная строка содержит десять единиц и три двойки, других цифр нет, точный порядок расположения единиц и двоек неизвестен. Какую наибольшую сумму цифр может иметь строка, которая получится после выполнения программы?
Разбор задания. Скажу прямо, это задание не самое сложное, что может быть на экзамене и с ним мы довольно быстро разберёмся.
1. Это задание немного отличается от привычных, так как требуется не полученную цепочку отобразить, а найти наибольшую сумму цифр этой строки. Давайте "пройдёмся" по программе и посмотрим, что она делает. Из неё видно, что если будет строка 112, то программа её заменит на 6, а строку 11 заменит на 3. Следовательно, результатом программы будет строка, состоящая из троек и шестёрок. Из условия нам известно, что необходимо получить наибольшую сумму, а для этого надо, чтобы в полученной строке, было как можно больше цифр 6.
2. Итак, мы имеем набор из десяти единиц и трёх двоек.
Чтобы получить как можно больше шестёрок обратим внимание на строки программы:
ЕСЛИ нашлось (112)
ТО заменить (112, 6)
Из них следует, что все последовательности 112 будут заменены на 6. Давайте расставим наши единицы и двойки таким образом, чтобы получить как можно больше комбинаций 112. Мы получим следующую комбинацию:
3. Теперь "прогоним" эту комбинацию через программу:
ПОКА нашлось (11) // это условие выполняется и цикл начинает работу
ЕСЛИ нашлось (112) // у нас нашлось 112 и мы заменяем этот кусочек строки на 6
4. Опять проверяем условие
ПОКА нашлось (11) // это условие выполняется и цикл начинает работу
ЕСЛИ нашлось (112) // у нас нашлось 112 и мы заменяем этот кусочек строки на 6
5. Снова возвращаемся к началу программы и проверяем условие:
ПОКА нашлось (11) // это условие выполняется и цикл начинает работу
ЕСЛИ нашлось (112) // у нас нашлось 112 и мы заменяем этот кусочек строки на 6
6. Снова возвращаемся к началу программы и проверяем условие:
ПОКА нашлось (11) // это условие выполняется и цикл начинает работу
ЕСЛИ нашлось (112) // у нас комбинации 112 больше не встречается, переходим к следующей строке программы
ИНАЧЕ заменить (11, 3) // комбинация 11 у нас в строке есть и мы заменяем её на 3
7. Продолжаем выполнять программу и проверяем условие цикла:
ПОКА нашлось (11) // это условие выполняется и цикл начинает работу
ЕСЛИ нашлось (112) // у нас комбинации 112 больше не встречается, переходим к следующей строке программы
ИНАЧЕ заменить (11, 3) // комбинация 11 у нас в строке есть и мы заменяем её на 3
8. У нас получилась строка 66633, теперь уже эта строка попадает в программу и проверяется условие цикла
ПОКА нашлось (11) // это условие больше не выполняется и цикл завершает свою работу.
У нас получилась строка 66633, теперь необходимо сложить все цифры и записать ответ. 6+6+6+3+3=24.
Ответ: 24. Ну вот, как-то так.