Информатика ОГЭ - Комплекс материалов для подготовки учащихся

ТРЕНИРОВОЧНЫЕ МАТЕРИАЛЫ К ЗАДАНИЯМ ЭКЗАМЕНАЦИОННОЙ РАБОТЫ

Задание 1

Тема этого задания - равномерное двоичное кодирование текста. Кодирование называется равномерным потому, что на каждый символ текста отводится одинаковое, известное заранее количество бит. Соотношение между двоичным кодом и символом называется кодовой таблицей. Кодовых таблиц существует достаточно много. Наиболее распространенными являются 8-битные таблицы (КОИ-8, СР1251 и др.), а также 16-битная таблица Unicode.

Для определения объема памяти, требуемого для хранения исходного текста, надо количество знаков в тексте умножить на 8 или 16 бит, в зависимости от таблицы. Следует помнить, что знаками считаются все символы, не только буквы и цифры, но и знаки препинания, пробелы и специальные символы.

Пример 1.1

В одной из кодировок Unicode каждый символ кодируется 16 битами. Определите размер следующего предложения в данной кодировке:

Я вас любил безмолвно, безнадежно, то робостью, то ревностью томим.

1) 536 байт

2) 134 бит

3) 67 байт

4) 1072 бит √

Решение

Следует пересчитать все символы, включая знаки препинания и пробелы. Всего символов 67, требуется 1072 бита (134 байта).

Пример 1.2

В кодировке КОИ-8 каждый символ кодируется одним байтом. Определите количество символов в сообщении, если информационный объём сообщения в этой кодировке равен 160 бит.

1) 10

2) 16

3) 20 √

4) 160

Решение

1 байт = 8 бит. Используется 8-битный код. 160 : 8 = 20 символов в сообщении.

Пример 1.3

Информационное сообщение объёмом 1,5 Кбайта содержит 3072 символа. Каким количеством бит кодируется каждый символ этого сообщения?

1) 32

2) 16

3) 8

4) 4 √

Решение

В формулировке задания нет прямого указания, что код равномерный, но это подразумевается. Переводим объём сообщения в биты: 1,5 Кбайт = 1536 байт = 12288 бит. Делим это число на 3072, получаем 4. На один символ приходится 4 бита.

Дополнительный вопрос: сколько символов можно закодировать, затрачивая только 4 бита на символ? (Ответ - 16 различных символов).

Пример 1.4

Информационный объём статьи, набранной на компьютере, составляет 48 Кбайт. Определите, сколько страниц содержит статья, если известно, что на каждой странице 48 строк, в каждой строке 64 символа, и каждый символ кодируется 16 битами (одна из кодировок Unicode).

1) 4

2) 6

3) 8 √

4) 10

Решение

Для сокращения вычислительной сложности будем оперировать байтами, помня, что 16 бит = 2 байт. Умножением 48х64х2 = 6144 (байт) вычисляем информационный объём одной страницы текста в этой кодировке. Далее делим на 1024 (байт в 1 Кбайт) и получаем 6 Кбайт на страницу. Если весь объём 48 Кбайт, то методом деления 48 : 6 = 8 получаем количество страниц в статье.

Пример 1.5

Статья, набранная на компьютере, содержит 16 страниц, на каждой странице 32 строки, в каждой строке 40 символов. Определите информационный объём статьи в одной из кодировок Unicode, в которой каждый символ кодируется 16 битами.

1) 320 байт

2) 40 Кбайт √

3) 640 байт

4) 32 Кбайт

Решение

Это задача, обратная предыдущей. Умножением определяем количество байт, помня, что 16 бит = 2 байт. 16х32х40х2 = 40960 байт = 40 Кбайт. Для упрощения счета можно учесть, что 16х2 = 32 = 2⁵. Тогда 32х32 = 2⁵х2⁵ - 2¹⁰ - 1024 = 1К и 40 можно умножить на 1 Кбайт.

Задание 2

Это задание всегда содержит два условия, одно из них обычно с отрицанием, связанные операцией “И” или “ИЛИ”. При решении задания надо, во-первых, постараться избавиться от отрицания, перефразировав отрицаемое условие, и, во-вторых, помнить, что операция “И” истинна, только если оба условия истинны (в остальных случаях ложна), а операция “ИЛИ” ложна, только если оба условия ложны (в остальных случаях истинна).

Пример 2.1

Для какого из приведённых чисел истинно высказывание:

(Число > 100) И НЕ(Число нечётное)?

1) 35

2) 4598 √

3) 54321

4) 24

Решение

Преобразуем отрицание, получаем (Число > 100) И (Число четное). Такое число только одно.

Пример 2.2

Для какого из приведённых имён истинно высказывание:

НЕ(Первая буква гласная) И (Количество букв > 5)?

1) Иван

2) Николай √

3) Семён

4) Илларион

Решение

Преобразуем отрицание, получаем (Первая буква согласная) И (Количество букв > 5). Такое имя только одно: “Николай”, так как два начинаются на гласные, а в имени “Семён” ровно 5 букв (второе условие ложно).

Пример 2.3

Для какого из приведённых чисел истинно высказывание: НЕ (число < 50) И (число чётное)?

1) 24

2) 45

3) 74 √

4) 99

Решение

Преобразуем отрицание и получаем (число ≥ 50) И (число четное). Подходит только число 74. Здесь надо обратить внимание, что при отрицании строгое неравенство меняется на нестрогое и наоборот.

Пример 2.4

Для какого из приведённых чисел истинно высказывание:

НЕ(Первая цифра чётная) И НЕ(Последняя цифра нечётная)?

1) 6843

2) 4562

3) 3561

4) 1234 √

Решение

Здесь преобразование отрицания применяется два раза. Операция “И” не изменяется, так как отрицание применяется к каждой части выражения а не к выражению в целом. Получаем (Первая цифра нечётная) И (Последняя цифра чётная). Подходит только число 1234.

Пример 2.5

Для какого из приведённых значений числа X ЛОЖНО высказывание:

НЕ (Х < 6) ИЛИ (Х< 5)?

1) 7

2) 6

3) 5 √

4) 4

Решение

Преобразуем отрицание, получаем (X ≥ 6) ИЛИ (X < 5). Выражение будет ложно только если оба условия ложны. Среди целых чисел такое X единственно, это число 5.

Задание 3

Задание требует установить соответствие между двумя видами моделей: таблицей смежности и графом. В более сложном варианте требуется построить граф по таблице смежности и найти кратчайший путь.

Пример 3.1

В таблице отражено наличие дорог между пятью городами: А, В, С, D и Е. Единица на пересечении строки и столбца указывает на наличие дороги между городами. Укажите схему, соответствующую таблице.

Решение

В данном случае требуется построить граф по таблице. Из А идет две дороги - в В и в Е, из С единственная дорога в D, из В, D и Е выходит три дороги. Таблице соответствует граф № 3.

Пример 3.2

На схеме отражено наличие дорог между пятью городами: А, В, С, D и Е. Укажите таблицу, соответствующую схеме (единица на пересечении строки и столбца указывает на наличие дороги между городами).

Решение

