Многие алгоритмы могут работать с различными типами данных, например, алгоритм поиска максимума или алгоритм сортировки списка. По сути, реализация такого алгоритма для разных типов (например, реализация функции сортировки массива целых чисел, массива действительных чисел и массива строк) будет выглядеть абсолютно одинаково для всех перечисленных типов. То есть алгоритм сортировки является некоторым “обобщенным” алгоритмом, не привязанным к какому-либо конкретному типу.
Язык программирования 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)
Удобней реализовывать суперпозицию при помощи схемы Горнера.