М
Молодежь
К
Компьютеры-и-электроника
Д
Дом-и-сад
С
Стиль-и-уход-за-собой
П
Праздники-и-традиции
Т
Транспорт
П
Путешествия
С
Семейная-жизнь
Ф
Философия-и-религия
Б
Без категории
М
Мир-работы
Х
Хобби-и-рукоделие
И
Искусство-и-развлечения
В
Взаимоотношения
З
Здоровье
К
Кулинария-и-гостеприимство
Ф
Финансы-и-бизнес
П
Питомцы-и-животные
О
Образование
О
Образование-и-коммуникации
pytbrain2007
pytbrain2007
27.10.2020 10:25 •  Информатика

Провести кодирование строки "to be or not to be? " кодом хаффмана и определить избыточность кода. текст в ковычках, там получается 19 символов, никак не могу построить правильное дерево, чтобы закодировать.

👇
Ответ:
Alvn
Alvn
27.10.2020
Подсчитываются вероятности появления символов первичного алфавита в исходном тексте (если они незаданы заранее)Символы первичного алфавита m1 выписывают в порядке убывания вероятностей.Последние n0 символов объединяют в новый символ, вероятность которого равна суммарной вероятностиэтих символов, удаляют эти символы и вставляют новый символ в список остальных на соответствующееместо (по вероятности). n0 вычисляется из системы:
,
где a — целое число, m1 и m2 — мощность первичного и вторичного алфавита соответственно.Последние m2 символов снова объединяют в один и вставляют его в соответствующей позиции,предварительно удалив символы, вошедшие в объединение.Предыдущий шаг повторяют до тех пор, пока сумма всех m2 символов не станет равной 1.Этот процесс можно представить как построение дерева, корень которого — символ с вероятностью 1,получившийся при объединении символов из последнего шага, его m2 потомков — символы из предыдущегошага и т. д.Каждые m2 элементов, стоящих на одном уровне, нумеруются от 0 до m2-1. Коды получаются из путей (отпервого потомка корня и до листка). При декодировании можно использовать то же самое дерево,считывается по одной цифре и делается шаг по дереву, пока не достигается лист — тогда выводится символ,стоящий в листе и производится возврат в корень.Построение дерева ХаффманаБинарное дерево, соответствующее коду Хаффмана, называют деревом Хаффмана.Задача построения кода Хаффмана равносильна задаче построения соответствующего ему дерева.Общая схема построения дерева Хаффмана:Составим список кодируемых символов (при этом будем рассматривать каждый символ как одноэлементноебинарное дерево, вес которого равен весу символа).Из списка выберем 2 узла с наименьшим весом (под весом можно понимать частоту использования символа— чем чаще используется, тем больше весит).Сформируем новый узел и присоединим к нему, в качестве дочерних, два узла выбранных из списка. Приэтом вес сформированного узла положим равным сумме весов дочерних узлов.Добавим сформированный узел к списку.Если в списке больше одного узла, то повторить 2-5.Пример реализацииПример реализации алгоритма Хаффмана на языке// скомпилируйте и введите java HuffmanTest class Tree { public Tree child0; // потомки "0" и "1" public Tree child1; public boolean leaf; // признак листового дерева public int character; // входной символ public int weight; // вес этого символа public Tree() {} public Tree(int character, int weight, boolean leaf) { this.leaf = leaf; this.character = character; this.weight = weight; } /* Обход дерева с генерацией кодов 1. "Распечатать" листовое дерево и записать код Хаффмана в массив 2. Рекурсивно обойти левое поддерево (с генерированием кода). 3. Рекурсивно обойти правое поддерево. */ public void traverse(String code, Huffman h) { if (leaf) { System.out.println((char)character +" "+ weight +" "+ code); h.code[character] = code; } if ( child0 != null) child0.traverse(code + "0", h); if ( child1 != null) child1.traverse(code + "1", h); } } class Huffman { public static final int ALPHABETSIZE = 256; Tree[] tree = new Tree[ALPHABETSIZE]; // рабочий массив деревьев int weights[] = new int[ALPHABETSIZE]; //
4,5(84 оценок)
Открыть все ответы
Ответ:
0894f
0894f
27.10.2020

ответ: 110.

Объяснение:

Максимально подробно.

В начале программы переменная s равна 0, n - 10.

Далее идет цикл "for" от 0 до n, то есть от 0 до 10.

Цикл "for" - последовательность команд, которые программа будет выполнять какое-то количество раз (в данном случае 11 раз:

для "i" равного 0,1,2,3,4,5,6,7,8,9 и 10).

Последовательность команд описывается между словами begin и end:

if і = n-i then s:=s+A[i]+A[i+1];

Рассмотрим подробнее эту строчку. В ней проверяется равенство:

i = n-i

Если это равенство верно, то программа переходит к инструкции, описанной после слова then: s:=s+A[i]+A[i+1];

Если же неверно - программа переходит к следующему значению i.

n - число постоянное и нигде не меняется, оно равно 10, то есть условие выглядит так:

i = 10-i