Это обратная предыдущей задача. Надо по данному графу построить таблицу смежности. Построение осуществляем в алфавитном порядке вершин, начинаем с А. В столбцах С и D ставим 1, в остальных столбцах 0. В строке В ставим единицы в трёх столбцах: С, D и Е, а в двух остальных 0. Продолжаем аналогично. Получаем таблицу, приведенную в ответе № 3.

Пример 3.3

Между населёнными пунктами А, В, С, D построены дороги, протяжённость которых (в километрах) приведена в таблице.

Определите длину кратчайшего пути между пунктами А и С. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.

1) 5

2) 6 √

3) 7

4) 8

Решение

В этом задании граф является полным, то есть из каждого пункта есть дорога в три остальных. Кратчайшей оказывается дорога, проходящая через два промежуточных пункта: из А в D (3 км), далее в В (1 км) и, наконец, в С (еще 2 км). Общий путь равен сумме длин ребер, то есть 6 км.

Пример 3.4

Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице.

Определите длину кратчайшего пути между пунктами А и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.

1) 7

2) 8

3) 9 √

4) 10

Решение

Здесь уже дороги есть не везде. В D приходят только две дороги: из С и из Е, но при этом путь из С в D через Е оказывается короче (1+4=5) чем напрямую (6), а путь из А в С через В оказывается также короче (2+2=4), чем по прямой дороге (5 км). Суммарный путь составит 4+5=9 км.

Задание 4

Задание проверяет знание иерархической системы каталогов файлов и умение ею пользоваться. Для записи имен файлов и дерева каталогов используется синтаксис операционной системы DOS/ Windows, являющийся универсальным.

Пример 4.1

Пользователь работал с каталогом Пушкин. Сначала он поднялся на один уровень вверх, потом спустился в каталог Лермонтов и после этого спустился в каталог Стихи. В результате он оказался в каталоге П:\Учеба\Литература\Лермонтов\Стихи. Укажите полный путь того каталога, в котором пользователь работал вначале.

1) D:\Учеба\Литература\Пушкин √

2) D:\Учеба\Литература\Пушкин\Стихи

3) D:\ Учеба\Литература\Стихи\Пушкин

4) D:\Учеба\Пушкин

Решение

Пользователь спустился на два уровня и оказался в каталоге D:\Учеба\Литература\Лермонтов\Стихи. Значит он оказался в каталоге D:\Учеба\Литература\ из каталога D:\Учеба\Литература\Пушкин, поднявшись на один уровень вверх.

Пример 4.2

Пользователь работал с каталогом Участники. После окончания работы с этим каталогом, он поднялся на один уровень вверх, затем спустился на один уровень вниз, потом ещё раз спустился на один уровень вниз.

В результате он оказался в каталоге С:\Конференция\Секции\Информатика

Укажите возможный полный путь каталога, с которым пользователь начинал работу.

1) С:\Конференция\Регионы\Списки\Участники

2) С:\Конференция\Участники √

3) С:\Конференция\Регионы\Участники

4) С:\У частники

Решение

Пользователь спустился на два уровня из каталога С:\Конференция. В этом каталоге он оказался, поднявшись на один уровень вверх. Исходный каталог назывался С:\Конференция\Участники.

Пример 4.3

В некотором каталоге хранился файл с именем сирень.jpg. После того как в этом каталоге создали подкаталог Цветы и переместили в него файл сирень.jpg, полное имя файла стало D:\Mapинa\Pисунки\Цветы\сирень.jpg

Каким было полное имя этого файла до перемещения?

1) D:\Рисунки\Цветы\сирень.jpg

2) D:\Марина\Цветы\сирень.jрg

3) D:\Марина\Рисунки\

4) D:\Марина\Рисунки\сирень.jpg √

Решение

Файл лежал первоначально в каталоге на один уровень выше, то есть в каталоге D:\Марина\Рисунки. Полное имя файла было D:\Марина\Рисунки\сирень.jpg.

Пример 4.4

Пользователь работал с файлом C:\Work\9klass\Math\Geom\part1.doc. Затем он поднялся на два уровня вверх, создал там каталог Form, в нём создал ещё один каталог lessons и переместил в него файл part1.doc. Каким стало полное имя этого файла после перемещения?

1) C:\Work\9klass\Math\Form\lessons\part1.doc

2) C:\Work\9klass\Form\lessons\part1.doc √

3) C:\Work\Form\lessons\part1.doc

4) C:\Work\9klass\Math\Geom\Form\lessons\part1.doc

Решение

Пользователь поднялся на два уровня вверх в каталог C:\Work\9klass. Там он создал каталог Form, в нём создал ещё один каталог lessons. Тем самым полное имя нового каталога стало C:\Work\9klass\Form\lessons, а полное имя файла C:\Work\9klass\Form\lessons\part1.doc.

Задание 5

Данное задание требует соотнести между собой таблицу и построенную по ее значениям диаграмму. При решении следует обращать внимание на соотношение значений, по которым строится диаграмма.

Пример 5.1

Дан фрагмент электронной таблицы.

	А	В	С	D
1		1	2
2	=С1/2	=(А2+В1)/2	=С1-В1	=2*В2

После выполнения вычислений была построена диаграмма по значениям диапазона ячеек A2:D2. Укажите получившуюся диаграмму.

Решение

Прежде всего надо вычислить значения формул диапазона ячеек A2:D2.

	А	В	С	D
1		1	2
2	1	1	1	2

Из представленных диаграмм только у диаграммы №1 значения соотносятся как 1:1:1:2. У диаграммы № 2 все значения равны, у диаграммы № 3 соотношение 1:2:2:1, у диаграммы №4 соотношение 1:1:1:3.

Пример 5.2

Дан фрагмент электронной таблицы, в первой строке которой записаны числа, а во второй формулы:

	А	В	С	D
1	4	2	3	1
2	=А1-В1		=В1-1	=A1-B1+D1

Какая из перечисленных ниже формул должна быть записана в ячейке В2, чтобы построенная после выполнения вычислений круговая диаграмма по значениям диапазона ячеек A2:D2 соответствовала рисунку?

1) =А1-С1

2) =А1-1

3) =(C1+D1)/2 √

4) =B1-D1

Решение

Сектора на диаграмме соотносятся как 2:2:1:3. Вычислив значения формул диапазона ячеек A2:D2, мы понимаем, что значение формулы в ячейке В2 должно быть равно 2. Единственная формула, имеющая такое значение - № 3: =(C1+D1)/2.

Пример 5.3

Дан фрагмент электронной таблицы.

	А	В	С	D	Е	F	G
1	12		4		3
2	=С1*Е1	=А1-С1	=С1*2	=А1/Е1	=Е1	=С1/2	=F2

После выполнения вычислений по некоторым ячейкам диапазона A2:G2 была построена диаграмма. Укажите адреса этих ячеек.

1) А2; В2; С2; G2

2) А2; D2; F2; G2 √

3) А2; Е2; F2; G2

4) В2; D2; Е2; F2

Решение

Здесь следует прежде всего вычислить все значения формул в диапазоне A2:G2:

	А	В	С	D	Е	F	G
1	12		4		3
2	12	8	8	4	3	2	2

Видно, что на диаграмме длины столбиков соотносятся как числа 1:1:2:6. В диапазоне A2:G2 так соотносятся только ячейки G2; F2; D2; А2. Этот набор ячеек (в обратном порядке) представлен в варианте ответа № 2.

