Решение задач 1 ЕГЭ по информатике 2015 года

Рассмотрим задачу №1 из демоверсии  ФИПИ 2015 года:

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 0; Б – 100; В – 1010; Г – 111; Д – 110.Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким из указанных способов это можно сделать?
1) для буквы В – 101
2) это невозможно
3) для буквы В – 010
4) для буквы Б – 10

Давайте проанализируем текст задачи. Итак, нам известно, что используется неравномерный двоичный код. Что это такое? На самом деле все очень просто:

равномерное кодирование — каждый символ кодируется кодами равной длины
неравномерное кодирование — разные символы могут кодироваться кодами разной длины

Например, если у нас есть три символа А, Б, В и закодированы они так:

  • А — 010
  • Б — 011
  • В — 111

, то это равномерное кодирование, так как длина кода одинаковая. Если же эти же символы мы закодируем вот так:

  • А — 01
  • Б — 110
  • В — 1011

, то получим неравномерное кодирование.

Кроме этого, нам необходимо знать и понимать условие Фано

Никакое кодовое слово не может быть началом другого кодового слова

Также существует обратное условие Фано

Никакое кодовое слово не является окончанием другого кодового слова
Чтобы однозначно декодировать сообщение, достаточно того, чтобы условие Фано (или обратное условие) выполнялось.

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

Рассмотрим первый вариант ответа. Если мы для буквы В сократим код до 101, то условие Фано нарушено не будет. Действительно, с кода 101 не начинается ни один из четырех оставшихся кодов для А, Б, Г и Д и все коды различны.

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

Третий вариант не подходит, так как в этом случае код буквы В — 010 будет начинаться с 0, а 0 — это код буквы А. Получается, что это нарушает условие Фано.

Вариант 4 тоже не подходит. В этом случае код буквы Б — 10 будет являться началом для кода буквы В, а это нарушение условия Фано.

Правильный ответ: 1.

 

 

Для успешного решения задач типа А1 ЕГЭ по информатике рекомендую ознакомиться со статьями “Системы счисления” и “Перевод чисел из двоичной системы счисления в десятичную”. Для контроля правильности перевода удобно использовать “Скрипт для перевода числа из десятичной системы счисления в любую другую”.

Задачи А1 предполагают проверку знаний  о  системах  счисления  и  двоичном  представлении информации в памяти компьютера.

Рассмотрим решение задачи А1 из демоверсии ЕГЭ 2012.

Сколько единиц в двоичной записи числа 1025?
1)   1
2)   2
3)   10
4)   11

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

image

Как видно, в полученном двоичном числе содержится 2 единицы.

Второй способ решения данной задачи рассчитан на тех, кто хорошо знает степени числа 2. Если посмотреть на число 1025 внимательно, можно заметить, что 1025=1024+1. Число 1024 – это 210. Отсюда следует, что 1025=210+1.

Если посмотреть как выглядят степени числа 2 записанные в двоичной системе счисления, то нетрудно представить число 1024 в двоичной системе счисления.

21=210=102

22=410=1002

23=810=10002

24=1610=100002

25=3210=1000002

…

210=102410=100000000002

Прибавив к получившемуся числу единицу получим число 100000000012, которое содержит 2 единицы.

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

Возьмем для примера число 73 и узнаем сколько единиц в его двоичной записи.

73=64+8+1=26+23+20. Так как слагаемых у нас получилось три, значит и единиц в двоичной записи числа 73 будет тоже 3.

Решение задачи А1 демонстрационной версии ЕГЭ 2013:

Сколько единиц в двоичной записи десятичного числа 255?

1) 1        2) 2        3) 7        4) 8

Первый способ:

Для успешного решения данной задачи необходимо знать, что 256 это 2 в восьмой степени или 10000 0000 в двоичной системе счисления — 256=28=1000000002. Соответственно, 255 — это 11111111 в двоичной системе счисления — 25510=111111112. Правильный ответ — 4 (8 единиц).

Второй способ:

Этот способ заключается в переводе числа 255 из десятичной системы счисления в двоичную и подсчете единиц:

 

Как видим, количество единиц восемь. Правильный ответ 4.

Автор: