Определите объем памяти в байтах отводимый этой программой для записи 25 паролей

Обновлено: 05.07.2024

Подготовка школьников к сдаче ЕГЭ по предмету "Информатика". Уровень знаний учащихся может быть любым. Представлены такие разделы информатики, знание которых необходимо для сдачи экзамена: системы счисления, алгебра логики, программирование,кодирование информации, компьютерные сети, электронные таблицы (Excel), базы данных, графы, файловая система организации данных. На данный момент теоретический материал представлен для четырех разделов информатики: для систем счисления, алгебры логики, программирования и кодирования информации.

Для поиска задания по году и номеру используйте таблицу:

Год	Задание
Год	тип "A"	тип "B"	тип "C"
2013	A1, A2, A3, A4, A5, A6,A7, A8, A9, A10, A11, A12, A13	B1, B2, B3, B4, B5, B6, B7, B8, B9, B10, B11, B12, B13, B14, B15	C1, C2, C3, C4
2012	A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13	B1, B2, B3, B4, B5, B6, B7, B8, B9, B10, B11, B12, B13, B14, B15	C1, C2, C3, C4
2011	A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18	B1, B2, B3, B4, B5, B6, B7, B8, B9, B10	C1, C2, C3, C4
2010	A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18	B1, B2, B3, B4, B5, B6, B7, B8, B9, B10	C1, C2, C3, C4
2009	A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18	B1, B2, B3, B4, B5, B6, B7, B8, B9, B10	C1, C2, C3, C4
2008	A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19, A20	B1, B2, B3, B4, B5, B6, B7, B8	C1, C2, C3, C4
2007	A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19, A20	B1, B2, B3, B4, B5, B6, B7, B8	C1, C2, C3, C4
2006	A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19, A20	B1, B2, B3, B4, B5, B6, B7, B8	C1, C2, C3, C4
2005	A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19, A20, A21, A22, A23, A24	B1, B2, B3, B4, B5, B6, B7, B8	C1, C2, C3, C4, C5
2004	A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19, A20, A21, A22, A23, A24, A25, A26, A27, A28, A29, A30, A31, A32	B1, B2, B3	C1, C2, C3, C4, C5

В таблице ниже представлено соответствие задач из ЕГЭ рассмотренным разделам информатики.

Каждый пользователь сети обладает паролем вида XXYYYXZ, где X — строчная буква английского алфавита, Y —цифра 0, 1, · · · , 9 и Z — либо 0, либо 1. Кодирование паролей осуществляется посимвольно. Каждый из символов X, Y и Z кодируется минимально возможным количеством бит, а каждый пароль занимает одинаковое целое число байт. Определите объём памяти (в байтах), необходимый для хранения 18 паролей. В ответе запишите только число, слово «байт» писать не нужно.

Решение

Всего три строчных буквы в пароле (X) и на их кодирование потребуется: всего 26 букв, значит на одну букву 5 бит, а на три буквы 15 бит;
Всего три цифры в пароле (Y) и на их кодирование потребуется: всего 10 цифр, значит на одну цифру 4 бита, а на три цифры 12 бит;
На конце пароля символ Z, на кодирование которого потребуется 1 бит, поскольку всего 2 различных значения.
Итого 15+12+1=28 бит или 28/4=3.5=4 байта. На 18 паролей: 18 * 4 = 72

Задача 2

В книгохранилище специальное устройство каждый час записывает время замера (в часах—от 0 до 23), показания относительной влажности (от 48% до 62%) и температуры воздуха (от 13 ◦C до 22 ◦C). Для записи каждого из трёх показателей используется минимально возможное количество бит, одинаковое для всех показателей одного типа.

Решение

На запись часов потребуется 5 бит, поскольку всего 24 различных значения
На запись влажности потребуется 4 бита, поскольку всего 15 различных значений
На запись температуры потребуется 4 бита, поскольку всего 10 различных значений
Итого: 5+4+4=13 бит на запись одного замера. На 30 замеров = 30*13=390 бит

Задача 3

В соревнованиях по тяжёлой атлетике результат по сумме двух упражнений может принимать целочисленное значение от 210 кг до 240 кг. Специальное устройство регистрирует результат каждого участника, записывая его номер от 1 до 120 (с использованием минимально возможного количества бит) и результат спортсмена по сумме двух упражнений (также с использованием минимально возможного количества бит).

Решение

Для кодирования числа от 210 до 240, то есть одного из 30 чисел потребуется 5 бит.
Номер участника представляет из себя одно из 120 чисел, значит на запись номера потребуется 7 бит.
Запись об одном спортсмене -это его номер и информация о двух упражнениях, то есть $7 + 5 = 12 $ бит
Информация о 120 спортсменах - это $120 * 12 = 1440$ бит

Задача 4

В некоторой стране автомобильный номер длиной в 5 символов составляют из заглавных букв (всего используется 24 различные буквы) и десятичных цифр, записанных в любом порядке. Каждый такой номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование: каждый символ кодируется одинаковым и минимально возможным количеством бит). Определите объём памяти (в байтах), отводимый этой программой для записи 40 номеров.

