какое минимальное количество бит потребуется для хранения числа
Урок посвящён 11 заданию из ЕГЭ по информатике нового формата 2021. Проанализируем основные примеры и научимся решать это задание!
В 11 задании из ЕГЭ по информатике часто даются задачи на умение работать с количеством информации.
Приступим к делу! Раньше это задание было под номером тринадцать.
Задача (Демонстрационный вариант ЕГЭ по информатике, 2018)
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 10 символов. В качестве символов используют прописные буквы латинского алфавита, т.е. 26 различных символов. В базе данных для хранения каждого пароля отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Определите объём памяти (в байтах), необходимый для хранения данных о 50 пользователях. В ответе запишите только целое число – количество байт.
У каждого пользователя есть пароль, состоящий из 10 символов. Это значит, длина пароля 10 символов!
И в каждую ячейку мы может выбрать символ из 26 букв!
Здесь важно различать длину пароля и количество символов из которых пользователь выбирает для каждой ячейки пароля.
Теперь нужно определить: сколько бит занимает одна ячейка (1 символ пароля!).
Когда речь идёт о количестве бит, применяем формулу, которую мы использовали в 7 задании из ЕГЭ по информатике. Там мы кодировали цвета для одного пикселя, а здесь нужно закодировать 26 букв для одного поля пароля.
Целого числа нету для i (количества бит), чтобы равенство было верным. Значит берём столько количество бит, сколько точно будет достаточно, чтобы закодировать 26 букв (символов).
Получаем одна ячейка (одно поле) пароля занимаем 5 бит! А в пароле их 10! Значит, весь пароль будет занимать:
Vпароля = 5 бит * 10 символов = 50 бит (в одном пароле!)
В условии сказано: для хранения каждого пароля отведено одинаковое и минимально возможное целое число байт. Это означает, что мы не может выделять память по одному биту. Память выделяется блоками по 8 бит (по одному байту).
Если взять 7 блоков по 8 бит (1 байту), то нам хватит этого на один пароль.
7 блоков (байт) * 8 бит = 56 бит > 50 бит
Таким образом, на 1 пароль потребуется 7 байт!
Тогда на 50 пользователей потребуется:
50 пользователей * 7 байт = 350 байт (для 50 пользователей).
Ответ: 350
Разберём задачу, которая была на реальном экзамене в Москве
Задача (ЕГЭ по информатике, 2020, Москва)
Здесь длина пароля составляет 11 символов!
Найдём сколько бит занимает одна ячейка пароля.
Найдём сколько бит нужно на весь пароль.
Vпароля = 6 бит * 11 символов = 66 бит (в одном пароле!)
Теперь найдём, а сколько байт нужно на 1 пароль:
9 * 8 бит = 72 бит > 66 бит
Следовательно, 9 байт достаточно, чтобы покрыть 66 бит на 1 пароль.
Сказано, что для 30 сотрудников выделено 750 байт. Подсчитаем, сколько байт будет выделено на одного сотрудника.
Vпользователя = 750 байт / 30 = 25 байт (приходится на одного пользователя)
Мы выяснили, что на пароль из этих 25 байт потребуется 9 байт. Тогда на дополнительную информацию о каждом пользователе потребуется:
Ещё один важный пример из запасов тренировочных задач ЕГЭ по информатике.
В велокроссе участвуют 48 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена.Какой объём памяти будет использован устройством, когда все спортсмены прошли промежуточный финиш? (Ответ дайте в байтах.)
Узнаем сколько бит потребуется выделить на каждого спортсмена, чтобы была возможность записать любой номер от 1 до 48.
На рисунке показано, как может происходить кодирование чисел. Например, для двух номеров потребуется 1 бит (2 1 = 2), для четырёх номеров потребуется два бита (2 2 = 4). Нам нужно закодировать 48 чисел! Причём для каждого участника отведено одинаковое количество бит!
Получается 6 бит потребуется для того, чтобы была возможность записать любой номер от 1 до 48 для каждого спортсмена. Если взять пять бит, то мы будем иметь возможность записать номера только от 1 до 2 5 = 32 для каждого спортсмена (этого не хватает).
Т.к. все участники пересекли финиш, а на каждого участника выделено по 6 бит, то получается:
6 бит * 48 = 288 бит = 36 байт
Ответ: 36
Найдём сколько бит потребуется для кодирования 4-х букв.
N = 2 i = 2 4 бита = 16 > 12
4 бита хватит для кодирования 12 букв. Всего таких ячейки 4! Поэтому в одном номере на все буквы уйдёт 4 * 4 бита = 16 бит.
Найдём сколько бит потребуется на кодирование 3 ячеек, где находятся цифры.
Для кодирования одной ячейки, где находится цифра, потребуется 3 бита.
Все цифры в одном номере будут закодированы 3 бита * 3 = 9 битами.
Всего на один номер уйдёт 16 бит + 9 бит = 25 бит.
Найдём сколько байт потребуется для кодирования одного номера.
4 * 8 бит (1 байт) = 32 бита > 25 бит
4-х байт достаточно, чтобы закодировать 25 бит. Если взять 3 байта, то 3 * 8 бит (1 байт) = 24 бита. Этого будет не достаточно.
Найдём количество байт, которое нужно для кодирования 160 автомобилей
160 автомобилей * 4 байта = 640 байт
Метеорологическая станция ведет наблюдение за влажностью воздуха. Результатом одного наблюдения является целое число от 0 до 100%, записываемое при помощи минимально возможного количества бит. Станция сделала 800 измерений. Определите информационный объем результатов наблюдений. (Ответ дайте в байтах.)
Здесь, нужно закодировать сто одно число (от 0 до 100). Ситуация похоже на ту, где мы кодировали номера спортсменов.
Получается, что 7 бит потребуется, чтобы полностью закодировать 101 число.
Всего было сделано 800 таких измерений
800 * 7 бит = 5600 бит = 700 байт
Ответ: 700
На этом всё! Удачи при решении 11 задания на ЕГЭ по информатике!
Какое минимальное количество бит потребуется для хранения числа
Каждый объект, зарегистрированный в информационной системе, получает уникальный код из 9 символов, каждый из которых может быть одной из 26 заглавных или строчных латинских букв. Для представления кода используют посимвольное кодирование, все символы кодируют одинаковым минимально возможным количеством битов, а для кода в целом выделяется минимально возможное целое количество байтов. Кроме того, для каждого объекта в системе выделен одинаковый объём памяти для хранения содержательной информации. Для хранения данных (код и содержательная информация) о 50 объектах потребовалось 2500 байт.
Сколько байтов выделено для хранения содержательной информации об одном объекте? В ответе запишите только целое число — количество байтов.
Заметим, что k бит позволяют кодировать 2 k символов, поэтому для кодирования 52-символьного алфавита требуется 6 бит (ведь 
). Для хранения 9 символов требуется 
бит. Минимальное количество байт, вмещающее в себя 54 бита = 7 байт (56 бит).
Поскольку для хранения данных (код и содержательная информация) о 50 объектах потребовалось 2500 байт, для хранения данных об одном пользователе потребуется 2500 : 50 = 50 байт. Для хранения содержательной информации об одном пользователе используется 50 − 7 = 43 байта.
Вычисление битов, необходимых для хранения десятичного числа
Это домашний вопрос, с которым я застрял.
Рассмотрим целочисленное представление без знака. Сколько бит потребуется для хранения десятичного числа, содержащего:
Я знаю, что диапазон целого числа без знака будет от 0 до 2^n, но я не понимаю, как от этого зависит количество битов, необходимых для представления числа. Пожалуйста, помогите мне.
11 ответов
Ну, вам просто нужно рассчитать диапазон для каждого случая и найти наименьшую степень 2, которая выше этого диапазона.
Редактировать: в основном вам нужно найти количество возможных чисел с количеством цифр, которые у вас есть, а затем выяснить, какое количество цифр (в другой базе, в данном случае в двоичной базе 2) имеет как минимум те же возможные числа, что и цифра. в десятичном.
Для подсчета количества возможностей дано количество цифр: possibilities=base^ndigits
Итак, если у вас есть 3 цифры в десятичном виде (основание 10), у вас есть 10^3=1000 возможности. Затем вы должны найти количество цифр в двоичном виде (биты, основание 2), чтобы число возможностей было не менее 1000, что в данном случае 2^10=1024 (9 цифр недостаточно, потому что 2^9=512 что меньше 1000).
Если вы обобщите это, у вас есть: 2^nbits=possibilities nbits=log2(possibilities)
Который применяется к я) дает: log2(1000)=9.97 и так как число бит должно быть целым числом, вы должны округлить его до 10.
log e (n) / log e (2)
От 0 до n используйте n + 1 в приведенной выше формуле (есть n + 1 целое число).
На вашем калькуляторе log e может быть просто помечен как log или ln (натуральный логарифм).
Взяв логарифм по основанию 2 обеих сторон последнего выражения, получим:
Поскольку мы хотим, чтобы наименьшее целое число N, удовлетворяющее последнему отношению, нашло N, найдите log b n / log2 и возьмите потолок.
В последнем выражении любая основа подходит для логарифмов, если обе базы одинаковы. Здесь удобно, поскольку нас интересует случай, когда b = 10, использовать логарифмы с основанием 10, используя преимущество log1010 n == n.
Для n = 3:
Для n = 4:
Для n = 6:
И вообще, для n десятичных цифр:
Для десятичной системы счисления R=9, поэтому мы решаем 9=2^n, ответ равен 3,17 бита на десятичную цифру. Таким образом, для трехзначного числа потребуется 9,51 бит или 10. Для 1000-значного числа требуется 3170 бит
Продолжайте делить число на 2, пока не получите коэффициент 0.
Это просто потому, что pow(2, nBits) немного больше N.
Чтобы включить отрицательные числа, вы можете добавить дополнительный бит, чтобы указать знак.
Для двоичного числа из n цифр максимальное десятичное значение, которое оно может содержать, будет
Возьмем случай, когда вам нужны только три цифры, т.е. ваш случай 1. Мы видим, что требования
Применяя журнал для обеих сторон,
n = 9,964 (приблизительно).
Принимая значение ceil n, так как 9.964 не может быть действительным числом цифр, мы получаем n = 10.
Здесь много ответов, но я добавлю свой подход, так как я нашел этот пост, работая над той же проблемой.
Начнем с того, что мы знаем здесь, число от 0 до 16.
глядя на перерывы, он показывает эту таблицу
Итак, как нам теперь вычислить шаблон?
Помните, что log base 2 (n) = log base 10 (n) / log base 10 (2)
Теперь желаемый результат соответствует первой таблице. Обратите внимание, что некоторые значения также являются особыми случаями. 0 и любое число, которое является степенью 2. Эти значения не изменяются при применении потолка, поэтому вы должны добавить 1, чтобы получить минимальную длину поля битов.
Для учета особых случаев добавьте один к входу. Результирующий код, реализованный на python:
Пусть его требуемый бит n затем 2^n=(основа)^ цифра, а затем взять журнал и считать №. для п
В качестве базового примера, давайте предположим, что мы хотели сохранить однозначное основание из десяти чисел и хотели узнать, сколько битов потребуется. Наибольшее однозначное число из десяти основных чисел равно 9, поэтому нам нужно преобразовать его в двоичный файл. Это дает 1001, который имеет в общей сложности 4 бита. Этот же пример может быть применен к двузначному числу (с максимальным значением 99, которое преобразуется в 1100011). Чтобы найти n цифр, вам, вероятно, нужно решить другие и найти шаблон.
Чтобы преобразовать значения в двоичные, вы несколько раз делитесь на два, пока не получите коэффициент 0 (и все ваши остатки будут равны 0 или 1). Затем вы меняете порядок остатков, чтобы получить число в двоичном виде.
Пример: 13 в двоичном.
Надеюсь, это поможет.
Предполагая, что вопрос заключается в том, какие минимальные биты необходимы для хранения
Мой подход к этому вопросу будет:
Эту проблему можно решить таким образом, рекурсивно разделив 999 на 2. Тем не менее, проще использовать силу математики, чтобы помочь нам. По сути, мы решаем n для уравнения ниже:
Вам понадобится 10 бит для хранения трехзначного числа.
Используйте аналогичный подход для решения других подвопросов!
Количество информации (страница 3)
Каждая ячейка памяти компьютера может принимать 9 значений. Для хранения некоторой величины использовали 3 ячейки памяти. Сколько различных значений может принимать эта величина?
Если одной ячейкой памяти можно закодировать \(9^1\) различных значения, то 3 ячейками памяти можно закодировать \(9^3 = 729\) различных значения.
Прямоугольная клетчатая доска, содержащая результаты соревнований, состоит из 20 столбцов и 7 строк. Какое минимальное количество бит потребуется для кодирования одной клетки этой таблицы?
Доска состоит из \(20 \cdot 7 = 140\) клеток. Бит может принимать 2 значения, для кодирования таблицы потребуется такое количество бит, чтобы можно было закодировать 140 символов.
7 бит: \(2^7 = 128 — не подходит, слишком мало символов можно закодировать.
8 бит: \(2^8 = 256 \geq 140\) — подходит, можно закодировать достаточное количество символов.
Значит для кодирования таблицы потребуется 8 бит.
Прямоугольная клетчатая доска, содержащая результаты исследования, состоит из 75 столбцов и 30 строк. Какое минимальное количество бит потребуется для кодирования одной клетки этой таблицы?
Доска состоит из \(75 \cdot 30 = 2250\) клеток. Бит может принимать 2 значения, для кодирования таблицы потребуется такое количество бит, чтобы можно было закодировать 2250 символов.
11 бит: \(2^ <11>= 2048 — не подходит, слишком мало символов можно закодировать.
12 бит: \(2^ <12>= 4096 \geq 2250\) — подходит, можно закодировать достаточное количество символов.
Значит для кодирования таблицы потребуется 12 бит.
Прямоугольная клетчатая доска с участниками семинара состоит из 120 столбцов и 80 строк. Какое минимальное количество бит потребуется для кодирования одной клетки этой таблицы?
Доска состоит из \(120 \cdot 80 = 9600\) клеток. Бит может принимать 2 значения, для кодирования таблицы потребуется такое количество бит, чтобы можно было закодировать 9600 символов.
13 бит: \(2^ <13>= 8192 — не подходит, слишком мало символов можно закодировать.
14 бит: \(2^ <14>= 16384 \geq 9600\) — подходит, можно закодировать достаточное количество символов.
Значит для кодирования таблицы потребуется 14 бит.
Какое минимальное количество бит потребуется для хранения числа
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 25 символов и содержащий только символы из 7-символьного набора: С, Д, А, М, Е, Г, Э. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей. Для хранения сведений о 50 пользователях потребовалось 1200 байт.
Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число – количество байт.
Согласно условию, в пароле могут быть использованы 7 символов. Известно, что с помощью N бит можно закодировать 2 N различных вариантов. Поскольку 2 3 = 8, то для записи каждого из 7 символов необходимо 3 бита.
Для хранения всех 25 символов пароля нужно 3 · 25 = 75 бит, а т. к. для записи используется целое число байт, то берём ближайшее не меньшее значение, кратное восьми, это число 80 = 10 · 8 бит (10 байт).
Для хранения всех сведений о 50 пользователях потребовалось 1200 байт. Для хранения паролей 50 пользователей используется 50 · 10 = 500 байт. Значит, для хранения дополнительных сведений об одном пользователе используется 700 : 50 = 14 байт.