Задание №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. Ну вот, как-то так.

 

Добавить комментарий


Защитный код
Обновить

© 2019 Информатика и ИКТ. Все права защищены

^ Наверх