Стрим #5 ЕГЭ по информатике
Решение с разбором всех заданий (Видео) находится в самом низу страницы!!
Задание 1 тип 11
При регистрации на сервере каждый пользователь получает уникальный персональный код, состоящий из 17 символов, каждый из которых может быть одной из 26 заглавных латинских букв или одной из 10 цифр. При этом в базе данных сервера формируется запись, содержащая этот код и дополнительную информацию о пользователе. Для представления кода используют посимвольное кодирование, все символы кодируют одинаковым минимально возможным количеством битов, а для кода в целом выделяется минимально возможное целое количество байтов. Для хранения данных о 30 пользователях потребовалось 2400 байт.
Сколько байтов выделено для хранения дополнительной информации об одном пользователе? В ответе запишите только целое число — количество байтов.
Решение.
k бит позволяют кодировать 2k символов, поэтому для кодирования 36-символьного алфавита требуется 6 бит (ведь 26=64). Для хранения 17 символов требуется 17*6=102 бит. Минимальное количество байт, вмещающее в себя 102 бит = 13 байт (104 бит).
Если на 30 пользователей понадобилось 2400 байт, то на одного нужно 80 байт. Из них 13 отводится на пароль. Значит, остальные 67 для хранения дополнительных сведений.
Ответ: 67.
Задание 2 тип 11
Автоматическое устройство осуществило перекодировку информационного сообщения на русском языке, первоначально записанного в 16-битном коде Unicode, в 8-битную кодировку КОИ-8. При этом информационное сообщение уменьшилось на 480 бит. Какова длина сообщения в символах?
Решение.
1 символ в коде Unicode кодируется 16-ю битами, 1 символ в коде КОИ-8 — 8-ю битами. Количество символов при перекодировке не меняется, поэтому обозначим его за х.
Составим уравнение:
16х-8х=480
Решая его найдём 8х=480 следовательно, х=60
Задание 3 тип 12
Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:
вверх
вниз
влево
вправо
При выполнении этих команд РОБОТ перемещается на одну клетку соответственно: вверх, вниз, влево, вправо.
Четыре команды проверяют истинность условия отсутствия стены у той клетки, где находится РОБОТ:
сверху свободно
снизу свободно
слева свободно
справа свободно
Цикл
ПОКА <условие> команда
выполняется, пока условие истинно, иначе происходит переход на следующую строку.
Сколько клеток лабиринта соответствуют требованию, что, выполнив предложенную программу, РОБОТ остановится в той же клетке, с которой он начал движение?
НАЧАЛО
ПОКА <слева свободно> вниз
ПОКА <снизу свободно> вправо
ПОКА <справа свободно> вверх
ПОКА <сверху свободно> влево
КОНЕЦ
Решение.
Так как программа заканчивается командой "ПОКА <сверху свободно> влево", для того, чтобы робот остановился в той же клетке, с которой он начал движение, необходимо, чтобы у этой клетки была стенка сверху. Этому условию удовлетворяют все клетки верхней стенки лабиринта и еще пять клеток кроме нее.
Проверим каждую клетку, удовлетворяющую условию. Обратите внимание, что возможны зацикливания, например, если начать движение из клетки Д1 (если нумеровать цифрами сверху вниз, а русскими буквами слева направо).
Ответ: две клетки Г4 и А2.
Правильный ответ: 2
Задание 4 тип 12
Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости, состоит из 8 команд. Четыре команды - это команды-приказы:
вверх
вниз
влево
вправо
При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх вниз влево вправо
Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:
сверху свободно
снизу свободно
слева свободно
справа свободно
Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.
В конструкции
ЕСЛИ условие
ТО команда 1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно)
В конструкциях ПОКА и ЕСЛИ условие может содержать команды проверки, а также слова И, ИЛИ, НЕ, обозначающие логические операции.
Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разрушится и программа прервётся.
Сколько клеток лабиринта соответствуют требованию, что, начав движение в данной клетке и выполнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клетке (клетка F6)?
НАЧАЛО
ПОКА снизу свободно ИЛИ справа свободно
ПОКА снизу свободно
вниз
КОНЕЦ ПОКА
ЕСЛИ справа свободно
ТО
вправо
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦl
Решение.
Один из главных приёмов в решении этой задачи — проверять клетки группами, а не по одной.
При данной программе РОБОТ поступает следующим образом: сперва РОБОТ проверяет, свободна ли клетка справа или снизу от него. Если это так, то РОБОТ переходит к первому действию внутри цикла. В этом цикле пока у нижней стороны клетки, в которой находится РОБОТ, нет стены, он продолжает двигаться вниз. Как только это условие перестанет выполняться, он переходит ко второму действию внутри цикла. Второе действие, заключается в следующем: РОБОТ проверяет, есть ли стена у правой стороны клетки, в которой он находится, и если справа свободно, РОБОТ передвигается на одну клетку вправо. После чего возвращается к началу внешнего цикла.
Проанализировав эту программу, приходим к выводу, что РОБОТ будет двигаться вниз или вправо, пока у него есть такая возможность. РОБОТ при данной программе никогда не разобьётся.
Проверив все клетки по выведенному нами правилу движения РОБОТА выясняем, что число клеток, удовлетворяющих условию задачи, равно 30 (все клетки за исключением E1:F3).
Правильный ответ: 30
Задание 5 тип 16
Ниже на пяти языках программирования записаны две рекурсивные функции: F и G.
Паскаль
function F(n: integer): integer;
begin
if n > 2 then
F := F(n-1) + G(n-2)
else
F := n;
end;
function G(n: integer): integer;
begin
if n > 2 then
G := G(n-1) + F(n-2)
else
G := 3-n;
end;
Чему будет равно значение, вычисленное при выполнении вызова F(6)?
Решение.
Промоделируем работу программы:
F(6) = F(5) + G(4);
F(5) = F(4) + G(3); G(4) = G(3) + F(2);
F(4) = F(3) + G(2); G(3) = G(2) + F(1);
F(3) = F(2) + G(1);
Вычислим:
F(3) = 2 + 2 = 4;
F(4) = 4 + 1 = 5; G(3) = 1 + 1 = 2;
F(5) = 5 + 2 = 7; G(4) = 2 + 2 = 4;
F(6) = 7 + 4 = 11.
Ответ: 11.
Задание 7 тип 17
Рассматривается множество целых чисел, принадлежащих числовому отрезку [8812; 12285], которые делятся на 8 или 19 и не делятся на 4, 9, 14, 16. Найдите количество таких чисел и максимальное из них. В ответе запишите два целых числа без пробелов и других дополнительных символов: сначала количество, затем максимальное число.
Для выполнения этого задания можно написать программу или воспользоваться редактором электронных таблиц.
Решение.
Приведём решение данной задачи на языке Паскаль:
var count, max, i: integer;
begin
max := 0;
count := 0;
for i := 8812 to 12285 do begin
if (i mod 8 = 0) or (i mod 19 = 0) then
if i mod 4 <> 0 then
if i mod 9 <> 0 then
if i mod 14 <> 0 then
if i mod 16 <> 0 then begin
count := count + 1;
if i > max then
max := i;
end;
end;
writeln(count, max);
end.
Ответ: 11712274.
Задание 9 тип 17
Рассматривается множество целых чисел, принадлежащих числовому отрезку [4197; 9182], которые делятся на 5 и не делятся на 6, 10, 13, 16. Найдите количество таких чисел и
максимальное из них. В ответе запишите два целых числа без пробелов и других дополнительных символов: сначала количество, затем максимальное число.
Для выполнения этого задания можно написать программу или воспользоваться редактором электронных таблиц.
Решение.
Приведём решение данной задачи на языке Паскаль:
var count, max, i: integer;
begin
max := 0;
count := 0;
for i := 4197 to 9182 do begin
if i mod 5 = 0 then
if i mod 6 <> 0 then
if i mod 10 <> 0 then
if i mod 13 <> 0 then
if i mod 16 <> 0 then begin
count := count + 1;
if i > max then
max := i;
end;
end;
writeln(count, max);
end.
Ответ: 4599175.
