Цель: закрепление навыков работы с двумерными массивами на основе std::vector.
Критерии полноты
Данное задание является переносом задачи 5 на средства, предоставляемые Стандартной библиотекой C++, а именно — std::vector.
С помощью std::vector точно так же, как с помощью прямого выделения блоков памяти (динамических массивов), можно реализовать матрицы, используя способ 1 или способ 2. Способ 3 также возможен, но менее удобен и плохо сочетается с тем фактом, что вектор автоматически управляет своим хранилищем.
В качестве примера использования std::vector для работы с матрицами был написан заголовочный файл amatrix2.hpp (HTML), который может считаться заменой C-ориентированному amatrix.hpp, описанному в примерах к задаче 5.
Матрица представлена простейшим способом: как вектор векторов. Для удобства использованы шаблоны синонимов типов. Строка матрицы:
template <class T>
using Matrix_row = std::vector<T>;Собственно матрица (вектор строк):
template <class T>
using Matrix = std::vector<Matrix_row<T>>;Вектор управляет памятью автоматически, поэтому создание, удаление, присваивание матриц упрощается. Стандартная библиотека также определяет операции сравнения, поэтому вместо matrices_are_equal из amatrix.hpp следует использовать == и !=.
В amatrix2.hpp определены функции readln и writeln, позволяющие выполнять текстовый ввод-вывод векторов-строк и матриц (пробелы разделяют значения, переводы строк — строки, пустая строка завершает матрицу).
Для проверки и демонстрации возможностей amatrix2.hpp был написан набор тестов: amatrix2_tests.cpp.
Рекомендуется прочитать оба файла: amatrix2.hpp и amatrix2_tests.cpp и выполнить следующие задания:
В качестве примера выполнен перенос решения примера 2 из задачи 5 на средства, предоставляемые amatrix2.hpp.
Задача. Определить, являются ли строки или столбцы за пределами наибольшей по размеру квадратной угловой подматрицы нулевыми. В случае, если матрица квадратная, возвращать истину. Данному критерию удовлетворяют n×m-матрицы следующего вида (помимо случая n = m):
Решение повторяет таковое из задачи 5. Определим случай (см. иллюстрации выше) в соответствии с соотношением количеств строк и столбцов матрицы. В случае 1 проверим, что все “лишние” строки состоят из нулей. В случае 2 для каждой строки проверим, что “хвост” строки состоит из нулей. Для последнего действия в amatrix2.hpp определена функция consists_of, позволяющая проверить, равны ли все элементы матрицы или строки заданному значению.
/// Определить, являются ли внешние по отношению к квадратной подматрице
/// строки или столбцы нулевыми. Возвращает истину для квадратных матриц.
template <class T>
bool are_outer_lines_zeroes(const Matrix<T> &mtx)
{
const auto r = rows(mtx), c = cols(mtx);
if (r < c)
{
// Строк меньше, чем столбцов -- проверим "хвосты" строк на равенство нулю.
// Длина "хвоста".
const auto diff = c - r;
for (auto &row : mtx)
for (size_t j = diff; j < c; ++j)
if (row[j] != T())
return false;
}
else if (c < r)
{
// Столбцов меньше, чем строк -- проверим "лишние" строки на равенство нулю.
// Вычислим указатель на первую "лишнюю" строку,
// все последующие элементы массива принадлежат "лишним" строкам,
// проверим их на равенство нулю.
const auto diff = r - c;
for (size_t i = diff; i < r; ++i)
if (!consists_of(mtx[i], T()))
return false;
}
// Либо матрица является квадратной, либо проверка в ветках if прошла успешно.
return true;
}
Требуется проверить, удовлетворяет ли матрица следующему условию: в каждом столбце ровно два единичных элемента, остальные элементы — нули.
Разобьём задачу на две проверки:
Эти задачи позволяют выполнить процедурную декомпозицию с выделением процедур (функций), которые можно использовать повторно в других задачах (проверка на 0,1-матрицу и суммирование элементов столбцов).
Функция, проверяющая, является ли матрица 0,1-матрицей, довольно проста: нужно проверить каждый элемент каждой строки (а матрица у нас представлена вектором строк, каждая из которых является вектором элементов).
/// Проверить, является ли матрица 0,1-матрицей.
template <class T>
bool is_01_matrix(const Matrix<T> &m)
{
for (auto &row : m)
for (auto item : row)
if (item != T(0) && item != T(1))
return false;
return true;
}Вычисление постолбцовых сумм будем выполнять построчно. Это удобно и эффективно. Если бы у нас был определён оператор += для сложения строк матриц как математических векторов, то данная задача превратилась бы в обычную задачу о сумме последовательности, так как вектор постолбцовых сумм есть ни что иное как сумма всех строк матрицы.
Есть, впрочем одна особенность. Элементы 0,1-матрицы могут быть типа bool, что делает бессмысленным их суммирование как целых чисел. Поэтому наша функция принимает обязательный тип счётчика S (элемента вектора сумм).
/// Вычислить вектор сумм элементов столбцов матрицы.
/// Некий тип S используется для счётчика вместо собственно типа T, поскольку T может быть булевским.
template <class S, class T>
std::vector<S> row_sum(const Matrix<T> &m)
{
std::vector<S> s;
if (m.empty())
return s;
const auto rsz = m.front().size();
s.resize(rsz);
for (auto &row : m)
{
assert(row.size() == rsz);
for (std::size_t i = 0; i < rsz; ++i)
s[i] += row[i];
}
return s;
}Когда есть две приведённые выше функции, написать функцию, выполняющую проверку матрицы на соответствие критерию, данному в задании, несложно. Это 0,1-матрица, все элементы вектора постолбцовых сумм которой равны 2.
/// Проверить, является ли матрица матрицей инцидентности
/// (0,1-матрицей, в каждом столбце которой ровно две единицы).
template <class T>
bool is_incidence_matrix(const Matrix<T> &m)
{
if (!is_01_matrix(m))
return false;
for (auto item : row_sum<std::size_t>(m))
if (item != 2)
return false;
return true;
}
Диагональной матрицей называют квадратную матрицу (aij), для которой верно aij = 0 при i ≠ j.
Определить, является ли произвольная матрица диагональной.
Симметричной матрицей называют квадратную матрицу (aij), для которой верно aij = aji при всех возможных значениях индексов i и j.
Определить, является ли произвольная матрица симметричной.
Верхнетреугольной матрицей называют квадратную матрицу (aij), для которой верно aij = 0 при i > j.
Определить, является ли произвольная матрица верхнетреугольной.
Кососимметричной матрицей называют квадратную матрицу (aij), для которой верно aij = –aji при всех возможных значениях индексов i и j.
Определить, является ли произвольная матрица кососимметричной.
Нижнетреугольной матрицей называют квадратную матрицу (aij), для которой верно aij = 0 при i < j.
Определить, является ли произвольная матрица нижнетреугольной.
Трёхдиагональной матрицей называют квадратную матрицу (aij), для которой верно aij = 0 при |i – j| > 1.
Определить, является ли произвольная матрица трёхдиагональной.
Матрицей с диагональным преобладанием называют квадратную матрицу (aij), для которой верно 2|aii| > Σj |aij| для всех индексов i.
Определить, обладает ли произвольная матрица свойством диагонального преобладания.
Ортогональной матрицей называют квадратную матрицу (aij), для которой верно ai*·aj* = a*i·a*j = [i = j]. Здесь ai* — i-я строка, а a*i — i-й столбец (как векторы), операция · обозначает скалярное произведение.
Строки (или столбцы) ортогональной матрицы составляют ортонормированный базис (являются попарно перпендикулярными друг другу векторами единичной длины). Транспонирование ортогональной матрицы даёт обратную матрицу.
Определить, является ли произвольная матрица ортогональной. Для этого достаточно проверить попарные скалярные произведения всех строк или всех столбцов (следует выбрать, что использовать — строки или столбцы — из соображений вычислительной эффективности).
Определить, сколько нулевых столбцов содержит матрица. Функция должна возвращать целое число (тип size_t).
Замечание. Данный вариант отличается от прочих тем, что требует не проверки некоего условия, а вычисления значения. Реализовать три теста: с матрицей без нулевых столбцов и с двумя матрицами с несколькими нулевыми столбцами (разное количество нулевых столбцов).
Антидиагональной матрицей называют n×n-матрицу (aij), для которой верно aij = 0 при любых i + j ≠ n – 1, если начинать отсчитывать индексы с нуля. (Ненулевыми могут быть только элементы на побочной диагонали.)
Определить, является ли произвольная матрица антидиагональной.
Персимметричной матрицей называют n×n-матрицу (aij), для которой верно aij = an–j–1,n–i–1 при всех возможных значениях отсчитываемых с нуля индексов i и j.
Пример
1 2 3 4
8 0 5 3
1 6 0 2
7 1 8 1Определить, является ли произвольная матрица персимметричной.
L-матрица — квадратная матрица, диагональные элементы которой строго больше нуля, а все прочие элементы не превосходят нуля.
Определить, является ли произвольная матрица L-матрицей.
Циркулянт — квадратная матрица, j-й столбец (кроме самого левого) которой задаётся циклической перестановкой элементов предыдущего столбца на одну позицию вниз.
Пример
5 3 7 1
1 5 3 7
7 1 5 3
3 7 1 5Определить, является ли произвольная матрица циркулянтом.
Антициркулянт — квадратная матрица, i-я строка (кроме самой верхней) которой задаётся циклической перестановкой элементов предыдущей строки на одну позицию влево.
Пример
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3Определить, является ли произвольная матрица антициркулянтом.
Ведущим элементом ненулевой строки матрицы будем называть самый левый ненулевой элемент этой строки.
Ступенчатой матрицей будем называть матрицу, для которой выполняются следующие условия:
Пример
1 5 0 1 1
0 0 1 2 2
0 0 0 1 1
0 0 0 0 0
0 0 0 0 0Определить, является ли произвольная матрица ступенчатой.
Матрицей Тёплица называют матрицу (не обязательно квадратную), в которой на всех диагоналях, параллельных главной диагонали, стоят равные элементы.
Пример
1 2 3 4 5 6 7
8 1 2 3 4 5 6
9 8 1 2 3 4 5Определить, является ли произвольная матрица матрицей Тёплица.
Матрицей Ганкеля называют квадратную матрицу, в которой на всех диагоналях, параллельных побочной диагонали, стоят равные элементы.
Пример
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
5 6 7 8 9Определить, является ли произвольная матрица матрицей Ганкеля.
Кувшинов Д.Р. © 2016