Алгоритмы и структуры данных. Подгруппа 106-2 — различия между версиями
Строка 33: | Строка 33: | ||
return 0; | return 0; | ||
} | } | ||
+ | |||
+ | Семинар 3.02 | ||
+ | |||
+ | Домашнее задание: | ||
+ | |||
+ | Решить задачу: | ||
+ | Алфавит из всех маленьких латинских букв и пробела закодирован числами следующим способом: | ||
+ | 'a' -> 1 | ||
+ | 'b' -> 2 | ||
+ | 'c' -> 3 | ||
+ | ... | ||
+ | 'z' -> 26 | ||
+ | ' ' -> 27 | ||
+ | На вход программы подается строка из цифр. Нужно посчитать, сколькими способами можно раскодировать эту строку. | ||
+ | Решить программу нужно при помощи динамического программирования. | ||
+ | К решению нужно написать стресс тест, в котором ответ программы, посчитанный при помощи динамического программирования сравнивается с ответом, полученным при помощи рекурсивного brute force решения. | ||
+ | Для этого также нужно реализовать рекурсивное решение. | ||
+ | Решенную задачу нужно отправить на ревью на адрес a.v.dorogush@gmail.com |
Версия 15:34, 4 февраля 2015
Семинар 29.01
Домашнее задание:
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