Многие алгоритмы могут работать с различными типами данных, например, алгоритм поиска максимума или алгоритм сортировки списка. По сути, реализация такого алгоритма для разных типов (например, реализация функции сортировки массива целых чисел, массива действительных чисел и массива строк) будет выглядеть абсолютно одинаково для всех перечисленных типов. То есть алгоритм сортировки является некоторым “обобщенным” алгоритмом, не привязанным к какому-либо конкретному типу.
Язык программирования C++ позволяет создавать такие “обобщенные алгоритмы”, с использованием абстрактного типа, вместо какого-либо конкретного типа. Вот как это можно сделать при помощи популярных функций:
template <typename BaseType> BaseType min(BaseType a, BaseType b) { if (a < b) return a; else return b; } template <typename BaseType> void swap(BaseType & a, BaseType & b) { BaseType tmp = a; a = b; b = tmp; } template <typename BaseType> void sort(BaseType * A, int n) { for (int i = n - 1; i > 0; --i) for (int j = 0; j < i; ++j) if (A[j] < A[j + 1]) swap(A[j], A[j + 1]); }
После этого можно пользоваться указанными функциями для различных типов данных.
Ключевое слово template
означает, что данная функция явлется шаблоном.
После этого в угловых скобках идет описание параметров шаблона. Как правило, это один или несколько
базовых типов, используемых в функции. Описание типа начинается со слова typename
, после которого
идет идентификатор типа. Например, запиcь template <typename BaseType>
обозначает,
что это шаблон от одного базового типа, которому дан идентификаторBaseType
. Этот
идентификатор можно использовать, например, для объявления переменных такого типа внутри функции-шаблона.
Можно также объявлять и структуры данных, являющиеся шаблонами. Например, тип Fraction
можно
сделать структурой, использующую тип int
для представления числителя и знаменателя, а можно использовать
тип long long
- в этом случае дробь будет занимать больше памяти, зато позволит работать с большими числами.
Реализовать шаблон-структуру можно так:
template <typename BaseType> struct Fraction { BaseType a; BaseType b; // Конструктор Fraction(BaseType x = 1, BaseType y = 0) { ... } };
Для объявление переменной типа шаблон-структура нужно явно указать базовый тип вот так:
Fraction<int> P; Fraction<long long> Q;
Несложно понять, что такие структуры данных, как vector
, set
, map
на самом деле являются шаблонами структур. А само название библиотеки STL расшифровывается, как
“Standard Template Library” — стандартная библиотека шаблонов.
Структура Poly
предназначена для представления многочленов и работы
с многочленами. Коэффициенты многочлена могут быть одного из следующих типов:
int
, double
, Fraction
. Коэффициенты
многочлена должны храниться в массиве (векторе) коэффициентов, коэффициент
при \(x^i\) должен храниться в \(i\)-м элементе массива (вектора).
Например, структуру Poly
можно объявить так:
template <typename BaseType> struct Poly { vector<BaseType> coeff; }
Необходимо реализовать следующие конструкторы:
Poly()
- создает нулевой многочлен.
Poly(BaseType a)
- создает многочлен степени 0 со свободным членом \(a\).
Poly(BaseType a, int n)
- создает многочлен степени \(n\) равный \(ax^n\).
Poly(vector<BaseType>> & C)
- создает многочлен по набору коэффициентов.
Необходимо реализовать метод value(BaseType x)
, возвращающий
значение многочлена в точке \(x\).
Необходимо реализовать метод int degree()
, возвращающий степень многочлена.
Степень многочлена, тождественно равного любой константе (в том числе 0) считается равной 0.
Определите операции сложения многочленов и сложения многочлена и числа.
Удобней всего начать с определения операций +=
:
Poly<BaseType> & operator += (Poly<BaseType> &, BaseType); Poly<BaseType> & operator += (Poly<BaseType> &, Poly<BaseType>);
Затем используя эти операции определяется сложение:
Poly<BaseType> operator + (Poly<BaseType>, Poly<BaseType>); Poly<BaseType> operator + (Poly<BaseType>, BaseType); Poly<BaseType> operator + (BaseType, Poly<BaseType>);
Аналогично предыдущему заданию определите операции вычитания.
Определите операции умножения многочленов, операции умножения многочлена на число. В данном случае удобней сначала определить
Poly<BaseType> operator * (Poly<BaseType>, Poly<BaseType>); Poly<BaseType> & operator *= (Poly<BaseType> &, BaseType);
и уже используя их определить
Poly<BaseType> & operator *= (Poly<BaseType> &, Poly<BaseType>); Poly<BaseType> operator * (Poly<BaseType>, BaseType); Poly<BaseType> operator * (BaseType, Poly<BaseType>);
Определите операцию возведение многочлена в целочисленную степень “^”:
Poly<BaseType> operator ^ (Poly<BaseType>, int); Poly<BaseType> & operator ^= (Poly<BaseType> &, int);
При этом:
Определите вывод многочлена в поток типа ostream:
ostream & operator<< (ostream &, Poly<BaseType>);
Правила вывода многочлена следующие:
x^179
.
-2x^3 + 3x^2 - 27x + 1
.
- (3/2)x^5
.
Если коэффициент имеет тип Fraction, но является целым числом, то он выводится как int, то есть без скобок.
При выполнение этого задания необходимо уметь проверять,
является ли переданный в шаблон тип Fraction
.
Для этого нужно определить два шаблона-структуры is_same
следующим образом:
template <typename T, typename U> struct is_same { static const bool value = false; }; template <typename T> struct is_same<T, T> { static const bool value = true; };
После этого проверить, является ли
переданный в шаблон тип T
типом
Fraction
можно так:
if (is_same<T, Fraction>::value)
Для проверки, является ли дробь целым числом,
необходимо опеределить для Fraction
оператор приведения к типу (int)
,
тогда проверку на то, явлется ли дробь F
целой можно так: (int) F == F
.
Оператор (int)
должен переопределяться
в качестве члена класса:
struct Fraction { operator int() { return ...; } }
Необходимо реализовать деление многочленов с остатком.
Операция деления многочленов с остатком
определена только для многочленов с коэффициентами типа int
и
Fraction
(оба многочлена, и делимое,
и делитель должны иметь целочисленные или рациональные коэффициенты).
Действительные числа в качестве коэффициентов не рассматриваются.
Результатом деления (и остатком) всегда явлется многочлен с коэффициентами типа
Fraction
.
Пусть даны два многочлена \(A\) и \(B\). При делении многочлена \(A\) на многочлен \(B\) получается два многочлена \(Q\) (частное) и \(R\) (остаток) такие, что \(A = Q B + R\), при этом \(\deg(R) \lt \deg(B)\). Для нахождения частного и остатка используется алгоритм деления “в столбик”.
Поскольку при делении в столбик сразу же получается и делимое, и делитель, удобно оформить деление в виде функции
void divmod(Poly<Fraction> A, Poly<Fraction> B, Poly<Fraction> & Q, Poly<Fraction> & R);
Затем используя эти функции определите операции деления и взятия остатка
Poly<Fraction> operator / (Poly<S> A, Poly<T> B); Poly<Fraction> operator % (Poly<S> A, Poly<T> B); Poly<Fraction> & operator /= (Poly<Fraction> & A, Poly<T> B); Poly<Fraction> & operator %= (Poly<Fraction> & A, Poly<T> B);
В качестве базовых типов для шаблоном могут быть только int
и Fraction
.
Реализуйте возможность вычисления суперпозиции многочленов, позволяющую делать вызовы типа:
Poly<int> F, G, H; H = F(G);
Для этого необходимо определить operator()
для многочленов. При этом operator()
равно как и оператор приведения типа operator int
должен быть объявлен, как член класса, то есть следующим образом:
template<typename T> struct Poly { Poly<T> operator() (Poly<T> G); };
Для того, чтобы можно было использовать внутри
метода operator()
нужно сначала внутри класса описать
метод operator()
, а реализацию его сделать вне класса:
template<typename T> Poly<T> Poly<T>::operator() (Poly<T> H)
Удобней реализовывать суперпозицию при помощи схемы Горнера.