Задание 6

В этом задании требуется понять, как устроен исполнитель алгоритмов, проанализировать возможный результат исполнения алгоритма в зависимости от значений параметров некоторых команд. Задание всегда содержит краткое описание исполнителя, его команд и синтаксиса языка. В процессе решения следует прежде всего выяснить, как влияют на результат исполнения алгоритма различные значения параметров команд.

Пример 6.1

Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует две команды:

Вперёд n (где n - целое число), вызывающая передвижение Черепашки на n шагов в направлении движения;

Направо m (где m - целое число), вызывающая изменение направления движения на m градусов по часовой стрелке.

Запись Повтори k [Команда1 Команда2 Команда3] означает, что последовательность команд в скобках повторится k раз.

Черепашке был дан для исполнения следующий алгоритм:

Повтори 7 [Вперёд 70 Направо 120]

Какая фигура появится на экране?

1) правильный семиугольник

2) правильный шестиугольник

3) правильный треугольник √

4) незамкнутая ломаная линия

Решение

Ключевым параметром, определяющим то, какая фигура появится на экране, является поворот Черепашки. Поворот на 120 градусов - это треть полного оборота вокруг своей оси. Поэтому передвижение Черепашки при любом (больше 2) количестве повторений будет оставлять след в виде одного правильного треугольника.

Пример 6.2

Вперёд n (где n - целое число), вызывающая передвижение Черепашки на n шагов в направлении движения,

Направо m (где m - целое число), вызывающая изменение направления движения на m градусов по часовой стрелке.

Черепашке был дан для исполнения следующий алгоритм:

Повтори 12 [Направо 45 Вперёд 20 Направо 45]

Какая фигура появится на экране?

1) квадрат √

2) правильный двенадцатиугольник

3) правильный восьмиугольник

4) незамкнутая ломаная линия

Решение

Здесь на одно передвижение приходится два поворота по 45 градусов каждый. В сумме это 90 градусов, то есть четверть круга. Четыре выполнения последовательности команд в скобках вызовет появление на экране квадрата, далее Черепашка будет ползать по той же траектории.

Пример 6.3

Исполнитель Чертежник перемещается на координатной плоскости, оставляя след в виде линии. Чертежник может выполнять команду Сместиться на (а, b) (где а, b - целые числа), перемещающую Чертежника из точки с координатами (х, у), в точку с координатами (х+а, у+b). Если числа а, b положительные, значение соответствующей координаты увеличивается, если отрицательные - уменьшается.

Например, если Чертежник находится в точке с координатами (4, 2), то команда Сместиться на (2, -3) переместит Чертежника в точку (6, -1).

Запись

Повтори k раз

Команда1 Команда2 Команда3

конец

означает, что последовательность команд Команда1 Команда2 Команда3 повторится k раз. Чертежнику был дан для исполнения следующий алгоритм:

Сместиться на (-5, 2)

Повтори 5 раз

Сместиться на (2, 0) Сместиться на (-3, -3) Сместиться на (-1, 0)

конец

На какую одну команду можно заменить этот алгоритм, чтобы Чертежник оказался в той же точке, что и после выполнения алгоритма?

1) Сместиться на (-10, -15)

2) Сместиться на (15, 13)

3) Сместиться на (10, 15)

4) Сместиться на (-15, -13) √

Решение

В этом задании надо всего лишь вычислить вектор суммарного перемещения Чертежника. Каждый шаг цикла Чертежник перемещается по оси х на 2-3-1=-2 единицы, а по оси у на -3 единицы. За пять выполнений тела цикла Чертежник переместится на (-10, -15). Прибавим к этому начальное перемещение (-5, 2) и получаем, что весь алгоритм сводится к одной команде “Сместиться на (-15, -13)”

Пример 6.4

Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду

Сместиться на (а, b) (где а, b - целые числа), перемещающую Чертёжника из точки с координатами (х, у) в точку с координатами (х+а, у+b). Если числа а, b положительные, значение соответствующей координаты увеличивается, если отрицательные - уменьшается.

Например, если Чертёжник находится в точке с координатами (4, 2), то команда Сместиться на (2, -3) переместит Чертёжника в точку (6, -1).

Запись

Повтори k раз

Команда1 Команда2 Команда3

Конец

означает, что последовательность команд Команда1 Команда2 Команда3 повторится k раз.

Чертёжнику был дан для исполнения следующий алгоритм:

Повтори 3 раз

Сместиться на (-2, -1) Сместиться на (3, 2) Сместиться на (2, 1)

Конец

Какую единственную команду надо выполнить Чертёжнику, чтобы вернуться в исходную точку, из которой он начал движение?

1) Сместиться на (-6, -9)

2) Сместиться на (-9, -6) √

3) Сместиться на (6, 9)

4) Сместиться на (9, 6)

Решение

Это задание похоже на предыдущее, только здесь нужно сначала определить итоговое перемещение Чертежника в результате выполнения алгоритма, а затем записать одну команду, возвращающую Чертежника в исходную точку. Аналогично вычисляем перемещение Чертежника за одно выполнение цикла: по оси х на -2+3+2=3 единицы и на -1+2+1=2 единицы по оси у. За 3 выполнения цикла Чертежник смещается на (9, 6). Соответственно, команда “Сместиться на (-9, -б)” вернет его в начальное положение.

Пример 6.5

Сместиться на (а, b) (где а, b - целые числа), перемещающую Чертёжника из точки с координатами (х, у) в точку с координатами (х+а, у+b). Если числа а, b положительные, значение соответствующей координаты увеличивается; если отрицательные, уменьшается.

Запись

Повтори k раз

Команда1 Команда2 Команда3

Конец

означает, что последовательность команд Команда1 Команда2 Команда3 повторится k раз.

Чертёжнику был дан для исполнения следующий алгоритм:

Повтори 2 раз

Команда1 Сместиться на (1, 3) Сместиться на (1, -2)

Конец

Сместиться на (2, 6)

После выполнения этого алгоритма Чертёжник вернулся в исходную точку. Какую команду надо поставить вместо команды Команда1?

1) Сместиться на (3, 4)

2) Сместиться на (-6, -8)

3) Сместиться на (-3, -4) √

4) Сместиться на (-4, -7)

Решение

Так как после выполнения этого алгоритма Чертёжник вернулся в исходную точку, общее перемещение Чертежника после цикла составило (-2, -6). Цикл выполнялся 2 раза, поэтому комбинация из трех команд в теле цикла перемещает Чертёжника на вектор (-1, -3). В связи с тем, что реализация двух известных команд дает смещение на (2, 1), первая команда должна переместить Чертёжника на (-3, -4).

Задание 7

В отличие от задания № 1 в этом задании используются кодовые таблицы с неравномерным кодом. Решение обычно достигается подбором подходящих вариантов.

Пример 7.1

От разведчика была получена следующая шифрованная радиограмма, переданная с использованием азбуки Морзе:

При передаче радиограммы было потеряно разбиение на буквы, но известно, что в радиограмме использовались только следующие буквы:

Определите текст радиограммы. В ответе укажите, сколько букв было в исходной радиограмме.

Ответ: 7.

Решение

