Банк заданий к ЕГЭ по информатике

1

2

3

4

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

5

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

6

В некоторой стране автомобильный номер состоит из 7 символов. В качестве символов используют 18 различных букв и десятичные цифры в любом порядке.

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

Определите объем памяти, отводимый этой программой для записи 60 номеров.

7

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

F(n) = 1 при n = 1;

F(n) = n + F(n − 1), если n — чётно;

F(n) = 2 × F(n − 2), если n 1 и при этом n — нечётно.

Чему равно значение функции F(26)?

88

Рассматривается множество целых чисел, принадлежащих числовому отрезку [7525; 13486], которые делятся на 7 и не делятся на 6, 9, 14, 21. Найдите количество таких чисел и минимальное из них. В ответе запишите два целых числа без пробелов и других дополнительных символов: сначала количество, затем минимальное число.

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

9

Найдите наименьшее возможное число x, у которого произведение чётных цифр младшего и старшего разрядов равно 12

10

11

12

1. Логика и алгоритмика

Решение:

1шаг (x∧z) ∨ (x∧¬y∧¬z) = x ∧ (z∨¬y∧¬z) = x ∧ (z∨¬y) ∧ (z∨¬z) = x ∧ (¬y∨z)

2 шаг – логическая операция И: истина будет тогда, когда все множители истинны. x = 1 и ¬y ∨ z = 1

По таблице переменная 2 везде = 1 ⇒ x. Для получения 1 в выражении z ∨ ¬y переменная 1 – y, переменная 3 – z. 1) ¬0 ∨ 0 = 1∨0 = 1 2) ¬0 ∨ 1 = 1∨1 = 1 3) ¬1 ∨ 1 = 0∨1 = 1

Ответ: yxz

Решение:

xÙØyÙ(ØzÚw)=1

x=1, Øy=1, ØzÚw=1

По таблице: переменная 3 – х, переменная 2 – y. Остаётся определить переменные 1 и 4 по уравнению ØzÚw=1: переменная 1 – z, переменная 4 – w.

Ø0 Ú 0 = 1

Ø0 Ú 1 = 1

Ø1 Ú 1 = 1

Ответ: zyxw

2 Информация и ее кодирование

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

По условию, код Морзе может содержать 5 или 6 символов. Каждое количество символов даст нам уникальный набор различных комбинаций, которые не будут пересекаться в силу того, что они будут иметь различное количество символов. Так, комбинация 11101 и комбинация 011101 будут различными, хотя и являются одним и тем же по значению числом.

Значит, всего различных комбинаций будет:

2⁵+2⁶=32+64=96

Ответ: 96.

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

Всего десятичных цифр 10 (с 0 до 9). Следующее после 10-ти число, являющееся целой степенью 2-х – число 16. Это означает, что нам нужно минимально 4 разряда (4 бита), чтобы закодировать все десятичные цифры, поскольку 2⁴=16, а 2³=8 (что недостаточно).

Информационный объём сообщения из 150 символов равен:

N=150*4 бит = 600 бит.

Ответ: 600 бит.

В некоторой стране автомобильный номер состоит из 7 символов. В качестве символов используют 18 различных букв и десятичные цифры в любом порядке.

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

Определите объем памяти, отводимый этой программой для записи 60 номеров.

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

Всего используют 18 букв + 10 десятичных цифр = 28 символов. Для кодирования 28 символов необходимо минимально 5 бит (2⁵=32). Поскольку таких символов в номере 7, значит, каждый номер автомобиля в программе и при хранении в файле занимает 5*7=35 бит. По условию, номер хранится в виде минимально возможного целого количества байт: округление в большую сторону(35бит:8)=5 байт, Тогда для записи 60-ти номеров потребуется 5 байт*60=300 байт.

Ответ: 300 байт.

3 Программирование

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

F(n) = 1 при n = 1;

F(n) = n + F(n − 1), если n — чётно;

F(n) = 2 × F(n − 2), если n 1 и при этом n — нечётно.

Чему равно значение функции F(26)?

var n: longint;

function F(n: longint): longint;

begin

if n = 1

then F := 1

else if ((n mod 2) = 0)

then F := n + F(n - 1)

else if (((n mod 2) = 1) and (n 1))

then F := 2 * F(n - 2);

end;

begin

n := F(26);

writeln(n);

end.

Значение функции от нечётных n являются значениями степеней двойки:  F(1) = 1, F(3) = 2, F(5) = 4 и т. д. Значит, F(25) = 4096. Тогда F(26) = 26 + 4096 = 4122.

Рассматривается множество целых чисел, принадлежащих числовому отрезку [7525; 13486], которые делятся на 7 и не делятся на 6, 9, 14, 21. Найдите количество таких чисел и минимальное из них. В ответе запишите два целых числа без пробелов и других дополнительных символов: сначала количество, затем минимальное число.

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

var count, min, i: integer;

begin

min := 20000;

count := 0;

for i := 7525 to 13486 do begin

if i mod 7 = 0 then

if i mod 6 0 then

if i mod 9 0 then

if i mod 14 0 then

if i mod 21 0 then begin

count := count + 1;

if i min then min := i;

end;

end;

writeln(count, min);

end.

Ответ: 2847525.

Найдите наименьшее возможное число x, у которого произведение чётных цифр младшего и старшего разрядов равно 12

Если число x нечётное, то к числу a прибавляется остаток от деления числа x на 12. Следовательно, поскольку необходимо найти наименьшее число x, во втором разряде числа будет стоять цифра 3.

Необходимо получить двенадцатиричное число, у которого произведение чётных цифр младшего и старшего разрядов равно 12. Следовательно, поскольку необходимо найти наименьшее возможное число x, у которого произведение чётных цифр младшего и старшего разрядов равно 12, число x должно выглядеть так 236₁₂ = 330₁₀.

Ответ: 330.

4 Элементы теории алгоритмов

Решение.

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

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

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

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Б + Г = 4

Е = В = 4

Ж = В + Е = 4 + 4 = 8

З = 0 (поскольку в З не ведёт ни одна дорога из В)

И = Е + Ж = 4 + 8 = 12

К = Л = И =12

М = К + И + Л = 36

Ответ: 36.

Используя данные таблиц, вычислим возраст родителей (первым идёт ID ребёнка (детей), вторым идут данные родителей).

ID 212: мать Грищенко Е.П., ID 182, отец Грищенко А.В, ID 127 — подходит.

ID 148: мать Грищенко Н.Н., ID 243, отец Грищенко И.А., ID 212 — подходит.

ID 314 и ID 412: мать Седых А.Н., ID 830, отец Клейн А.Б, ID 254 — не подходит, поскольку отец младше матери.

ID 243 и ID 830: мать Панько О.А., ID 543, отец Седых Н.Н., ID 849 — подходят (двое детей).

ID 545: мать Петрова А.Е., ID 750, отец Петров В.И., ID 544 — не подходит, поскольку отец старше матери меньше, чем на 2 года.

Таким образом, у четырёх детей отец старше матери более чем на 2 года.

Ответ: 4.

Решение.

Варианты маршрутов:

 A-B-C-E-F.

Длина маршрута 4 + 6 + 4 + 5 = 19

 A-B-D-E-F.

длина маршрута 4 + 3 + 2 + 5 = 14

 A-B-E-F.

Длина маршрута 4 + 6 + 5 = 15

 Кратчайший путь равен 14.