(2 курс ФИИТ) Алгоритмы и структуры данных

Архив 2014/15
#11

Вопрос. Задание сдал в классе, черновик залил, а отправить забыл… Теперь задание “висит” как не сданное. Что с ним делать?

#12

Да ничего не делать, раз сдали. На практике просто указать на это преподавателю, и всё.

#13

А если так регулярно делать: в процессе работы заливать и обновлять версии черновика, а если что-то в жизни случится, замотаться в других делах и не успеть нажать кнопку “Отправить задание”, то будет ли это критично? Т.е. так делать нежелательно, но баллы будут за это ставится или не будут, или всё равно - нажато ли там чего, лишь бы залито???

#15

Не важно, черновик это, или представлено к оценке – главное, чтобы была возможность выставить оценку.

#16

Если $m_h$ — минимальное число вершин в AVL-дереве высоты $h$. Как показать, что $m_{h+2} = m_{h+1} + m_h + 1$?

Это $h(L) + h® + 1$?

#17

Ну да, это практически очевидно, Вы всё правильно поняли.

Если AVL-дерево имеет высоту $h+2$, то, согласно определению, одно из поддеревьев корня имеет высоту $h+1$, а второе – $h+1$ или $h$. Для того, чтобы исходное дерево имело минимальное число вершин, левое и правое поддеревья корня должны иметь минимальное число вершин, тогда получаем: $$m_{h+2}=1 + m_{h+1} + min{m_{h+1},m_h}$$Осталось только показать, что $m_{h+1} > m_h$, что можно принять как очевидное, а можно и более строго попробовать доказать вспомогательное утверждение, что из AVL-дерева всегда можно удалить лист, и полученное дерево также будет AVL-деревом. Ну, остальное просто, хотя для полноты надо еще проверить верность утверждения для базиса – деревьев высотой 0 и 1, к примеру.

А как тут формулы-то по-человечески вставлять?

1 лайк
Пишем формулы и учим Маркдаун
#18

5 сообщений перенесены в новую тему: Пишем формулы и учим Маркдаун

#19

Выполнить задание «Частотный словарь» с использованием реализованных выше структур данных и сбалансированных деревьев. В качестве основы для структуры данных «Множество» использовать тот вариант сбалансированного дерева поиска, который был реализован в предыдущем задании.

Что это за задание, и зачем реализовывать множество на основе предыдущего задания (сбалансированные деревья)?

#20

Эта задача обсуждалась на лекции, и представляет собой простейший словарь, где ключ - слово, а значение по ключу - кол-во вхождений слова в текст. Другими словами, нода представляется в виде пары ключ-значение, т.е. D[слово] равно какому-то целочисленному значению - кол-ву вхождений слова в текст.

#21

Надеюсь, словарь не надо делать на основе кучи?

#22

Зря надеетесь. Если эта надежда связана с предположением о том, что преподаватель опять заставляет использовать неэффективные алгоритмы, могу предложить такой вариант: если Вы реализуете это задание по-своему, и докажете эффективность реализации, то получите x2 баллов. Не сможете доказать эффективность или «изобретете велосипед» – x0, причём выбор структуры для реализации ассоциативного массива оптимизацией не является.

Кстати, пояснение по заданию в Moodle обновлено.

#23

Как можно сделать это для обобщенного типа? Можно ли как-то выкрутиться?!?

void print()
{
	std::copy(a.begin(), a.end(), std::ostream_iterator<int>(std::cout));
}
#24 
template <typename T>
void print()
{
	std::copy(a.begin(), a.end(), std::ostream_iterator<T>(std::cout));
}

Вызывать так:

print<имя_типа>();

Для int, например, будет:

print<int>();
#25

Да, @Casey прав, для обобщенного типа – шаблоном. Могу предложить еще один вариант, с перегрузкой оператора вывода в поток:

template <typename T>
ostream & operator<<(ostream & out, const T & a)
{
    std::copy(a.begin(), a.end(), std::ostream_iterator<T::value_type>(out," "));
    return out;
}
...
std::vector<int> a;
...
std::cout << a;

После определения можете использовать обычный оператор помещения в поток, но у меня такой стиль вызывает опасения – очень уж общий, может вызвать проблемы.

#26

@MB вместо T::value_type лучше typename std::iteratot_traits<T>::value_type, тогда ещё и для массивов будет работать и появится возможность для своих типов-контейнеров внешним образом определять, что за тип элемента в контейнере.

#27

Можно уточнить, а на codeforces сколько заданий из 15 надо сделать?

#28

@pletnev_alexander, вообще говоря – минимум по 2 из каждой темы, но желательно это на практике с преподавателем обсудить.

#29

Почему-то я думала, что для итераторов нет обобщенных типов…

#30

Максим Валентинович, а программку курса можно?

#31

Можно: примерная программа курса. Только смысла в ней особого нет – вопросов в том виде, в котором они будут в билетах, программа не содержит, а знать нужно то, что было на лекциях. Поэтому фразы вида «Этого вопроса не было в программе!» не принимаются.