На тире начинается код только одной буквы: Т, поэтому первая буква Т. Буква X в сообщении не встречается, так как в шифровке нет 4-х подряд идущих точек. Коды трёх остальных букв заканчиваются на тире. Восстанавливаем текст шифровки: ТААУТАТ, в тексте 7 букв.

Пример 7.2

Сообщение было зашифровано кодом. Использовались только буквы, приведённые в таблице:

Определите, какие буквы в сообщении повторяются, и запишите их в ответе.

Ответ: ДЕ: ЕД.

Решение

Три подряд точки есть только в коде буквы Д. Начинаем расшифровку слева: ДЕДГЕ. Буквы Д и Е в слове повторяются.

Пример 7.3

Валя шифрует русские слова (последовательности букв), записывая вместо каждой буквы её код.

А	Д	К	Н	О	С
01	100	101	10	111	000

Некоторые шифровки можно расшифровать не одним способом. Например, 00010101 может означать не только СКА, но и СНК.

Даны три кодовые цепочки:

100101000

100000101

0110001

Найдите среди них ту, Которая имеет только одну расшифровку, и запишите в ответе расшифрованное слово.

Ответ: АДА.

Решение

Перебираем цепочки сверху вниз. В первой строке комбинация цифр 100101 может быть расшифрована как НАА или как ДК. Вторую строку можно расшифровать как НСАА или как ДСК. И лишь третья строка имеет единственную расшифровку: АДА.

Пример 7.4

Ваня шифрует русские слова, записывая вместо каждой буквы её номер в алфавите (без пробелов). Номера букв даны в таблице.

А	1	Й	11	У	21	Э	31
Б	2	К	12	Ф	22	Ю	32
В	3	Л	13	X	23	Я	33
Г	4	М	14	Ц	24
Д	5	Н	15	Ч	25
Е	6	О	16	ш	26
Ё	7	П	17	Щ	27
Ж	8	Р	18	Ъ	28
3	9	С	19	Ы	29
И	10	Т	20	Ь	30

Некоторые шифровки можно расшифровать несколькими способами. Например, 311333 может означать “ВАЛЯ”, может - “ЭЛЯ”, а может - “ВААВВВ”.

Даны четыре шифровки:

213113

987212

512030

266741

Только одна из них расшифровывается единственным способом. Найдите её и расшифруйте. Получившееся слово запишите в качестве ответа.

Ответ: ДАТЬ.

Решение

В первой, второй и четвертой строке встречаются сочетания цифр 12, 13, 31, 11, 21, 26, которые имеют неоднозначную интерпретацию. Только третья строка расшифровывается однозначно: 5-Д, 1-А, 20-Т, 30-Ь.

Задание 8

Это задание проверяет понимание экзаменуемым оператора присваивания и знание приоритета арифметических операций. Его решение предполагает последовательное исполнение фрагмента алгоритма, содержащего 3-4 оператора присваивания.

Пример 8.1

В программе “:=” обозначает оператор присваивания, знаки “+”, “-”, “*” и “/” - соответственно операции сложения, вычитания, умножения и деления. Правила выполнения операций и порядок действий соответствуют правилам арифметики.

Определите значение переменной а после выполнения данного алгоритма:

В ответе укажите одно целое число - значение переменной а.

Ответ: 18.

Решение

Последовательно исполним данный алгоритм, определив значение переменных после выполнения каждой строки:

Строка алгоритма	Что выполняется	Значение а	Значение b
а := 3	Число 3 записывается в а	3	Не опред.
b := 6	Число 6 записывается в b	3	6
b := 12+а*b	Вычисляется значение 12+(3x6)=30 и записывается в b	3	30
а := b/5*а	Вычисляется значение (30/5)x3=18 и записывается в а	18	30

Пример 8.2

В программе “:=” обозначает оператор присваивания, знаки “+”, “-”, “*” и “/” - операции сложения, вычитания, умножения и деления. Правила выполнения операций и порядок действий соответствуют правилам арифметики.

Определите значение переменной а после выполнения данного алгоритма:

В ответе укажите одно целое число — значение переменной а.

Ответ: 2.

Решение

Последовательно исполним данный алгоритм, определив значение переменных после выполнения каждой строки:

Строка алгоритма	Что выполняется	Значение а	Значение b
а := 4	Число 4 записывается в а	4	Не опред.
b := 3	Число 3 записывается в b	4	3
b := a+2*b	Вычисляется значение 4+(2x3)=10 и записывается в b	4	10
а := a*5/b	Вычисляется значение (4x5)/10=2 и записывается в а	2	10

Задание 9

Это задание содержит циклический алгоритм. Оно также выполняется формальным исполнением алгоритма. В тексте задания программа приводится на трёх языках программирования, все три программы эквивалентны.

Пример 9.1

Запишите значение переменной s, полученное в результате работы следующей программы. Текст программы приведён на трёх языках программирования.

Алгоритмический язык	Бейсик	Паскаль

Ответ: 66.

Решение

Цикл выполняется 6 раз, в цикле происходит увеличение переменной s на 11. Поскольку первоначальным значением s был 0, в результате работы программы значение s будет равно 6x11=66.

Пример 9.2

Алгоритмический язык
Бейсик
Паскаль

Ответ: 81.

Решение

Цикл выполняется 4 раза, в цикле происходит умножение переменной 5 на 3. Поскольку первоначальным значением s была 1, в результате работы программы значение s будет равно 3⁴=81.

Задание 10

Это третье задание, содержащее программу на языке программирования. В программе всегда сначала задаются значения отдельных элементов массива, a потом в один проход по массиву происходит какая-то его обработка. По алгоритму следует понять, какая обработка происходит. Задача также может быть решена методом формального исполнения программы.

Пример 10.1

В таблице Dat представлены данные о количестве голосов, поданных за 10 исполнителей народных песен (Dat[1] - количество голосов, поданных за первого исполнителя, Dat[2] - за второго и т. д.). Определите, какое число будет напечатано в результате работы следующей программы. Текст программы приведён на трёх языках программирования.

Алгоритмический язык	Бейсик	Паскаль

Ответ: 12.

Решение

В данном случае алгоритм ищет минимальное значение в массиве. Это восьмой элемент, его значение 12.

Пример 10.2

В таблице Dat хранятся данные ежедневных измерений количества осадков за неделю в миллиметрах (Dat[1] - данные за понедельник, Dat[2] - за вторник и т.д.). Определите, что будет напечатано в результате выполнения следующего алгоритма, записанного на трёх языках программирования.

Алгоритмический язык
Бейсик
Паскаль

Ответ: 4.

Решение

В данном случае алгоритм ищет максимальное значение в массиве. Это значение равно 15. В массиве два таких значения: у элементов Dat[4] и Dat[6]. Однако печатает программа не значение максимального осадка, а значения переменной day. Это значение изменяется, когда программа находит очередной максимум, то есть значение, большее предыдущего максимума. В данном примере значение переменной day изменится, когда k=4 и больше изменяться не будет.

Пример 10.3

Алгоритмический язык	Бейсик	Паскаль

Ответ: 7.

Решение

Переменная т увеличивается на 1 каждый раз, когда значение массива меньше 25. То есть считается, сколько таких элементов в массиве, поскольку первоначальное значение переменной т равно 0.

Задание 11

