Сделай подробно с алгоритмом

Краткие ответы

№	Ответ
1	40, 41, 42, 43
2	29
3	000, 100, 111 (сумма длин 9)
4	20 Кбайт (= 160 Кбит)
5	например 512 × 256 (произведение сторон 131 072)
6	89 байт

---

№1. Целые X между \(100111_2\) и \(2C_{16}\)

Алгоритм:

1. Переводим левую границу в десятичную: каждый разряд умножаем на степень двойки. \[100111_2 = 32+0+0+4+2+1 = 39\]
2. Переводим правую границу: hexadecimal digit \(C = 12\). \[2C_{16} = 2\cdot16+12 = 44\]
3. Неравенства строгие, значит сами границы не входят: \(39 < X < 44\).

Ответ: \(X \in \{40, 41, 42, 43\}\).

Проверка: \(40 = 101000_2\), \(43 = 101011_2\), а \(44 = 101100_2\). Все четыре числа лежат строго между \(100111_2\) и \(101100_2\). Первое число меньше 40 — это 39, оно равно границе, второе после 43 — это 44, тоже граница.

---

№2. Алгоритм с дописыванием двух разрядов

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

Алгоритм:

1. \(N\) чётное → дописываем 00 → \(R = 4N\).
2. \(N\) нечётное → дописываем 11 → \(R = 4N+3\).
3. Ищем минимальное \(N\) с условием \(R > 117\). Проверяем числа подряд от меньшего:
   • \(N=28\) (чётное): \(R = 112\) — не подходит;
   • \(N=29\) (нечётное): \(R = 4\cdot29+3 = 119 > 117\) — подходит.

Ответ: \(N = 29\).

Проверка: \(29 = 11101_2\), число нечётное, дописываем 11: \(1110111_2 = 64+32+16+4+2+1 = 119\). А для \(N=28\): \(11100_2 \to 1110000_2 = 112\), условие не выполнено.

---

№3. Условие Фано

Правило: ни одно кодовое слово не должно быть началом (префиксом) другого. Проверять удобно по дереву: занятое слово «выключает» все свои продолжения.

Алгоритм:

1. Выписываем занятые слова: 01 (длина 2), 001, 101, 110 (длина 3).
2. Свободные слова длины 1: 0 и 1 — оба являются началом занятых слов (01 и 101, 110), брать нельзя.
3. Свободные слова длины 2:
   • 00 — начало слова 001, нельзя;
   • 10 — начало слова 101, нельзя;
   • 11 — начало слова 110, нельзя.
4. Свободные слова длины 3 (проверяем все 8 вариантов): 000, 010, 011, 100, 111.
   • 010 и 011 начинаются с занятого 01 — отбрасываем;
   • остаются 000, 100, 111 — ровно три слова, и они не являются началами друг друга.
5. Значит, короче трёх разрядов слова для Д, Е, Ж быть не могут.

Ответ: Д, Е, Ж — 000, 100, 111 (в любом порядке); минимальная сумма длин \(3+3+3 = 9\).

Проверка: 000 отличается от 001 в третьем разряде, 100 — от 101, 111 — от 110, а слово 01 не является началом ни одного из новых.

---

№4. Объём текста

Алгоритм:

1. Мощность алфавита 1024: \(1024 = 2^{10}\), значит на один символ нужно 10 бит.
2. Количество символов \(2^{14} = 16384\).
3. Объём: \(16384 \cdot 10 = 163840\) бит.
4. Переводим в байты: \(163840 : 8 = 20480\) байт; в килобайты: \(20480 : 1024 = 20\) Кбайт.

Ответ: 20 Кбайт (это же 160 Кбит; в мегабайтах получается не целое число, поэтому Кбайт — максимальная «удобная» единица).

---

№5. Разрешение изображения

Алгоритм:

1. Палитра 256 цветов: \(256 = 2^8\), значит 8 бит = 1 байт на пиксель.
2. Объём файла: \(128\) Кб = \(128 \cdot 1024 = 131072\) байт.
3. Так как на пиксель ровно 1 байт, число пикселей тоже 131 072.
4. Разрешение — это пара сторон, произведение которых равно \(131072 = 2^{17}\): например \(512 \cdot 256\), \(256 \cdot 512\), \(1024 \cdot 128\).

Ответ: например 512 × 256 пикселей (или любая пара с произведением 131 072).

Замечание: считается, что файл без сжатия и без служебного заголовка.

---

№6. Пароль и дополнительные сведения

Алгоритм:

1. Мощность алфавита пароля: 33 заглавные русские буквы + 7 цифр (0–6) = 40 символов.
2. Бит на символ: \(2^5 = 32 < 40 \le 64 = 2^6\), значит 6 бит.
3. Объём пароля: \(14 \cdot 6 = 84\) бит. В целых байтах: \(\lceil 84:8 \rceil = 11\) байт.
4. На одного пользователя: \(3000 : 30 = 100\) байт.
5. На дополнительные сведения: \(100 - 11 = 89\) байт.

Ответ: 89 байт.

Проверка: \(89 + 11 = 100\), \(100 \cdot 30 = 3000\) — сходится с условием.