2019-gate-computer-science-and-it-practice.pdf/Q17-alg4 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 16: | Строка 16: | ||
* Отсортируем по частотам: <m>\{a: \frac{1}{36}, b: \frac{1}{36}, c: \frac{3}{36}, d: \frac{4}{36}, e: \frac{5}{36}\}</m> | * Отсортируем по частотам: <m>\{a: \frac{1}{36}, b: \frac{1}{36}, c: \frac{3}{36}, d: \frac{4}{36}, e: \frac{5}{36}\}</m> | ||
| − | * Собираем символы с меньшими частотами, узел <m>\{a, b\}<m> с частотой <m>\frac{1}{36} + \frac{1}{36} = \frac{2}{36} = \frac{1}{18}</m> | + | * Собираем символы с меньшими частотами, узел <m>\{a, b\}</m> с частотой <m>\frac{1}{36} + \frac{1}{36} = \frac{2}{36} = \frac{1}{18}</m> |
** Список: <m>\{\{a, b\}: \frac{2}{36}, c: \frac{3}{36}, d: \frac{4}{36}, e: \frac{5}{36}\}</m> | ** Список: <m>\{\{a, b\}: \frac{2}{36}, c: \frac{3}{36}, d: \frac{4}{36}, e: \frac{5}{36}\}</m> | ||
* Собираем символы с меньшими частотами, узел <m>\{\{a, b\}, c\}</m> с частотой <m>\frac{2}{36} + \frac{3}{36} = \frac{5}{36}</m> | * Собираем символы с меньшими частотами, узел <m>\{\{a, b\}, c\}</m> с частотой <m>\frac{2}{36} + \frac{3}{36} = \frac{5}{36}</m> | ||
| Строка 45: | Строка 45: | ||
;c: | ;c: | ||
| − | * | + | * Right → Right → Right |
| − | * | + | * 111 |
| Строка 56: | Строка 56: | ||
[[Категория:Надо не забыть выбрать тему]] | [[Категория:Надо не забыть выбрать тему]] | ||
| + | |||
| + | [[Категория:Теория кодирования]] | ||
Версия 14:27, 25 декабря 2024
Вопрос: Q17-alg4-31d68c
Предположим, что символы a,b,c,d,e встречаются с частотами .
Какие получатся коды Хаффмана для букв a,b,c соответственно?
Ответы
- 1101, 111, 1101
- Правильный ответ: 1100, 1101, 111
- 1100, 10, 0
- 1101, 1100, 111
Объяснение
Необходимо построить дерево Хаффмана и получить коды Хаффмана.
- Отсортируем по частотам:
- Собираем символы с меньшими частотами, узел с частотой
- Список:
- Собираем символы с меньшими частотами, узел с частотой
- Список:
- Собираем символы с меньшими частотами, узел с частотой
- Список:
- Собираем остатки, меньшие частоты налево, узел с частотой
Root
/ \
e {d, {{a, b}, c}}
/ \
d {{a, b}, c}
/ \
{a, b} c
/ \
a b
Осталось назначить коды.
- a
- Right → Right → Left → Left
- 1100
- b
- Right → Right → Left → Right
- 1101
- c
- Right → Right → Right
- 111
Исходники — вопрос 17 на 238 странице книги «2019-gate-computer-science-and-it-practice.pdf»
Задача зарезервирована: StasFomin 10:34, 25 декабря 2024 (UTC)