Это задание требует подсчета количества путей в графе. При достаточно большом графе выполнение этого задания методом простого перебора всех путей приведет к неизбежным ошибкам. Лучше решать подобные задания методами динамического программирования.

Пример 11.1

На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж 3, И, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?

Ответ: 23.

Решение

Для решения этой задачи будем последовательно подписывать около каждого названия города число путей, по которым можно туда попасть. В города Б и Д ведет единственный путь - из А. В город В можно попасть напрямую из А или через город Б. В город Г ведет 3 стрелки: из городов А, В и Д. Но так как в город В из города А можно попасть 2-мя путями (напрямую и через Б), то всего из А в Г ведут 4 пути. Подпишем эти числа на графе рядом с названием города:

В город Е ведет дорога только из города Б, в который из А единственный путь. Значит из города А в город Е (а потом и в город И) можно добраться единственным путем. Подписываем единички рядом с названием Е и И.

В город можно добраться из города Д и города Г. В Д из А ведет ровно одна дорога, а в Г можно добраться из А, как мы уже установили, 4 способами. Значит из А в Ж существует 5 путей.

В город 3 из А можно доехать через Е (единственный путь), через В (2 пути), через Г (4 пути) и через Ж (5 путей). Таким образом, существует 12 различных путей из А в 3.

В город К ведет единственная стрелка из города Ж, в который из А существует 5 путей. Значит, в город К также ведет 5 путей из А.

Наконец, в город Л приводят 4 стрелки: из города И (1 путь), 3 (12), Ж (5) и К (5). Таким образом, из города А в город Л существует 23 пути.

При решении этой задачи мы воспользовались методом динамического программирования, когда вычисления, которые мы делаем на каждой стадии, основываются на результатах предыдущих вычислений. Таким способом можно считать количество путей в любых, самых сложных графах.

Пример 11.2

На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Ответ: 7.

Задание 12

Это задание проверяет понимание принципов фильтрации баз данных. Приводится таблица с данными и составное логическое условие, по которым из базы данных должны быть отобраны записи. При решении этого задания происходит имитация работы компьютера по отбору подходящих условию поиска записей из всего массива записей реляционной базы данных.

Пример 12.1

Ниже в табличной форме представлен фрагмент базы данных о морях мира.

Название моря	Океан	Площадь (тыс. км²)	Максимальная глубина (метров)
Лазарева	Атлантический	929	4500
Фиджи	Тихий	3177	7633
Филиппинское	Тихий	5726	10263
Азовское	Атлантический	38	14
Красное	Индийский	450	3040
Берингово	Тихий	2315	4151
Бисмарка	Тихий	310	2665
Чёрное	Атлантический	422	2210

Сколько записей в данном фрагменте удовлетворяют условию

(Площадь < 2000) И (Максимальная глубина > 2500)?

В ответе укажите одно число - искомое количество записей.

Ответ: 3.

Решение

Отметим в таблице серым фоном значения, отвечающие каждому из заданных условий:

Дальше нам надо посмотреть количество строк, где мы отметили значения в обоих столбцах (так как условия связаны операцией “И”). Таких строк 3: моря Лазарева, Красное и Бисмарка.

Пример 12.2

Ниже в табличной форме представлен фрагмент базы данных о морях мира.

Название моря	Океан	Площадь (тыс. км²)	Максимальная глубина (метров)
Лазарева	Атлантический	929	4500
Фиджи	Тихий	3177	7633
Филиппинское	Тихий	5726	10263
Азовское	Атлантический	38	14
Красное	Индийский	450	3040
Берингово	Тихий	2315	4151
Бисмарка	Тихий	310	2665
Чёрное	Атлантический	422	2210

Сколько записей в данном фрагменте удовлетворяют условию

(Океан = “Атлантический”) ИЛИ (Площадь < 500)?

В ответе укажите одно число - искомое количество записей.

Ответ: 5.

Решение

Таблица с данными та же самая, только условия связаны операцией “ИЛИ”. Поэтому нам будут подходить данные, удовлетворяющие хотя бы одному условию. Проделаем те же действия по выделению подходящих значений полей:

Далее подсчитаем количество строк, где есть хотя бы одно отмеченное поле. Таких строк 5: моря Лазарева, Азовское, Красное, Бисмарка и Черное.

Задание 13

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

Пример 13.1

Переведите число 87 из десятичной системы счисления в двоичную систему счисления.

В ответе укажите двоичное число. Основание системы счисления указывать не нужно.

Ответ: 1010111.

Решение

Представим число 87 в виде суммы степеней двойки:

87 = 64 + 16 + 4 + 2 + 1 = 2⁶ + 2⁴ + 2² + 2¹ + 2⁰.

Запишем 1, если степень присутствует в сумме и 0, если степень пропущена. Получаем двоичную запись 1010111₂

Пример 13.2

Переведите двоичное число 1110001₂ в десятичную систему счисления.

Ответ: 113.

Решение

В двоичной записи 7 цифр, поэтому старшая цифра обозначает 2⁶ (64). Запишем сумму, где на место единиц поставим соответствующие значения степеней двойки:

1110001₂ = 2⁶ + 2⁵ + 2⁴ + 0 + 0 + 0 + 2⁰ = 64 + 32 + 16 + 1 = 113₁₀

Задание 14

Данное задание предполагает создание линейного алгоритма для исполнителя с небольшим набором команд.

Пример 14.1

У исполнителя Вычислитель две команды, которым присвоены номера:

1. умножь на 4

2. вычти 3

Первая из них увеличивает число на экране в 4 раза, вторая уменьшает его на 3.

Составьте алгоритм получения из числа 2 числа 14, содержащий не более 5 команд. В ответе запишите только номера команд.

(Например, 11221 - это алгоритм:

умножь на 4

вычти 3

умножь на 4,

который преобразует число 1 в 40.)

Если таких алгоритмов более одного, то запишите любой из них.

Ответ: 12122.

Решение

Число 14 не делится на 4, но 14 + 3 + 3 = 20 делится на 4. Значит последние три команды будут 122. Чтобы получить из числа 2 число 5, надо сначала умножить 2 на 4, а затем из получившегося числа 8 вычесть 3. Это две команды: 12. Полностью алгоритм имеет вид: 12122.

Пример 14.2

У исполнителя Квадратор две команды, которым присвоены номера:

1. раздели на 3

2. возведи в квадрат

Первая из них уменьшает число на экране в 3 раза, вторая возводит число в квадрат.

Исполнитель работает только с натуральными числами.

Составьте алгоритм получения из числа 18 числа 16, содержащий не более 4 команд. В ответе запишите только номера команд.

(Например, 1212 - это алгоритм:

раздели на 3

возведи в квадрат

раздели на 3

возведи в квадрат

который преобразует число 18 в 144).

Если таких алгоритмов более одного, то запишите любой из них.

Ответ: 1122.

Решение

Число 16 - это квадрат числа 4, которое в свою очередь квадрат двойки. Чтобы получить из числа 18 число 2 делением на 3, надо применить операцию два раза: сначала получить 6, а затем 2. Итак, должно быть сначала два деления, а затем два возведения в квадрат. Запишем алгоритм на языке исполнителя Квадратор: 1122.

Задание 15

