ГлавнаяИнформатикаКак решатьВ марафоне участвуют бегуны, специальное устройство регистрирует прохождение

В марафоне участвуют бегуны, специальное устройство регистрирует прохождение

2016-06-21 11:54:38

Формулировка задания: В марафоне участвуют N бегунов. Специальное устройство регистрирует прохождение каждым из спортсменов промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Какой объём памяти будет использован устройством, когда промежуточный финиш прошли K бегунов?

Задание входит в ЕГЭ по информатике для 11 класса под номером 13 (Вычисление количества информации).

Рассмотрим, как решаются подобные задания на примере.

Пример задания:

В марафоне участвуют 178 бегунов. Специальное устройство регистрирует прохождение каждым из спортсменов промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Какой объём памяти будет использован устройством, когда промежуточный финиш прошли 80 бегунов?

  1. 80 байт
  2. 70 байт
  3. 80 бит
  4. 70 бит

Решение:

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

2k = N

где k – информационный вес символа в битах, а N – количество информации. Нужно подобрать такое минимальное k, чтобы можно было закодировать номер каждого бегуна из 178. То есть:

2k ≥ 178


при k = 7:

27 = 128


при k = 8:

28 = 256

7 бит не хватит для кодирования 178 номеров бегунов, а 8 как раз достаточно.

Осталось вычислить, какой объём памяти будет использован устройством, когда промежуточный финиш прошли 80 бегунов:

80 ⋅ 8 = 640 бит

Такого ответа нет, поэтому переведем биты в байты:

640 / 8 = 80 байт

Таким образом, правильным является ответ номер 1.

Ответ: 1

Наверх