|
|
| Строка 1: |
Строка 1: |
| − | Семинар 29.01 | + | [[Семинар 29.01 Подгруппа 106-2|Семинар 29.01]]<br> |
| − | | + | [[Семинар 3.02 Подгруппа 106-2|Семинар 3.02]]<br> |
| − | Домашнее задание:
| + | |
| − | | + | |
| − | 1. Реализовать вычисление полинома в точке при помощи схемы Горнера и без нее.
| + | |
| − | Интерфейс алгоритма может быть, например, такой:
| + | |
| − | int CalculatePolynomial(const vector<int>& coefficients, int value);
| + | |
| − | Написать тесты для обоих функций. В стресс тесте можно сравнивать значения полиномов, посчитанные двумя функциями.
| + | |
| − | Сравнить быстродействие алгоритмов при помощи clock() из <ctime>.
| + | |
| − | | + | |
| − | 2. Реализовать быстрое возведение в степень и написать тесты для него.
| + | |
| − | | + | |
| − | 3. Реализовать подсчет k-ой статистики за гарантированное линейное время.
| + | |
| − | Написать тесты.
| + | |
| − | Сравнить быстродействие этого алгоритма с QuickSelect, который вы писали после прошлого семинара.
| + | |
| − | | + | |
| − | Для каждой задачки нужно создать ревью.
| + | |
| − | Тесты и сравнение быстродействия нужно писать в одном ревью. Функция main() в этом случае будет выглядеть примерно так:
| + | |
| − | | + | |
| − | void Test() {
| + | |
| − | CheckManualTests();
| + | |
| − | CheckCornerCases();
| + | |
| − | RunStressTest();
| + | |
| − | }
| + | |
| − | | + | |
| − | void CompareSpeed() {
| + | |
| − | // cout time to run each algorithm.
| + | |
| − | }
| + | |
| − | | + | |
| − | int main() {
| + | |
| − | Test();
| + | |
| − | CompareSpeed();
| + | |
| − | return 0;
| + | |
| − | }
| + | |
| − | | + | |
| − | Семинар 3.02 | + | |
| − | | + | |
| − | Домашнее задание:
| + | |
| − | | + | |
| − | Решить задачу:
| + | |
| − | Алфавит из всех маленьких латинских букв и пробела закодирован числами следующим способом:
| + | |
| − | 'a' -> 1
| + | |
| − | 'b' -> 2
| + | |
| − | 'c' -> 3
| + | |
| − | ...
| + | |
| − | 'z' -> 26
| + | |
| − | ' ' -> 27
| + | |
| − | На вход программы подается строка из цифр. Нужно посчитать, сколькими способами можно раскодировать эту строку.
| + | |
| − | Решить программу нужно при помощи динамического программирования.
| + | |
| − | К решению нужно написать стресс тест, в котором ответ программы, посчитанный при помощи динамического программирования сравнивается с ответом, полученным при помощи рекурсивного brute force решения.
| + | |
| − | Для этого также нужно реализовать рекурсивное решение.
| + | |
| − | Решенную задачу нужно отправить на ревью на адрес a.v.dorogush@gmail.com
| + | |
| − | | + | |
| | [[Семинар 5.02 Подгруппа 106-2|Семинар 5.02]]<br> | | [[Семинар 5.02 Подгруппа 106-2|Семинар 5.02]]<br> |
