Темы индивидуальных заданий по деревьям
1. Дэвид Хаффман, возглавлявший кафедру компьютерных наук Массачусетского технологического института, широко известен как разработчик метода построения минимально избыточных кодов. Использование метода Хаффмана для кодирования текстовой информации, позволяет сократить объем, занимаемой текстом, за счет того, что часто встречающиеся символы кодируются более короткими кодами, а редко встречающиеся – более длинными. Для определения кодов символов подсчитывается частота встречаемости каждого символа в тексте и на основе этих частот строится дерево кодирования. Алгоритм построения дерева Хаффмана:
Символы входного алфавита образуют список свободных узлов. Каждый узел имеет вес, равный количеству вхождений символа в исходное сообщение.
В списке выбираются два свободных узла с наименьшими весами, после чего создается их узел – «родитель» с весом, равным сумме их весов, он соединяется с «потомками» дугами.
Одной дуге, выходящей из «родителя», ставится в соответствие бит 1, другой – бит 0.
«Родитель» добавляется в список свободных узлов, а двое его «потомков» удаляются из этого списка.
Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.
Пример.
Построение дерева Хаффмана для текста «КOL_ОКОLО_КОLОКОLА»:
Теперь для определения кода каждой конкретной буквы необходимо просто пройти от вершины дерева до этой буквы, выписывая нули и единицы по маршруту следования. В нашем примере символы получат следующие коды:
Символ | Код |
O | 00 |
К | 01 |
L | 10 |
Пробел( _ ) | 110 |
А | 111 |
После кодирования исходного текста получим:
010010110000100100011001001000010010111
Таким образом, весь текст будет занимать 39 бит памяти, приблизительно 5 байт. Для сравнения: при использовании таблицы ASCII-кодов для хранения этого текста потребовалось бы 18 байт и коэффициент сжатия в нашем случае равен 18 / 5 = 3,6. Для восстановления сжатых данных так же необходимо воспользоваться деревом Хаффмана, полученным в самом начале.
Если построенное дерево Хаффмана содержит всего один узел (корень), не имеющий потомков, считать, что символ, соответствующий этому узлу кодируется одним битом, например, кодом 0.
Требуется написать программу, которая для заданного текста построит дерево Хаффмана, определит коды символов и закодирует с их помощью исходный текст. В качестве результата работы программы должна выдавать длину полученного кода в битах.
Формат входных данных
Во входном файле находится сжимаемый текст. Признаком окончания текста служат символ #. В тексте могут встречаться только заглавные латинские буквы, пробел и знаки препинания ( . , : ; ! ? – “). Текст может состоять из нескольких строк. Строк в тексте не более 25, символов в одной строке не более 80. Символы перевода строки и возврата каретки, а так же символ # не должны учитываться в исходном тексте.
Формат выходных данных
В выходном файле должно быть одно число, означающее длину кода Хаффмана для этого текста в битах.
Примеры входного и выходного файлов
input. txt | output. txt |
КОL ОКОLО КОLОКОLА# | 39 |
2. «Почтальон» Мудрый тритон работает почтальоном в Лукоморье. В перечень его обязанностей входит доставка корреспонденции птицам, разместившим свои гнезда на ветвях дуба (постепенно вытеснив оттуда русалку). Птицы вьют свои гнезда там, где ветка дерева разделяется на несколько более тонких веток. Лукоморье является районом с развитой инфраструктурой, поэтому все разветвления на дубе заняты гнездами птиц. За время работы тритон не только запомнил, где кто живет, но и уяснил, что если его путь проходит через чье-либо гнездо, и его обитатели не получают при этом корреспонденции, ему приходится извиняться за доставленные неудобства. Естественно, интеллигентный тритон стремится как можно меньше беспокоить обитателей дуба, поэтому он заранее планирует свой маршрут так, чтобы приносить минимальное число извинений.
Напишите программу, которая по описанию мест обитания птиц и списку корреспонденции определяет, сколько раз придется извиняться мудрому тритону.
Каждое гнездо дуба обозначено уникальным номером, что соответствует номеру квартиры, который мы иногда указываем, отправляя письма родным и близким по обычной почте. Гнездо, расположенное на первой развилке ствола имеет номер один. Тритон может только ползти по веткам или стволу дуба, прыжки и перелеты полностью исключены. Никакие ветки не соприкасаются и не пересекаются.
Формат входного файла:
В первой строке входного файла находится число M – количество гнезд на дубе (0<M<1000). В следующих M строках находится информация о размещении гнезд и количестве писем для каждого из возможных адресатов. Первые два числа ni и li – количество соседей гнезда с номером i и количество направленных по этому адресу писем соответственно. Далее в строке приводится ni чисел – номера гнезд, являющихся соседними с гнездом c номером i.
Формат выходного файла:
В единственной строке выходного файла должно содержаться единственное число – минимальное количество извинений, которые придется приносить мудрому тритону, для того чтобы доставить все письма.
Пример входного файла:
5
3 2 2 5 4
1 1 1
1 1 4
2 2 3 1
1 3 1
Пример выходного файла:
2
3. Чиновники. Есть министерство из n чиновников. Каждый из них может иметь только одного непосредственного начальника и произвольное количество подчиненных. Однако в министерстве работает только один чиновник, не имеющий начальников, – главный чиновник. Для того чтобы предприниматель мог получить некоторую лицензию, необходимо получить подпись на документе главного чиновника. Каждый чиновник для выставления своей подписи требует подпись на документе хотя бы одного из своих непосредственных подчиненных и, может быть, некоторую взятку – известное число у. е.
Необходимо определить, какое минимальное количество денег предпринимателю нужно заплатить, чтобы получить лицензию, и указать соответствующий этой сумме порядок получения подписей.
4. Два дерева называется изоморфными, если можно отобразить одно из них в другое, изменив порядок сыновей его узлов. Распознать изоморфизм двух произвольных деревьев T1 и T2. Считать, что Т1 и Т2 являются деревьями общего вида, т. е. каждая вершина может иметь произвольное число потомков.
5. Написать программу, которая по заданной формуле строит дерево и производит вычисления с помощью построенного дерева. Формула задана в традиционной инфиксной записи, в ней могут быть скобки, максимальная степень вложенности которых ограничивается числом 10. Аргументами могут быть целые числа и переменные, задаваемые однобуквенными именами. Допустимые операции: +, -, *, /. Унарный минус допустим. С помощью построенного дерева формулы упростить формулу, заменяя в ней все поддеревья, соответствующие формулам ((f1±f2)*f3) и (f1*(f2±f3)) на поддеревья, соответствующие формулам (f1*f3±f2*f3) и (f1*f2±f1*f3).
6. Написать программу, которая по заданной формуле строит дерево и производит вычисления с помощью построенного дерева. Формула задана в традиционной инфиксной записи, в ней могут быть скобки, максимальная степень вложенности которых ограничивается числом 10. Аргументами могут быть целые числа и переменные, задаваемые однобуквенными именами. Допустимые операции: +, -, *, /. Унарный минус допустим. С помощью построенного дерева формулы упростить формулу, заменяя в ней все поддеревья, соответствующие формулам (f1*f3±f2*f3) и (f1*f2±f1*f3) на поддеревья, соответствующие формулам ((f1±f2)*f3) и (f1*(f2±f3)).
7. Написать программу, которая по заданной формуле строит дерево и производит вычисления с помощью построенного дерева. Формула задана в традиционной инфиксной записи, в ней могут быть скобки, максимальная степень вложенности которых ограничивается числом 10. Аргументами могут быть целые числа и переменные, задаваемые однобуквенными именами. Допустимые операции: +, -, *, /, ^. Унарный минус допустим. С помощью построенного дерева формулы T1 построить новое дерево формулы T2. Формула T2 должна являться второй производной от формулы T1 по заданной переменной.
8. Написать программу, которая по заданной формуле строит дерево и производит вычисления с помощью построенного дерева. Формула задана в традиционной инфиксной записи, в ней могут быть скобки, максимальная степень вложенности которых ограничивается числом 10. Аргументами могут быть целые числа и переменные, задаваемые однобуквенными именами. Допустимые операции: sin(), cos(), +, -, *, /, ^. Унарный минус допустим. С помощью построенного дерева формулы T1 построить новое дерево формулы T2. Формула T2 должна являться первой производной от формулы T1 по заданной переменной.
9. Написать программу, которая по заданной формуле строит дерево и производит вычисления с помощью построенного дерева. Формула задана в традиционной инфиксной записи, в ней могут быть скобки, максимальная степень вложенности которых ограничивается числом 10. Аргументами могут быть целые числа и переменные, задаваемые однобуквенными именами. Допустимые операции: +, -, *, /. Унарный минус допустим. С помощью построенного дерева формулы упростить формулу, заменяя в ней все поддеревья, соответствующие формулам (f1 / f3 ± f2 / f3) на поддеревья, соответствующие формулам ((f1±f2)/f3). Для начального и преобразованного дерева реализовать возможность вычисления значения формулы при заданных значениях аргументов.
10. Имеется список идентификаторов некоторой программы отсортированный в порядке возрастания. Все идентификаторы хранятся в текстовом файле, по одному в строке и начинаются с первой позиции строки. Необходимо построить идеально-сбалансированное дерево поиска для данного списка идентификаторов. А так же реализовать операцию удаления идентификатора из дерева таким образом, чтобы дерево оставалось по крайней мере АВЛ-сбалансированным, т. е. если необходимо после удаления должна быть выполнена балансировка дерева. При балансировке дерева должны использоваться как малые, так и большие повороты. Программа должна выдавать полный отчет о построении дерева, т. е. распечатывать дерево так, чтобы видна была структура дерева после каждого удаления и каждого поворота.
11. Имеется словарь русского языка, отсортированный в порядке возрастания. Все слова словаря хранятся в текстовом файле, по одному в строке и начинаются с первой позиции строки. Необходимо построить АВЛ-дерево поиска для данного словаря.. При балансировке дерева должны использоваться как малые, так и большие повороты. Программа должна выдавать полный отчет о построении дерева, т. е. распечатывать дерево так, чтобы видна была структура дерева после каждого включения и каждого поворота.
12. Имеется список идентификаторов некоторой программы. Все идентификаторы хранятся в текстовом файле, по одному в строке и начинаются с первой позиции строки. Необходимо построить дерево поиска для данного списка идентификаторов. Дерево должно быть АВЛ-сбалансированным, т. е. при включении очередного идентификатора, если необходимо должна быть выполнена балансировка дерева. При балансировке дерева должны использоваться как малые, так и большие повороты. Программа должна выдавать полный отчет о построении дерева, т. е. распечатывать дерево так, чтобы видна была структура дерева после каждого включения и каждого поворота.
13. В файле даны n целых чисел, и здесь же указан путь их размещения в бинарном дереве виде двоичного кода (коды не повторяются). Построить двоичное дерево целых чисел, в котором путь по дереву определяется указанным двоичным кодом в этом листе (1 – переход к правому потомку, 0 - переход к левому потомку). В корень автоматически заносится значение 0. Например, для исходных данных:
15 | 111 |
18 | 101 |
3 | 10 |
8 | 11 |
9 | 1 |
11 | 0 |
7 | 100 |
4 | 110 |
17 | 00 |
20 | 01 |
должно быть построено такое дерево:
Учитывать ситуацию, когда дерево не может быть построено.
14. На телефонной станции картотека абонентов, содержащая сведенья о телефонах и их владельцах, организованна как бинарное дерево. Составить программу, которая:
1) Обеспечивает начальное формирование картотеки в виде бинарного дерева (информационные поля: номер телефона, общее время разговора за месяц, сумма долга);
2) Производит вывод всей картотеки;
3) Обеспечивает добавление в картотеку для указанного номера телефона времени нового разговора путем добавления его к уже заданному (суммированием);
4) определяет сумму задолженности для каждого номера после указания ввода стоимости 1 минуты.
5) выводит извещение на оплату телефонного разговора для заданного номера телефона.
Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.
15. Имеется набор чисел. Все числа хранятся в текстовом файле, по одному в строке и начинаются с первой позиции строки. Необходимо построить дерево поиска для данного набора чисел. Дерево должно быть АВЛ-сбалансированным, т. е. при включении очередного идентификатора, если необходимо должна быть выполнена балансировка дерева. При балансировке дерева должны использоваться как малые, так и большие повороты. Программа должна выдавать полный отчет о построении дерева, т. е. распечатывать дерево так, чтобы видна была структура дерева после каждого включения и каждого поворота.
16. Два дерева называется изоморфными, если можно отобразить одно из них в другое, изменив порядок сыновей его узлов. Распознать изоморфизм двух произвольных деревьев T1 и T2. Считать, что Т1 и Т2 являются деревьями общего вида, т. е. каждая вершина может иметь произвольное число потомков.
17. Написать программу, которая по заданной формуле строит дерево и производит вычисления с помощью построенного дерева. Формула задана в традиционной инфиксной записи, в ней могут быть скобки, максимальная степень вложенности которых ограничивается числом 10. Аргументами могут быть целые числа и переменные, задаваемые однобуквенными именами. Допустимые операции: +, -, *, /. Унарный минус допустим. С помощью построенного дерева формулы упростить формулу, заменяя в ней все поддеревья, соответствующие формулам ((f1±f2)*f3) и (f1*(f2±f3)) на поддеревья, соответствующие формулам (f1*f3±f2*f3) и (f1*f2±f1*f3).
18. Написать программу, которая по заданной формуле строит дерево и производит вычисления с помощью построенного дерева. Формула задана в традиционной инфиксной записи, в ней могут быть скобки, максимальная степень вложенности которых ограничивается числом 10. Аргументами могут быть целые числа и переменные, задаваемые однобуквенными именами. Допустимые операции: +, -, *, /. Унарный минус допустим. С помощью построенного дерева формулы упростить формулу, заменяя в ней все поддеревья, соответствующие формулам (f1*f3±f2*f3) и (f1*f2±f1*f3) на поддеревья, соответствующие формулам ((f1±f2)*f3) и (f1*(f2±f3)).
19. Имеется список идентификаторов некоторой программы. Все идентификаторы хранятся в текстовом файле, по одному в строке и начинаются с первой позиции строки. Необходимо построить дерево поиска для данного списка идентификаторов. Дерево должно быть АВЛ-сбалансированным, т. е. при включении очередного идентификатора, если необходимо должна быть выполнена балансировка дерева. При балансировке дерева должны использоваться как малые, так и большие повороты. Программа должна выдавать полный отчет о построении дерева, т. е. распечатывать дерево так, чтобы видна была структура дерева после каждого включения и каждого поворота.
20. Имеется набор чисел. Все числа хранятся в текстовом файле, по одному в строке и начинаются с первой позиции строки. Необходимо построить дерево поиска для данного набора чисел. Дерево должно быть АВЛ-сбалансированным, т. е. при включении очередного идентификатора, если необходимо должна быть выполнена балансировка дерева. При балансировке дерева должны использоваться как малые, так и большие повороты. Программа должна выдавать полный отчет о построении дерева, т. е. распечатывать дерево так, чтобы видна была структура дерева после каждого включения и каждого поворота.