Тематика данного задания: скорость передачи данных. Это расчетные задачи, в которых надо определить либо объем переданных файлов, либо время передачи, зная скорость. Для снижения вычислительной сложности заданий рекомендуется правильно выбирать единицы, в которых ведутся расчеты и хорошо знать значения степеней двойки.

Пример 15.1

Скорость передачи данных через ADSL-соединение равна 256000 бит/с. Передача файла через данное соединение заняла 16 секунд. Определите размер файла в Кбайт.

В ответе укажите одно число - размер файла в Кбайт. Единицы измерения писать не нужно.

Ответ: 500.

Решение

Прежде всего, надо перейти от битов к байтам и Кбайт. Запишем умножение (скорость на время) и деление (число бит в байте и байт в Кбайт), а потом сократим общие множители. Результат будет в Кбайт.

Пример 15.2

Скорость передачи данных через WAP-соединение равна 512000 бит/с. Через данное соединение было передано 500 Кбайт. Сколько секунд потребовалось для передачи файла.

В ответе укажите одно число - длительность передачи в секундах. Единицы измерения писать не нужно.

Ответ: 8.

Решение

Для определения времени передачи мы должны переданный объем разделить на скорость. Здесь, наоборот, целесообразно перейти от Кбайт к битам, а потом сократить тысячи. Запишем объем в битах и разделим на скорость. Результат будет в секундах

Пример 15.3

Файл размером 16 Кбайт передаётся через некоторое соединение со скоростью 2048 бит в секунду. Определите размер файла (в Кбайт), который можно передать за то же время через другое соединение со скоростью 512 бит в секунду.

В ответе укажите одно число - размер файла в Кбайт. Единицы измерения писать не нужно.

Ответ: 4.

Решение

Здесь не требуется вычислять объемы, достаточно составить пропорцию:

2048 / 512 = 16 / х.

Решив пропорцию, получаем х = 4

Задание 16

Это задание предполагает исполнение алгоритма, записанного на естественном языке в виде определенной совокупности правил. Оно обычно заключается в выборе из некоторого множества элементов, отвечающих данной совокупности правил.

Пример 16.1

Цепочка из трех бусин, помеченных латинскими буквами, формируется по следующему правилу:

- в середине цепочки стоит одна из бусин С, D, Н, В;

- в конце - одна из бусин А, В, С, которой нет на втором месте;

- на первом месте - одна из бусин А, В, D, Н, не стоящая в конце.

Определите, сколько из перечисленных цепочек созданы по этому правилу?

BDB НВА DCC DDA DAB BHD CDB BDC ACB

В ответе запишите только количество цепочек.

Ответ: 4

Решение

Всего в исходном множестве 9 цепочек. Первому правилу не отвечает одна цепочка DAB, стоящая на 5 месте. Второму правилу не отвечают цепочка DCC, стоящая на 3 месте и цепочка BHD, стоящая на 6 месте. Третье правило нарушают стоящая на 1 месте цепочка BDB и цепочка CDB, которая стоит на 7 месте. Таким образом, всем трём правилам соответствуют 4 цепочки: НВА, DDA, BDC и ACB.

Пример 16.2

Автомат получает на вход четырёхзначное десятичное число. По полученному числу строится новое десятичное число по следующим правилам.

1. Вычисляются два числа - сумма четных цифр и сумма нечетных цифр заданного числа.

2. Полученные два числа записываются друг за другом в порядке невозрастания (без разделителей).

Пример. Исходное число: 2177. Сумма четных цифр — 2, сумма нечетных цифр — 15.

Результат: 152.

Определите, сколько из приведённых ниже чисел могут получиться в результате работы автомата. 294 1113 232 1716 1212 121 422 370 30 В ответе запишите только количество чисел.

Ответ: 4

Решение

При решении задач этого типа следует перебирать числа по одному и смотреть, насколько они соответствуют условию задания. В числе 294 первые две цифры должны образовать число - сумму трех нечетных цифр, которая очевидно не больше 27. Это число не подходит. В числе 1113 два двузначных числа идут по возрастанию, не подходит. Число 232 подходит, сумму 23 могут образовать 3 нечетные цифры, например 779. Число 1716 не подходит, так как два двузначных числа могу быть только суммой двух пар чисел, но суммы пар всегда четные (сумма двух нечетных всегда четна). Число 1212 подходит, это может быть, например, результат преобразования числа 5676. Число 121 также подходит, если 12 - сумма трёх четных цифр (например: 6, 4, 2). Число 422 не подходит, так как при разбиении 42 и 2 двузначное число больше максимальной суммы трех цифр (27), а при разбиении 4 и 22 нарушается правило невозрастания. Число 370 не подходит по той же причине. И, наконец, число 30 подходит, оно получится, например, при преобразовании числа 1011.

Подведем итог - из приведенных 9 чисел 4 числа могут быть результатом работы автомата.

Пример 16.3

Автомат получает на вход пятизначное десятичное число. По полученному числу строится новое десятичное число по следующим правилам.

1. Вычисляются два числа - сумма первых трёх цифр и сумма последних трёх цифр.

2. Полученные два числа записываются друг за другом в порядке невозрастания (без разделителей).

Пример. Исходное число: 15177. Поразрядные суммы: 7, 15. Результат: 157.

Определите, сколько из приведённых ниже чисел могут получиться в результате работы автомата.

2828 2512 2518 2524 2425 1825 1225 123

В ответе запишите только количество чисел.

Ответ: 4

Решение

Эта задача похожа на предыдущую, здесь также следует перебирать числа по одному и смотреть, насколько они соответствуют условию задания. Вспоминаем, что в порядке невозрастания - это значит, что четверки или тройки цифр надо разбить на два числа, первое из которых больше либо равно второму. Сумма трех цифр никак не может быть трехзначной, поэтому четверки цифр следует разбивать на два двузначных числа. В четверке 2828 первые две цифры должны образовать число - сумму трех цифр, которая очевидно не больше 27. Это число не подходит. В числе 2512 два двузначных числа идут по убыванию, что подходит. Сумму 25 могут образовать 3 цифры, например 699, а число 12 можно представить как сумму цифр 642 или даже 921. Аналогично подходят числа 2518 и 2524. Число 2425 не подходит, так как второе число больше первого. Аналогично не подходят числа 1825 и 1225. Число 123может быть представлено как две суммы: 12 и 3. Сумма 3 может быть только у числа 111, а вот число 12 легко раскладывается в сумму, содержащую единицу, например 921. Так что число 123 подходит.

Подведем итог - из приведенных 8 чисел 4 числа могут быть результатом работы автомата.

Задание 17

Это задание проверяет знание экзаменующимся стандарта записи ссылок (URL) на ресурсы Интернет. В ссылке сначала пишется протокол доступа, затем двоеточие и две косые черты, затем имя сервера, косая черта и имя файла. Имя сервера может быть составным, имя файла обычно содержит расширение. Части имени сервера и имя файла и расширение разделяются точками. В задании требуется как в конструкторе собрать URL из отдельных деталей в соответствии с описанным выше правилом.

Пример 17

Доступ к файлу ftp.doc, находящемуся на сервере pochta.net, осуществляется по протоколу ftp. Фрагменты адреса файла закодированы буквами от А до Ж. Запишите последовательность этих букв, кодирующую адрес указанного файла в сети Интернет.

