150) (К. Багдасарян) В медицинском учреждении каждой медицинской карточке пациента присваивают уникальный идентификатор, состоящий из 20 символов. Для его хранения отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 600 000 идентификаторов отведено более 11 Мбайт памяти. Определите минимально возможную мощность алфавита, который используется для составления идентификаторов. В ответе запишите только число. 151) (К. Багдасарян) В медицинском учреждении каждой медицинской карточке пациента присваивают уникальный идентификатор, состоящий из 23 символов. Для его хранения отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 500 000 идентификаторов отведено не более 21 Мбайта памяти. Определите максимальную возможную мощность алфавита, который используется для составления идентификаторов. В ответе запишите только число.

Для решения задач необходимо разобраться с тем, как рассчитывается мощность алфавита и необходимо количество бит для кодирования идентификаторов.

Задача 150:

1. Условие задачи: Каждая карточка имеет уникальный идентификатор длиной 20 символов. Для 600 000 идентификаторов нужно более 11 Мбайт.
2. Переведем мегабайты в байты: 11 Мбайт = 11 × 1024 × 1024 байт = 11 577 600 байт.
3. Общее количество символов для хранения: 600 000 идентификаторов × 20 символов = 12 000 000 символов.
4. Определим, сколько байт требуется на один символ: Минимально необходимое количество байт на один символ будет равно общему количеству байт, делённому на общее количество символов: \[ \frac{11 577 600 \text{ байт}}{12 000 000 \text{ символов}} \approx 0.9648 \text{ байт/символ} \] Поскольку один символ не может занимать часть байта, округляем до 1 байта на символ.
5. Количество бит на символ: 1 байт = 8 бит, значит, каждый символ кодируется 8 битами.
6. Количество уникальных символов: Максимальное количество уникальных символов \( A \) определяется по формуле: \[ A^{20} \geq 600 000 \] То есть, \( A \) должно быть меньше или равно \( 2^8 \) (так как мы используем 8 бит): \[ A^{20} \geq 600 000 \Rightarrow A \geq 600 000^{1/20} \approx 2.6 \] Так как мощность алфавита должна быть целым числом, минимум \( A = 3 \).

Ответ: 3

Задача 151:

1. Условие задачи: Каждая карточка имеет уникальный идентификатор длиной 23 символа. Для 500 000 идентификаторов нужно не более 21 Мбайта.
2. Переведем мегабайты в байты: 21 Мбайт = 21 × 1024 × 1024 байт = 22 118 200 байт.
3. Общее количество символов для хранения: 500 000 идентификаторов × 23 символа = 11 500 000 символов.
4. Определим, сколько байт требуется на один символ: Максимально необходимое количество байт на один символ: \[ \frac{22 118 200 \text{ байт}}{11 500 000 \text{ символов}} \approx 1.925 \text{ байт/символ} \] Округляем до 2 байтов на символ.
5. Количество бит на символ: 2 байта = 16 бит, значит, каждый символ кодируется 16 битами.
6. Количество уникальных символов: Максимальное количество уникальных символов \( A \): \[ A^{23} \leq 500 000 \] Поскольку у нас 16 бит на символ: \[ A \leq 2^{16} \approx 65536 \] Теперь вычислим, сколько символов может быть при 500 000 идентификаторов: \[ A^{23} \leq 500 000 \Rightarrow A \leq 500 000^{1/23} \approx 2.339 \] Так как мощность алфавита также должна быть целым числом, максимум \( A = 2 \).

Ответ: 2