Форум » Вычисление количества информации » 5701 » Ответить

5701

Алексей Г.: При регистрации в компьютерной системе каждому пользователю присваивается уникальный идентификатор, состоящий из 12 символов. Первым символом идентификатора является одна из 26-ти заглавных латинских букв, оставшиеся символы могут быть одной из 26-ти строчных латинских букв, либо десятичной цифрой. Для кодирования каждого идентификатора отведено одинаковое минимально возможное целое число байтов. Сколько байтов потребуется для хранения 100 идентификаторов? Решение: На первую часть выделяем 5 бит всего, т к 26 символов - вес 1 символа 5 бит, а мы кодируем й символ. На вторую часть выделяем 66 бит, т к мощность алфавита 36 символов, т е на 1 символ 6 бит, а символов 11. Итого: 5 + 66 бит = 71 бит, т е 9 байт => 9*100 = 900 байт Ответ на сайте: 800 Объясните, пожалуйста

Ответов - 7

info17: Т.к. ничего не сказано о посимвольном кодировании, кодируем количество различных идентификаторов. Первый символ: одна из 26 букв Остальные 11 символов: один из 36 символов (10 цифр + 26 букв = 36) Значит необходимо закодировать: 26 * 36 * 36 * 36 * 36 * 36 * 36 * 36 * 36 * 36 * 36 * 36 = 26 * 36**11 идентификаторов или 3 422 164 299 898 945 536 Для кодирования такого количества идентификаторов потребуется: log_2⁡(3 422 164 299 898 945 536)=62 бита Целое количество байтов, для кодирования одного идентификатора: 62 / 8 = 8 байт Для хранения 100 идентификаторов потребуется: 100 * 8 = 800 байтов

mary: 71 бит = 8 юайт, в меньшую сторону округляется

oval: А где сказано про посимвольное кодирование? 26 вариантов на 1 символ и 36^11 на оставшиеся log2(26)+log2(36^11) = 61,5..... помещается в 8 байт mary пишет: 71 бит = 8 юайт, в меньшую сторону округляется интересно, как Вы уместите 71 кг картошки в 8 ящиков по 8 кг каждый


Alvik77: Решал сейчас эту задачу и тоже получилось 900. Логика следующая. 1-й символ может быть любым из 26-ти (заглавные латинские буквы), то есть кодируется числами от 0 до 25 для его кодировки надо 5 бит. Условно, Z = 11001. Символы со 2-го по 12-й могут быть маленькими латинскими буквами либо цифрами, то есть, любым из 36-ти. Последний, 36-й (например, 9) будет иметь номер 35 и код = 100011. Теоретически возможен идентификатор Z99999999999, для его кодирования будут нужны 1х5 + 11х6 = 71 бит = 9 байт. Но в условии сказано, что "Для кодирования каждого идентификатора отведено одинаковое минимально возможное целое число байтов", следовательно, для остальных идентификаторов также должны быть отведены 9 байт. Следовательно, для хранения 100 идентификаторов нужно 9 х 100 = 900 байт. Ответ: 900.

Ж: Читайте выше: тут нет посимвольного кодирования: Для кодирования каждого идентификатора отведено одинаковое минимально возможное целое число байтов. Поэтому ваша логика неверна. Т.к. ничего не сказано о посимвольном кодировании, кодируем количество различных идентификаторов. Первый символ: одна из 26 букв Остальные 11 символов: один из 36 символов (10 цифр + 26 букв = 36) Значит необходимо закодировать: 26 * 36 * 36 * 36 * 36 * 36 * 36 * 36 * 36 * 36 * 36 * 36 = 26 * 36**11 идентификаторов или 3 422 164 299 898 945 536 Для кодирования такого количества идентификаторов потребуется: log_2⁡(3 422 164 299 898 945 536)=62 бита Целое количество байтов, для кодирования одного идентификатора: 62 / 8 = 8 байт Для хранения 100 идентификаторов потребуется: 100 * 8 = 800 байтов

Alvik77: Как у вас будет кодирован идентификатор Z99999999999, при условии, что это последние символы в последовательностях? Для него нужны 71 бит (25 в двоичной системе = 11001 и 35 в двоичной = 100011, поэтому 5*1 + 11*6 = 71), т.е. 9 байт. В 8 байт он никак не влезет. Но все идентификаторы, по условию, имеют "ОДИНАКОВУЮ" длину, т.е., 9 байт. Значит, для хранения 100 идентификаторов нужны 900 байт.

Ж: В случае посимвольного кодирования мы выделяем для 1-го символа 5 бит, для остальных 11-ти по 6. Итого 71 бит Но в задаче не требуется посимвольное кодирование: в таком случае память выделяется для кодирования идентификатора целиком: Таких идентификаторов : 26 * 36 * 36 * 36 * 36 * 36 * 36 * 36 * 36 * 36 * 36 * 36 = 26 * 36**11 штук (или 3 422 164 299 898 945 536) Z99999999999 - один из них. Для сохранения такого объема данных выделяем log_2⁡(3 422 164 299 898 945 536)=62 бита памяти. Т.е. 8 байт. Более компактный и простой пример: Пусть идентификатор состоит из 3 символов: одной из букв "абвгд' и двух цифр. При посимвольном кодировании выделяем память на каждый символ: буква - 5 вариантов - 3 бита, цифра- 10 вариантов = 4 бита ИТОГО 3+4+4 = 11 бит При отсутствии посимвольного кодирования выделяем память на весь идентификатор: По правилам комбинаторики таких идентификаторов: 5*10*10 = 500 штук. Для кодирования такого количества данных достаточно Log_2(500)=9 бит номер идентификатора двоичный код идентификатор 1 000000000 а00 2 000000001 а01 3 000000010 а02 4 000000011 а03 ... 497 111110000 д96 498 111110001 д97 499 111110010 д98 500 111110011 д99 [pre2] from itertools import * print('номер идентификатора двоичный код идентификатор') for i,c in enumerate(product('абвгд','0123456789','0123456789')): print(i+1,' '*22, bin(i)[2::].zfill(9),' '*7,''.join(c)) [/pre2]



полная версия страницы