A) ftp:

Б) ftp.

B) doc

Г) //

Д) pochta

Е) /

Ж) .net

Ответ:

Решение

Записываем URL согласно правилу: ftp://pochta.net/ftp.doc, а затем разбиваем строку на составные элементы. В данном примере сочетание букв “ftp” присутствует как в имени протокола, так и в названии файла. Но во фрагменте А после указанных букв идет двоеточие, а во фрагменте Б - точка. Очевидно, что во фрагменте A ftp - имя протокола, а во фрагменте Б - часть имени файла.

Задание 18

Это задание моделирует результаты поиска в интернет. Экзаменующимся надо расположить запросы в порядке возрастания или убывания количества страниц, которые могут быть найдены. Задача решается на основе здравого смысла и простого рассуждения, или, более формально, с применением диаграмм Эйлера-Венна.

Пример 18

В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу.

Для обозначения логической операции “ИЛИ” в запросе используется символ “|”, а для логической операции “И” - “&”.

A	законы & физика
Б	законы \| (физика & биология)
В	законы & физика & биология
Г	законы \| физика \| биология

Ответ: ВАБГ

Решение

Можно использовать два способа решения, один из которых основан на рассуждении, а второй предполагает использование графического представления операций над множествами в виде пересекающихся фигур.

Рассуждая логически, мы видим, что больше всего будет найдено страниц по запросу Г, так как при его исполнении будут найдены и страницы со словом “законы” (в том числе, например, и юридические), и страницы, со словом “физика”, и страницы со словом “биология”. Меньше всего будет найдено страниц по запросу В, так как в нем требуется присутствие всех трех слов на искомой странице.

Осталось сравнить запросы А и Б. По запросу Б будет найдены все страницы, соответствующие запросу А, (так как в последних обязательно присутствует слово “законы”), а также страницы, содержащие одновременно слова “физика” и “биология”. Следовательно, по запросу Б будет найдено больше страниц, чем по запросу А.

Итак, упорядочив запросы по возрастанию страниц, получаем ответ: ВАБГ.

Для решения вторым способом рассмотрим множества страниц, содержащие каждое из искомых слов. Запросу X&Y будет соответствовать пересечение множеств X и Y, а запросу X | Y - их объединение. Воспользуемся графическим представлением действий над множествами и сравним площади получившихся фигур (см. рисунок).

Задание 19

Задание 19 выполняется на компьютере. Экзаменующийся получает от организатора в аудитории файл электронной таблицы с данными и задание. Задание выдается в бумажной форме. Оно содержит описание структуры данных в таблице и конкретные указания, какие два значения следует вычислить, опираясь на данные из таблицы и в каких ячейках таблицы их следует записать.

Электронные таблицы - довольно мощный вычислительный инструмент и обычно существует несколько способов вычисления требуемых значений. При проверке решения не имеет значения, каким способом получен искомый результат, эксперты сравнивают полученный результат с эталонным и, соответственно, засчитывают или не засчитывают задание.

Максимальный балл, который можно получить за 19 задание - 2 балла. Эта оценка ставится в том случае, если получены два верных значения. В том случае, когда только одно значение верно, выставляется 1 балл.

Файл таблицы с верным ответом и всеми исходными данными требуется сохранить под именем, которое сообщит организатор в аудитории экзамена.

Пример задания 19 (бумажная часть КИМ).

В электронную таблицу занесли данные о калорийности продуктов. Ниже приведены первые пять строк таблицы.

	А	Б	В	Г	Д
1	Продукт	Жиры, г	Белки, г	Углеводы, г	Калорийность, Ккал
2	Арахис	45,2	26,3	9,9	552
3	Арахис жареный	52	26	13,4	626
4	Горох отварной	0,8	10,5	20,4	130
5	Горошек зелёный	0,2	5	8,3	55

В столбце А записан продукт; в столбце В - содержание в нём жиров; в столбце С - содержание белков; в столбце D - содержание углеводов и в столбце Е - калорийность этого продукта.

Всего в электронную таблицу были занесены данные по 1000 продуктам.

Выполните задание

Откройте файл с данной электронной таблицей (расположение файла Вам сообщат организаторы экзамена). На основании данных, содержащихся в этой таблице, ответьте на два вопроса.

1. Сколько продуктов в таблице содержат меньше 25 г жиров и меньше 25 г углеводов? Запишите число этих продуктов в ячейку Н2 таблицы.

2. Какова средняя калорийность продуктов с содержанием белков больше 20 г? Ответ на этот вопрос запишите в ячейку НЗ таблицы с точностью не менее двух знаков после запятой.

Полученную таблицу необходимо сохранить под именем, указанным организаторами экзамена.

Решение

Существует несколько способов вычисления обоих значений. Для вычисления ответа на первый вопрос проще всего завести промежуточный столбец F, в котором в каждую строку, содержащую запись о продукте, занести 1, если продукт содержит и меньше 25 г жиров и менее 25 г углеводов. Проще всего сделать это, записав соответствующую формулу в ячейку F2. Для электронных таблиц Microsoft Excel формула будет следующей: =ЕСЛИ(И(С2<25;D2<25);1;0). Далее формула копируется во все строки, содержащие данные о продуктах. Общее число строк, в которых содержатся данные о таких продуктах, можно вычислить с помощью формулы, записанной в ячейку Н2: =CYMM(F:F). Она сложит все единицы, записанные в столбец F.

Это решение хорошо тем, что оно не зависит от того, в каком порядке расположены строки в таблицы. В частности, если в процессе выполнения второго задания мы произведем сортировку таблицы с данными, значение не пострадает и останется неизменным.

Для ответа на второй вопрос можно произвести сортировку диапазона столбцов A:F по убыванию значения в поле “Белки, г”. Надо найти последнюю строку, где содержание белков будет больше 20 г и запомнить ее номер. Если воспользоваться файлом данных к примеру задания 19 из данной книги, то номер этой строки будет 130. Тогда формула в ячейке НЗ примет вид: СРЗНАЧ(Е2:Е130)

Для файла данных к примеру задания 19 искомые значения в ячейке Н2: 753, в ячейке Н3: 292,9.

Задание 20

Последнее задание в работе проверяет умение разработки и записи программ для решения конкретной задачи. Задание предлагается в двух видах: по созданию алгоритма для исполнителя Робот или по разработке программы, обрабатывающей последовательность целых чисел. Задание выполняется либо в среде исполнителя Робот (наиболее распространенная среда, поддерживающая исполнителя Робот - “КуМир”), либо в привычной для экзаменующегося среде программирования. Решение проверяется экспертами с помощью наборов обстановок для Робота, соответствующих условию задачи, или с помощью набора тестовых числовых последовательностей.

В отличие от ЕГЭ, задание 20 на ОГЭ выполняется на компьютере, поэтому экзаменующийся имеет возможность отладить программу (алгоритм) и протестировать его на наборе исходных обстановок/последовательностей. Именно поэтому синтаксические ошибки и программные ошибки, мешающие нормальному исполнению программы или не приводящие к нормальному завершению работы программы (приводящие к “зацикливанию” программы), влекут за собой оценку программы в ноль баллов независимо от того, насколько программный код похож на правильное решение. При разработке программы следует обязательно проверить ее правильную работу на нескольких наборах исходных данных.