Решение

Для кодирования 24 различных букв и 10 цифр потребуется 6 бит.
Для хранения всего номера: 5 * 6 = 30 бит или 4 байта, поскольку записывается минимально возможным и одинаковым целым количеством байт
Тогда для записи 40 номеров: 40 * 4 = 160 байт

Задача 5

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

Сколько байт потребуется для хранения данных о 80 пользователях? В ответе запишите только целое число—количество байт.

Решение

Пароль составляется из набора, содержащего 22+10+9=41 символа, на кодирование которых потребуется 6 бит, значит на кодирование пароля потребуется 7 * 6 = 42 бита или 6 байт (42 / 8 = 5.25)
Тогда информация о пользователе (пароль + доп.сведения) будет весить: 6 + 4 = 10 байт
Информация о 80 пользователях будет весить 80*10 = 800 байт

Задача 6

Идентификационный номер состоит из 8 символов. В качестве первого символа используют 26 различных букв, остальные символы — десятичные цифры (пример номера Z1234567). Каждый такой номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байтов, при этом для первого символа отводится один байт, а каждая цифра кодируется одинаковым, минимально возможным количеством бит. Определите объём памяти (в байтах), отводимый этой программой для записи 50 номеров.

Решение

Для кодирования каждой цифры необходимо 4 бита. Следовательно, для кодирования 7-ми цифр потребуется 4 · 7 = 28 бит. Определим минимальное количество байтов для кодирования этих цифр: 28/8 = 3,5. Следовательно, необходимо 4 байта.

Так как ещё один байт требуется для кодирования первого символа, то для одного номера необходимо 4 + 1 = 5 байтов. Значит, 50 номеров займут 5 · 50 = 250 байт.

Задача 7

В некоторой стране автомобильный номер длиной 8 символов составляют из заглавных букв (всего используется 20 различных букв) и десятичных цифр, записанных в любом порядке. Каждый такой номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование: каждый символ кодируется одинаковым и минимально возможным количеством бит). Определите объём памяти (в байтах), отводимый этой программой для записи 30 номеров.

Решение

Найдём наименьшее количество бит, которым можно закодировать не менее 30 символов: 20 различных букв и 10 десятичных цифр. Для этого найдём такое наименьшее натуральное число N, при котором 2 N ≥ 30. Так как 2 4 < 30 < 2 5 , то минимальное количество бит, необходимое для кодирования 30 символов, равно 5. Значит, для кодирования одного символа требуется 5 бит. Номер состоит из 8 символов. Для его кодирования потребуется 5 ∗ 8 = 40 бит. Поскольку номер кодируется минимально возможным количеством байт, то для его кодирования используют 5 байт. Следовательно, для 30 номеров отводится 5 ∗ 30 = 150 байт.

Задача 8

Запись для каждого пользователя при регистрации состоит из логина и пароля. Логин состоит из 12 символов, которые пользователь придумывает сам из 14 фиксированных строчных букв латинского алфавита и 6 цифр. Каждый такой логин в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством бит). Далее к логину каждого пользователя дописывается пароль, автоматически сгенерированный системой.

Для хранения сведений о 100 пользователях потребовалось 1100 байт. Сколько байт выделено для хранения пароля одного пользователя? В ответе запишите только целое число—количество байт.

Решение

Определим минимальное количество бит, необходимое для кодирования логина пользователя. n битами можно закодировать 2 n различных значений. По условию задачи для логина используется 14 фиксированных строчных букв латинского алфавита и 6 цифр, то есть всего 20 различных символов. Следовательно, необходимо определить наименьшее количество бит, которыми можно закодировать не менее 20 различных значений. То есть найти такое наименьшее натуральное число N, при котором 2 N ≥ 20. Так как 2 4 < 20 < 2 5 , то минимальное количество бит, необходимое для кодирования одного символа, равно 5. Логин состоит из 12 символов. Следовательно, для его записи потребуется 12 · 5 = 60 бит.

По условию задачи логин в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт. Для нахождения необходимого количества байтов округляем в большую сторону значение 60/8. То есть для логина потребуется 8 байт.

Так как для хранения записей о 100 пользователях потребуется 1100 байт, то на одного пользователя программой отводится 1100/100 == 11 байт.

Учитывая, что 8 байт отводится под логин, получаем, что для пароля отводится 3 байта.

Задача 9

Каждый пользователь сети обладает паролем вида XXZXYXXZ, где X — строчная буква английского алфавита (всего используется 26 различных символов), Y — цифра 0, 1, · · · , 9 и Z — либо 0, либо 1. Кодирование паролей осуществляется посимвольно. Каждый из символов X, Y и Z кодируется минимально возможным количеством бит, а каждый пароль занимает одинаковое целое число байт. Определите объём памяти (в байтах), необходимый для хранения 20 паролей. В ответе запишите только число, слово «байт» писать не нужно.

13.1 В некоторой стране автомобильный номер длиной 6 символов составляют из заглавных букв (задействовано 19 различных букв) и десятичных цифр в любом порядке.

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

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

