Algorithms and Data Structures FAMCS BSU Y2S4 Course
Task list:
- Task 0.1: По набору ключей постройте бинарное поисковое дерево и выполните его прямой левый обход.
- Task 0.2: По набору ключей постройте бинарное поисковое дерево. Удалите из него ключ (правым удалением), если он есть в дереве. Выполните прямой левый обход полученного дерева.
- Task 1.36: Во входном файле задано бинарное дерево поиска в прямом порядке обхода, в котором для любой его вершины все ключи в ее левом поддереве строго меньше ее ключа, а все ключи в ее правом поддереве не меньше ее ключа. В выходной файл требуется вывести данное дерево в обратном и внутреннем порядке обхода. Требуется разработать алгоритм трудоемкости O(n), где n — число вершин дерева.
- Task 2.12: Пусть x и y — две бинарных последовательности длины n и m соответственно, состоящие из нулей и единиц. Сами последовательности x и y можно рассматривать как запись в двоичной форме некоторых двух положительных целых чисел. Необходимо найти максимальное число z, двоичную запись которого можно получить как из x, так и из y вычёркиванием цифр. Ответ выдайте в виде бинарной последовательности.
- Task 2.13: Заданы три пробирки по 100 литров каждая. Две пробирки могут иметь деления, причём деления у первой и второй пробирки совпадают. Третья пробирка делений не имеет. Деления — это отметки, i-я из которых обозначает число di литров. Имеется 100 литров воды, которая разлита в три пробирки. Известно, какой объём воды находится в каждой из двух пробирок с делениями в начальный момент времени, оставшаяся жидкость находится в третьей пробирке. Необходимо определить, можно ли отмерить в третью пробирку ровно x литров воды. Если можно, то за какое минимальное число переливаний. Разрешается выливание (в другую пробирку) из пробирки до метки или доливание (из другой пробирки) в пробирку до метки. Разрешается также выливать (в другую пробирку) всю воду из пробирки.
- Task 2.69: В одном очень длинном и узком пруду по кувшинкам прыгает лягушка. Кувшинки в пруду расположены в один ряд. Лягушка начинает прыгать с первой кувшинки ряда и хочет закончить на последней. Но в силу вредности характера лягушка согласна прыгать только вперед через одну или через две кувшинки. Например, с кувшинки номер 1 она может прыгнуть лишь на кувшинки номер 3 и номер 4. На некоторых кувшинках сидят комарики. А именно, на i-й кувшинке сидят ai комаров. Когда лягушка приземляется на кувшинку, она съедает всех комариков, сидящих на ней. Лягушка хочет спланировать свой маршрут так, чтобы съесть как можно больше комаров. Помогите ей: подскажите, какое максимальное число комаров она может съесть за своё путешествие.