Оценивается только одно решение - либо задачи 20.1, либо задачи 20.2. Экзаменующийся должен выбрать тот вариант задания, который он собирается выполнить, сосредоточиться на его правильном выполнении и не тратить время и силы на альтернативную задачу.

Правильно выполненное задание оценивается в 2 балла. Один балл ставится за задание работающее не на всех стартовых обстановках/тестовых последовательностях, но работающее на некоторых. Программы, не выдающие результат, завершающиеся аварийно, не завершающиеся вовсе - оцениваются нулем баллов.

Задание 20.1 предваряется описанием исполнителя Робот. Разрешается использовать иной, чем описан в задании, синтаксис языка, если имеется однозначное соответствие между используемыми - командами и описанными в задании. При выполнении задания 20.2 разрешается применять все возможности используемых языка и среды программирования.

Пример 20.1

Исполнитель Робот умеет перемещаться по лабиринту, начерченному на плоскости, разбитой на клетки. Между соседними (по сторонам) клетками может стоять стена, через которую Робот пройти не может.

У Робота есть девять команд. Четыре команды - это команды-приказы:

вверх вниз влево вправо

При выполнении любой из этих команд Робот перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Если Робот получит команду передвижения сквозь стену, то он разрушится.

Также у Робота есть команда закрасить, при которой закрашивается клетка, в которой Робот находится в настоящий момент.

Ещё четыре команды - это команды проверки условий. Эти команды проверяют, свободен ли путь для Робота в каждом из четырёх возможных направлений:

сверху свободно снизу свободно слева свободно справа свободно

Эти команды можно использовать вместе с условием “если”, имеющим следующий вид:

если условие то

последовательность команд

все

Здесь условие - одна из команд проверки условия.

Последовательность команд - это одна или несколько любых команд-приказов.

Например, для передвижения на одну клетку вправо, если справа нет стенки и закрашивания клетки, можно использовать такой алгоритм:

если справа свободно то

вправо

закрасить

все

В одном условии можно использовать несколько команд проверки условий, применяя логические связки и, или, не, например:

если (справа свободно) и (не снизу свободно) то

вправо

все

Для повторения последовательности команд можно использовать цикл “пока”, имеющий следующий вид:

нц пока условие

последовательность команд

кц

Например, для движения вправо, пока это возможно, можно использовать следующий алгоритм:

нц пока справа свободно

вправо

кц

Выполните задание.

На бесконечном поле есть горизонтальная и вертикальная стены. Правый конец горизонтальной Стены соединён с верхним концом вертикальной стены. Длины стен неизвестны. В каждой стене есть ровно один проход, точное место прохода и его ширина неизвестны. Робот находится в клетке, расположенной рядом с вертикальной стеной слева от её нижнего конца.

На рисунке указан один из возможных способов расположения стен и Робота (Робот обозначен буквой “Р”).

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

При исполнении алгоритма Робот не должен разрушиться, выполнение алгоритма должно завершиться. Конечное расположение Робота может быть произвольным.

Алгоритм должен решать задачу для любого допустимого расположения стен и любого расположения и размера проходов внутри стен.

Решение

Следует внимательно прочитать условие и понять, какие особенности обстановки точно известны, а какие могут варьироваться. Точно известно, что Робот слева от идущей вверх стены, в которой есть ровно один разрыв. Стена заканчивается углом, в котором стены расположены сверху и справа. Далее стена уходит влево и где-то заканчивается. В этой стене также есть один разрыв. Длины стен и разрывов неизвестны. Нужно закрашивать клетки непосредственно слева от вертикальной стены и непосредственно под горизонтальной стеной, но не закрашивать клетки рядом с разрывами. Робот первоначально находится в клетке, расположенной рядом с вертикальной стеной слева от её нижнего конца.

Сначала составим описание алгоритма для Робота на естественном языке. Робот должен идти вдоль вертикальной стены вверх, при этом он должен сначала закрашивать клетку, а потом делать шаг вверх. Когда стена справа закончится, он должен делать шаги вверх, не закрашивая клетки. Как только стена справа появится вновь, Робот должен возобновить движение вверх и закрашивание до тех пор, пока не появится стена сверху, то есть Робот окажется в углу. Тогда он начинает движение влево, контролируя наличие стены сверху. Дойдя до разрыва в стене, Робот должен продолжить движение вправо, но прекратить закрашивание, и он должен возобновить закрашивание клеток после того как стена сверху появится вновь. Работа алгоритма заканчивается, когда сверху от Робота становится свободно.

Видно, что движение Робота описывается 6 циклами “пока”: за 3 цикла он доходит до угла и еще за 3 цикла до конца горизонтальной стены.

Вот алгоритм на описанном в задании языке управления Роботом (разработан в среде Кумир):

алг задание20 нач

Его можно проверить на ряде обстановок, отвечающих описанным в задаче условиям, отличающихся различной длиной стен и проходов в них.

Пример 20.2

Напишите программу, которая в последовательности натуральных чисел определяет сумму чисел, кратных 5. Программа получает на вход количество чисел в последовательности, а затем сами числа. В последовательности всегда имеется число, кратное 5.

Количество чисел не превышает 100. Введённые числа не превышают 300.

Программа должна вывести одно число - сумму чисел, кратных 5.

Пример работы программы:

Входные данные	Выходные данные
3	40
15
25
6

Решение

Число, кратное 5, имеет остаток от деления на 5 равный 0. Алгоритм должен объявить целые переменные: s для хранения суммы, N для хранения чисел в последовательности, i для подсчета количества введенных чисел и m для хранения очередного введенного числа. Требуется сначала ввести с клавиатуры значение N, потом инициализировать переменную s значением 0, далее в цикле от 1 до N вводить очередное число, сравнивать остаток от его деления с 0 и в случае равенства увеличивать переменную s на введенное число. После завершения цикла следует напечатать значение s.

Приводим текст программы на алгоритмическом языке:

А	1	Й	11	У	21	Э	31
Б	2	К	12	Ф	22	Ю	32
В	3	Л	13	X	23	Я	33
Г	4	М	14	Ц	24
Д	5	Н	15	Ч	25
Е	6	О	16	ш	26
Ё	7	П	17	Щ	27
Ж	8	Р	18	Ъ	28
3	9	С	19	Ы	29
И	10	Т	20	Ь	30

А	1	Й	11	У	21	Э	31
Б	2	К	12	Ф	22	Ю	32
В	3	Л	13	X	23	Я	33
Г	4	М	14	Ц	24
Д	5	Н	15	Ч	25
Е	6	О	16	ш	26
Ё	7	П	17	Щ	27
Ж	8	Р	18	Ъ	28
3	9	С	19	Ы	29
И	10	Т	20	Ь	30

А	1	Й	11	У	21	Э	31
Б	2	К	12	Ф	22	Ю	32
В	3	Л	13	X	23	Я	33
Г	4	М	14	Ц	24
Д	5	Н	15	Ч	25
Е	6	О	16	ш	26
Ё	7	П	17	Щ	27
Ж	8	Р	18	Ъ	28
3	9	С	19	Ы	29
И	10	Т	20	Ь	30