На этом форуме отвечают на конкретные вопросы. Фраза «я не понимаю, как решать» — это не вопрос. На вопрос «как решить задачу №X» вас отошлют к материалам сайта kpolyakov.spb.ru. За бессвязный поток слов и неспособность формулировать свои мысли — бан.
Если у вас не сходится ответ на какую-то задачу, пожалуйста сразу представляйте свое «правильное» решение.
Программы "заворачивайте" в тэг [pre2]...[/pre2], при этом сохраняются все отступы и применяется моноширинный шрифт. Если у вас используется сочетание "[i]" для обозначения элемента массива или строки, ставьте пробел после открывающей скобки. Иначе система выделит все дальнейшее курсивом.
Для регистрации на форуме щелкните по ссылке «Вход-регистрация» вверху страницы. В открывшееся окошко «ник» введите свою фамилию на русском языке (например, Иванов). В окошко «пароль» введите придуманный вами пароль, состоящий из латинских букв и цифр. Поставьте галочку в окошке «зарегистрироваться, я новый участник» и нажмите кнопку «ОК».
Отправлено: 17.07.19 15:51. Заголовок: тренировочный КИМ №190121 задание 5
Дан ответ 01,для буквы Б. Но в этом случае не будет выполнено обратное цсловие Фано(как написано в ответах). И как можно сократить Б до 01, если его код дан 101. Что я не так делаю?
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность.
Вот этот код: А – 00; Б – 101; В – 011; Г – 111; Д – 110.
Как можно сократить длину кодового слова для буквы Б так, чтобы код по-прежнему можно было декодировать однозначно?
Коды остальных букв меняться не должны. Если есть несколько вариантов, выберите кодовое слово с минимальным значением.
Вы пишете:
цитата:
Дан ответ 01 для буквы Б. Но в этом случае не будет выполнено обратное условие Фано (как написано в ответах).
Нет. Ни один из оставшихся кодов не заканчивается на 01. Поэтому обратное условие Фано выполнено.
Как решить задачу?
Означает ли фраза "код, удовлетворяющий условию Фано", что нужно рассматривать только прямое условие Фано? Да.
Означает ли отсутствие фразы "код, удовлетворяющий условию Фано", что нужно рассматривать и обратное условие Фано? Да.
В задаче отсутствует фраза "код, удовлетворяющий условию Фано". Поэтому нужно рассматривать и обратное условие Фано.
Построим дерево для заданных кодовых слов, читая их слева направо (прямое условие Фано: А – 00; Б – 101; В – 011; Г – 111; Д – 110). Согласно условию Фано, код декодируется однозначно, если все используемые кодовые слова соответствуют листьям такого дерева. Видим, что для заданных кодовых слов это условие выполняется (выполняется прямое условие Фано).
Код Б - 101 можно в этом случае сократить до Б - 10.
Построим дерево для заданных кодовых слов, читая их справа налево (обратное условие Фано: А – 00; Б – 101; В – 110; Г – 111; Д – 011).
Видим, что для заданных кодовых слов это условие выполняется (выполняется обратное условие Фано).
Код Б - 101 можно в этом случае сократить до Б - 10. При обычном чтении слева направо код Б - 01.
Таким образом, для Б - 10 выполняется прямое условие Фано, а для Б - 01 выполняется обратное условие Фано.
Отправлено: 19.07.19 14:51. Заголовок: Спасибо за ответ. По..
Спасибо за ответ. По первой части все понятно. У меня тоже получился ответ, что Код Б - 101 можно в этом случае сократить до Б - 10. А почему мы должны построить дерево в обратном порядке, по обратному условию Фано, и ответ принимается только 01? Ведь в условии это не сказано.
А почему мы должны построить дерево в обратном порядке, по обратному условию Фано?
Посмотрите пример задания Р-06 в ege5.docРешение (2 способ, дерево) пункт 5 (страница 9):
цитата:
... у нас есть еще обратное условие Фано, для которого тоже можно построить аналогичное дерево, в котором движение от корня к букве дает её код с конца (красным цветом выделен код буквы В – 011, записанный с конца): 110 (выделено красным)...
Далее смотрите на код буквы Г (пункт 6). Код буквы Г сокращается так же, как код буквы Б в рассмотренной ранее задаче. Смотрите рисунок.
Вы пишете:
цитата:
А почему ответ принимается только 01? Ведь в условии это не сказано.
Нет, сказано.
В задаче отсутствует фраза "код, удовлетворяющий условию Фано". Поэтому нужно рассматривать и прямое, и обратное условие Фано.
В условии сказано, что если есть несколько вариантов, нужно выбрать кодовое слово с минимальным значением.
Для Б - 10 выполняется прямое условие Фано, а для Б - 01 выполняется обратное условие Фано.
Кодовое слово с минимальным значением: Б - 01. Поэтому именно его и выбираем.
Все даты в формате GMT
3 час. Хитов сегодня: 2044
Права: смайлы да, картинки да, шрифты нет, голосования нет
аватары да, автозамена ссылок вкл, премодерация откл, правка нет
- участник сейчас на форуме
- участник вне форума