Когда такое возможно? "i" у нас меняется от 0 до 10 включительно. Посмотрим. Для этого мысленно продумаем весь ход работы программы. В начале i равно 0. Смотрим условие:

0 = 10 - 0

Неверно. 0 не равно 10. Далее программа переходит к следующему i, то есть единице.

i=1: 1 = 10 - 1

Тоже неверно. 1 не равно 9.

i=2: 2 = 10 - 2 Неверно. 2 не равно 8.

i=3: 3 = 10 - 3 Неверно. 3 не равно 7.

i=4: 4 = 10 - 4 Неверно. 4 не равно 6.

i=5: 5 = 10 - 5

Верно. Если это равенство верно, то программа переходит к инструкции, описанной после слова then: s:=s+A[i]+A[i+1];

Здесь к переменной "s", которая изначально равна нулю, прибавляется сама s, то есть 0, и значение элементов массива "A" под индексами i и i+1.

i у нас равно 5.

Следовательно: s=0+A[5]+A[5+1]

Или s=0+A[5]+A[6].

Посмотрим на массив:

(0,10,20,30,40,50,60,70,80,90,100)

A[0]=0, A[1]=10.

Значит пятый элемент равен 50, а шестой - 60.

Следовательно наше выражение:

s=0+A[5]+A[6] = 0 + 50 + 60 = 110.

Но на этом работа программы не закончена.

Цикл будет выполняться до тех пор, пока "i" не станет равно 10.

Идем дальше.

i=6: 6 = 10 - 6 Неверно. 6 не равно 4.

i=7: 7 = 10 - 7 Неверно. 7 не равно 3.

i=8: 8 = 10 - 8 Неверно. 8 не равно 2.

i=9: 9 = 10 - 9 Неверно. 9 не равно 1.

i=10: 10 = 10 - 10 Неверно. 10 не равно 0.

Теперь "i" равно 10, цикл больше выполняться не будет.

ответ: 110.

4,6(58 оценок)
Ответ:
alexaval1980p08mu0
alexaval1980p08mu0
27.10.2020

ответ: 110.

Объяснение:

Максимально подробно.

В начале программы переменная s равна 0, n - 10.

Далее идет цикл "for" от 0 до n, то есть от 0 до 10.

Цикл "for" - последовательность команд, которые программа будет выполнять какое-то количество раз (в данном случае 11 раз:

для "i" равного 0,1,2,3,4,5,6,7,8,9 и 10).

Последовательность команд описывается между словами begin и end:

if і = n-i then s:=s+A[i]+A[i+1];

Рассмотрим подробнее эту строчку. В ней проверяется равенство:

i = n-i

Если это равенство верно, то программа переходит к инструкции, описанной после слова then: s:=s+A[i]+A[i+1];

Если же неверно - программа переходит к следующему значению i.

n - число постоянное и нигде не меняется, оно равно 10, то есть условие выглядит так:

i = 10-i

Когда такое возможно? "i" у нас меняется от 0 до 10 включительно. Посмотрим. Для этого мысленно продумаем весь ход работы программы. В начале i равно 0. Смотрим условие:

0 = 10 - 0

Неверно. 0 не равно 10. Далее программа переходит к следующему i, то есть единице.

i=1: 1 = 10 - 1

Тоже неверно. 1 не равно 9.

i=2: 2 = 10 - 2 Неверно. 2 не равно 8.

i=3: 3 = 10 - 3 Неверно. 3 не равно 7.

i=4: 4 = 10 - 4 Неверно. 4 не равно 6.

i=5: 5 = 10 - 5

Верно. Если это равенство верно, то программа переходит к инструкции, описанной после слова then: s:=s+A[i]+A[i+1];

Здесь к переменной "s", которая изначально равна нулю, прибавляется сама s, то есть 0, и значение элементов массива "A" под индексами i и i+1.

i у нас равно 5.

Следовательно: s=0+A[5]+A[5+1]

Или s=0+A[5]+A[6].

Посмотрим на массив:

(0,10,20,30,40,50,60,70,80,90,100)

A[0]=0, A[1]=10.

Значит пятый элемент равен 50, а шестой - 60.

Следовательно наше выражение:

s=0+A[5]+A[6] = 0 + 50 + 60 = 110.

Но на этом работа программы не закончена.

Цикл будет выполняться до тех пор, пока "i" не станет равно 10.

Идем дальше.

i=6: 6 = 10 - 6 Неверно. 6 не равно 4.

i=7: 7 = 10 - 7 Неверно. 7 не равно 3.

i=8: 8 = 10 - 8 Неверно. 8 не равно 2.

i=9: 9 = 10 - 9 Неверно. 9 не равно 1.

i=10: 10 = 10 - 10 Неверно. 10 не равно 0.

Теперь "i" равно 10, цикл больше выполняться не будет.

ответ: 110.

4,4(88 оценок)
Новые ответы от MOGZ: Информатика
logo
Вход Регистрация
Что ты хочешь узнать?
Спроси Mozg
Открыть лучший ответ