Решение В номере используется 19+10 = 29 символов. 2 4 = 16 < 29 <= 2 5 = 32. Поэтому для кодирования одного символа требуется 5 бит. В каждом номере – 6 символов. Поэтому для хранения одного номера нужно 30 бит. Так как 3*8 < 30 <= 4*8, то придется использовать 4 байт. Для записи 40 номеров нужно 4*40 = 160 байт.

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

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

Правильный ответ: 240 байт

13.3 В некоторой стране автомобильный номер длиной 10 символов составляют из заглавных букв (задействовано 19 различных букв) и десятичных цифр в любом порядке. Каждый такой номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством бит). Определите объем памяти, отводимый этой программой для записи 40 номеров.

Правильный ответ: 280 байт

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

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

Правильный ответ: 240 байт

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

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

Правильный ответ: 300 байт

13.6 При регистрации в компьютерной системе каждому пользователю выдается пароль, состоящий из 9 символов и содержащий только символы A, B, C, D. E, F. Каждый такой пароль в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством бит).

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

Решение. С помощью k бит можно закодировать 2 k символов. У нас 6 символов. Значит, нужно брать 3 бит на символ (2 2 =4 < 6 < 8 = 2 3 ).

В пароле 9 символов, для их кодирование нужно 9*3 = 27 бит = 3 байт + 3 бит. Наименьшее достаточное целое число байт – это 4 байта. Для хранения 50 паролей нужно 50*4 = 200 байт.

13.7 При регистрации в компьютерной системе, используемой при проведении командной олимпиады, каждому ученику выдается уникальный идентификатор - целое число от 1 до 1000. Для хранения каждого идентификатора используется одинаковое и минимально возможное количество бит. В каждой команде участвует 3 ученика. Идентификатор команды состоит из последовательно записанных идентификаторов учеников. Для записи каждого идентификатора команды система использует одинаковое и минимально возможное количество байт. Сколько байт должна отвести система для записи идентификаторов 20 команд?

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

13.8 При регистрации в компьютерной системе, используемой при проведении командной олимпиады, каждому ученику выдается уникальный идентификатор - целое число от 1 до 1000. Для хранения каждого идентификатора используется одинаковое и минимально возможное количество бит. В каждой команде участвует 4 ученика. Идентификатор команды состоит из последовательно записанных идентификаторов учеников и 12 дополнительных бит. Для записи каждого идентификатора команды система использует одинаковое и минимально возможное количество байт. Сколько байт должна отвести система для записи идентификаторов 20 команд?

Правильный ответ: 140 байт

Решение. Всего нужно 1000 вариантов идентификаторов учеников. Наименьшая степень двойки, которая больше или равна 1000, - это 2 10 = 1024. Поэтому минимальное количество бит, которое можно использовать для хранения одного идентификатора ученика – 10.

Для хранения идентификатора команды нужно 4×10 + 12 = 52 бит.

Далее, 52 бит = 6 байт + 4 бит. Поэтому наименьшее целое количество байт, достаточное для хранения одного идентификатора команды – 7.

I = log₂M * N (формула Хартли).

Если log₂M не является целым числом, округляем значение в большую сторону.

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

Если log₂M не является целым числом, округляем значение в большую сторону.

В нашем случае мощность алфавита (все символы, подлежащие кодированию) M = 28. N тоже = 28, т.к. все спортсмены прошли финиш.

Тогда I = log₂28 * 28 ≈ 5 * 28 = 140 бит.

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы из 12-символьного набора: А, В, C, D, Е, F, G, H, K, L, M, N. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей. Для хранения сведений о 20 пользователях потребовалось 400 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число – количество байт.

Раз для хранения сведений о 20 пользователях потребовалось 400 байт, то для хранения сведений об 1 пользователе нужно 20 байт.

Для хранения пароля, по формуле Хартли, необходимо log₂M * N = log₂12 * 15 ≈ 4 * 15 = 60 бит. Но под пароль отведено минимально возможное целое количество байт, значит под пароль отведено 60/8 ≈ 8 байт (округляем в большую сторону, иначе не получится записать пароль). Значит, для хранения дополнительных сведений остается 20 – 8 = 12 байт.

При регистрации в компьютерной системе каждому пользователю выдаётся идентификатор, состоящий из 8 символов, первый и последний из которых — одна из 18 букв, а остальные — цифры (допускается использование 10 десятичных цифр). Каждый такой идентификатор в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование; все цифры кодируются одинаковым и минимально возможным количеством бит, все буквы также кодируются одинаковым и минимально возможным количеством бит).

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

Рассмотрим отдельно буквенную и цифровую часть идентификатора.

Для записи каждой из 18 букв необходимо log₂18 ≈ 5 бит.

Для записи каждой из 10 цифр необходимо log₂10 ≈ 4 бит.

Для хранения всех 8 символов идентификатора нужно 5·2 + 4·6 = 34 бита, а т. к. для записи используется целое число байт, то 34/8 округляем в большую сторону. Получаем 5 байт.

Читайте также: