Алгоритмы и структуры данных. Подгруппа 106-2 — различия между версиями
(Новая страница: «Семинар 29.01 Домашнее задание: 1. Реализовать вычисление полинома в точке при помощи схемы…») |
|||
Строка 1: | Строка 1: | ||
Семинар 29.01 | Семинар 29.01 | ||
+ | |||
Домашнее задание: | Домашнее задание: | ||
+ | |||
1. Реализовать вычисление полинома в точке при помощи схемы Горнера и без нее. | 1. Реализовать вычисление полинома в точке при помощи схемы Горнера и без нее. | ||
Интерфейс алгоритма может быть, например, такой: | Интерфейс алгоритма может быть, например, такой: | ||
− | double CalculatePolynomial(const vector<double>& coefficients, double value); | + | double CalculatePolynomial(const vector<double>& coefficients, double value); |
Написать тесты для обоих функций. В стресс тесте можно сравнивать значения полиномов, посчитанные двумя функциями. | Написать тесты для обоих функций. В стресс тесте можно сравнивать значения полиномов, посчитанные двумя функциями. | ||
Сравнить быстродействие алгоритмов при помощи clock() из <ctime>. | Сравнить быстродействие алгоритмов при помощи clock() из <ctime>. |
Версия 12:51, 30 января 2015
Семинар 29.01
Домашнее задание:
1. Реализовать вычисление полинома в точке при помощи схемы Горнера и без нее. Интерфейс алгоритма может быть, например, такой:
double CalculatePolynomial(const vector<double>& coefficients, double 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; }