Отправлено: 20.11.22 22:47. Заголовок: 5701

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

Ответ на сайте: 800

Объясните, пожалуйста

 Отправлено: 22.11.22 13:29. Заголовок: Решение

Т.к. ничего не сказано о посимвольном кодировании, кодируем количество различных идентификаторов.
Первый символ: одна из 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 байтов

 Отправлено: 28.04.23 02:49. Заголовок: 71 бит = 8 юайт, в м..

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

 Отправлено: 28.04.23 15:25. Заголовок: А где сказано про по..

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

цитата:

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

интересно, как Вы уместите 71 кг картошки в 8 ящиков по 8 кг каждый

 Отправлено: 14.11.23 00:13. Заголовок: Решал сейчас эту зад..

Решал сейчас эту задачу и тоже получилось 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.

 Отправлено: 14.11.23 21:47. Заголовок: Читайте выше: тут не..

Читайте выше: тут нет посимвольного кодирования:

цитата:

Для кодирования каждого идентификатора отведено одинаковое минимально возможное целое число байтов.

Поэтому ваша логика неверна.

цитата:

Т.к. ничего не сказано о посимвольном кодировании, кодируем количество различных идентификаторов. Первый символ: одна из 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 байтов

 Отправлено: 15.11.23 12:20. Заголовок: Как у вас будет коди..

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

 Отправлено: 29.11.23 23:16. Заголовок: В случае посимвольно..

В случае посимвольного кодирования мы выделяем для 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

 
 from itertools import * 
 print('номер идентификатора     двоичный код      идентификатор') 
 for i,c in enumerate(product('абвгд','0123456789','0123456789')): 
     print(i+1,' '*22, bin(i)[2::].zfill(9),' '*7,''.join(c))