/*
** Класс "матрица"
** Слава Антонов (с) 2003
*/
//----------------------------------------------------------------------------
#ifndef MATRIX_H
#define MATRIX_H
#include
typedef long double tableitem;
// класс "строка вещественных чисел"
// по умолчанию все элементы - нулевые
class CRow {
protected:
unsigned size; // кол-во элементов
tableitem *items; // массив элементов
public:
// конструктор по умолчанию
CRow();
// конструктор копирования
CRow(const CRow& r);
// конструктор с заданным размером
CRow(unsigned uSize);
// деструктор
~CRow();
// обнуление всех элементов
void zero_items();
// кол-во элементов
unsigned getSize() const { return size; }
// изменение размера столбца, старые значения сохр, новые = 0
CRow& setSize(unsigned uSize);
// оператор [], индекс от нуля
tableitem& operator [](unsigned uIndex);
const tableitem& operator [](unsigned uIndex) const;
// оператор вывода
friend ostream& operator << (ostream& s, CRow& r);
// оператор ввода
friend istream& operator >> (istream& s, CRow& r);
// оператор присваивания
CRow& operator = (const CRow& r);
};
class CVector : public CRow {
protected:
public:
CVector() : CRow () {};
CVector(const CVector& v) : CRow(v) {};
CVector(unsigned uSize) : CRow(uSize) {};
// сумма векторов
CVector operator +(const CVector &v) const;
CVector operator -(const CVector &v) const;
// скалярное произведение векторов
tableitem operator * (const CVector& v);
// умножение вектора на скаляр
friend CVector operator * (tableitem s, const CVector &v);
// оператор присваивания
CVector& operator = (const CRow& r);
};
/* Класс "Таблица"
** Можно динамачески менять размеры.
** При этом старые значения сохраняются.
** Поддерживаются операторы: <<, >>, =
*/
class CTable {
protected:
// массив строк
CVector *items;
// ширина и высота таблицы
unsigned width;
unsigned height;
public:
CTable();
CTable(const CTable& t);
CTable(unsigned uHeight, unsigned uWidth);
~CTable();
unsigned getWidth() const { return width; }
unsigned getHeight() const { return height; }
// изменить размеры таблицы
CTable& setSize(unsigned uHeight, unsigned uWidth);
/*
// поиск элемента с указанным значением в прямоугольнике с указанной лев. верней вершиной до конца таблицы
// возвращаеются его координаты если он есть.
// match - искать равный элемент или отличный от указанного
// результат функции 0 - не найнен, не 0 - найден
*/
int search(tableitem what, bool match, unsigned &uI, unsigned &uJ, unsigned starti = 0, unsigned startj = 0) const;
// меняет два столбца местами
CTable& swapcolumns(unsigned j1, unsigned j2);
// меняет две строки местами
CTable& swaprows(unsigned i1, unsigned i2);
// оператор доступа [], индекс от нуля
CVector& operator [](unsigned uIndex);
const CVector& operator [](unsigned uIndex) const;
// оператор вывода
friend ostream& operator << (ostream& s, CTable& t);
// оператор ввода. сработает только если таблица
// имеет не нулевые размеры
friend istream& operator >> (istream& s, CTable& t);
// оператор присваивания
CTable& operator = (const CTable& t);
};
// класс "Матрица", наследник класса "Таблица"
class CMatrix: public CTable {
private:
public:
// вызывает конструктор базового класса
CMatrix() : CTable() {};
CMatrix(const CMatrix& m) : CTable(m) {};
CMatrix(unsigned uHeight, unsigned uWidth) : CTable(uHeight, uWidth) {};
// ~CMatrix() : ~CTable() {};
// определитель матрицы
tableitem determinant() const;
// ранг матрицы. 0 - если ошибка
unsigned rang() const;
// возврашает матрицу полученную из исходной вычеркиванием i-ой строки
// и j-го столбца
CMatrix minor (unsigned i, unsigned j) const;
// транспонирование матрицы
CMatrix& transpon();
// сложение матриц
CMatrix operator +(const CMatrix &m) const;
// вычитание матриц
CMatrix operator -(const CMatrix &m) const;
// умножение матриц
CMatrix operator * (const CMatrix &m) const;
// обращение матрицы
CMatrix operator ! () const;
// умножение матрицы на вектор
friend CVector operator * (const CMatrix &m, const CVector &v);
// умножение матрицы на скаляр
friend CMatrix operator * (const tableitem &scalar, const CMatrix &m);
};
#endif
#include "matrix.h"
#include
#include
#include
//----------------------------------------------------------------------------
// конструктор по умолчанию
CRow::CRow() {
size = 0;
items = 0;
};
//----------------------------------------------------------------------------
// конструктор копирования
CRow::CRow(const CRow& r) {
size = r.size;
items = new tableitem[size];
for (unsigned i = 0; i < size; i++)
items[i] = r.items[i];
};
//----------------------------------------------------------------------------
// конструктор с заданным размером
CRow::CRow(unsigned uSize) {
size = uSize;
items = new tableitem[size];
zero_items();
};
//----------------------------------------------------------------------------
// деструктор
CRow::~CRow() {
if (size != 0) delete []items;
};
//----------------------------------------------------------------------------
// обнуление всех элементов
void CRow::zero_items() {
for (unsigned i = 0; i < size; i++)
items[i] = 0;
};
//----------------------------------------------------------------------------
// изменение размера, старые значения сохр, новые = 0
CRow& CRow::setSize(unsigned uSize) {
if (uSize == size) return *this;
tableitem *tmp = 0;
if (uSize > 0) tmp = new tableitem[uSize];
for (unsigned i = 0; i < uSize; i++)
if (i < size) tmp[i] = items[i];
else tmp[i] = 0;
if (size != 0) delete []items;
items = tmp;
size = uSize;
return *this;
};
//----------------------------------------------------------------------------
// оператор доступа к элементу
tableitem& CRow::operator [](unsigned uIndex) {
return items[uIndex];
};
const tableitem& CRow::operator [](unsigned uIndex) const {
return items[uIndex];
};
//----------------------------------------------------------------------------
// оператор вывода
ostream& operator << (ostream& s, CRow& r) {
for (unsigned i = 0; i < r.size; i++) {
s.width(10);
s.right;
s << r.items[i];
}
return s;
};
// оператор ввода
istream& operator >> (istream& s, CRow& r) {
tableitem tmp;
for (unsigned i = 0; i < r.size; i++) {
cout << endl << "Enter item [" << i << "] = ";
s >> tmp;
r.items[i] = tmp;
s.ignore();
}
return s;
};
//----------------------------------------------------------------------------
// оператор присваивания
CRow& CRow::operator = (const CRow& r) {
setSize(r.size);
for (unsigned x = 0; x < size; x++)
items[x] = r.items[x];
return *this;
};
/*
// Реализация методов Вектора
*/
// сумма векторов
CVector CVector::operator +(const CVector &v) const
{
CVector res(*this);
for (unsigned i = 0; i < res.size; i++)
res[i] = res[i] + v[i];
return res;
}
CVector CVector::operator -(const CVector &v) const
{
CVector res(*this);
for (unsigned i = 0; i < res.size; i++)
res[i] = res[i] - v[i];
return res;
}
// скалярное произведение векторов
tableitem CVector::operator * (const CVector& v) {
tableitem res = 0;
if (size != v.size) return 0;
for (unsigned i = 0; i < size; i++)
res += items[i] * v.items[i];
return res;
};
// умножение вектора на скаляр
CVector operator * (tableitem s, const CVector &v) {
CVector nv(v.size);
for (unsigned i = 0; i < v.size; i++)
nv[i] = v[i]*s;
return nv;
};
// оператор присвоения
CVector& CVector::operator = (const CRow& r) {
setSize(r.getSize());
for (unsigned i = 0; i < size; i++)
items[i] = r[i];
return *this;
};
//----------------------------------------------------------------------------
// конструктор по умолчанию
CTable::CTable() {
width = 0;
height = 0;
items = 0;
};
//----------------------------------------------------------------------------
// конструктор копирования
CTable::CTable(const CTable& t) {
width = t.width;
height = t.height;
items = new CVector[height];
for (unsigned x = 0; x < height; x++) {
items[x].setSize(width);
for (unsigned y = 0; y < width; y++)
items[x][y] = t.items[x][y];
}
};
//----------------------------------------------------------------------------
CTable::CTable(unsigned uHeight, unsigned uWidth) {
width = uWidth;
height = uHeight;
items = new CVector[height];
for (unsigned x = 0; x < height; x++)
items[x].setSize(width);
};
//----------------------------------------------------------------------------
// деструктор
CTable::~CTable() {
if (height != 0) delete []items;
};
//----------------------------------------------------------------------------
// изменить ширину таблицы
CTable& CTable::setSize(unsigned uHeight, unsigned uWidth) {
if ((width == uWidth) && (height == uHeight)) return *this;
CVector *tmp = 0;
// create table
if (uHeight) tmp = new CVector[uHeight];
// copy old values
for (unsigned x = 0; x < uHeight; x++) {
tmp[x].setSize(uWidth);
for (unsigned y = 0; y < uWidth; y++)
if ((x < height) && (y < width)) tmp[x][y] = items[x][y];
else tmp[x][y] = 0;
}
if (height != 0) delete []items;
items = tmp;
width = uWidth;
height = uHeight;
return *this;
};
//----------------------------------------------------------------------------
/*
// поиск элемента с указанным значением
// возвращаеются его координаты если он есть.
// match - искать равный элемент или отличный от указанного
// результат функции 0 - не найнен, не 0 - найден
*/
int CTable::search(tableitem what, bool match, unsigned &uI, unsigned &uJ, unsigned starti, unsigned startj) const {
if ((!width) || (!height)) return 0;
if ((starti >= height) || (startj >= width)) return 0;
for (unsigned i = starti; i < height; i++)
for (unsigned j = startj; j < width; j++)
if (match == true) {
if (items[i][i] == what) {
uI = i;
uJ = j;
return 1;
}
}
else
if (items[i][j] != what) {
uI = i;
uJ = j;
return 1;
}
return 0;
}; // CTable::search()
//----------------------------------------------------------------------------
// меняет два столбца местами
CTable& CTable::swapcolumns(unsigned x1, unsigned x2) {
if ((x1 >= width) || (x2 >= width) || (x1 == x2)) return *this;
tableitem tmp;
for (unsigned x = 0; x < height; x++) {
tmp = items[x][x1];
items[x][x1] = items[x][x2];
items[x][x2] = tmp;
}
return *this;
}; // swarcolumns()
//----------------------------------------------------------------------------
// меняет две строки местами
CTable& CTable::swaprows(unsigned i1, unsigned i2) {
if ((i1 >= height) || (i2 >= height) || (i1 == i2)) return *this;
CRow tmp = items[i1];
items[i1] = items[i2];
items[i2] = tmp;
return *this;
}; // swaprows()
//----------------------------------------------------------------------------
// оператор доступа [], индекс от нуля
CVector& CTable::operator [](unsigned uIndex) {
return items[uIndex];
};
const CVector& CTable::operator [](unsigned uIndex) const{
return items[uIndex];
};
//----------------------------------------------------------------------------
// оператор вывода
ostream& operator << (ostream& s, CTable& t) {
for (unsigned i = 0; i < t.height; i++) {
for (unsigned j = 0; j < t.width; j++) {
s.width(10);
s.right;
s << t.items[i][j];
}
s << endl;
}
return s;
};
//----------------------------------------------------------------------------
// оператор ввода. сработает только если таблица
// имеет не нулевые размеры
istream& operator >> (istream& s, CTable& t) {
if ((t.width == 0) || (t.height == 0)) return s;
for (unsigned i = 0; i < t.height; i++)
for (unsigned j = 0; j < t.width; j++) {
cout << endl << "Enter item[" << i << ", " << j << "] = ";
s >> t.items[i][j];
}
if (s.peek() == '\n') s.ignore();
return s;
};
//----------------------------------------------------------------------------
// оператор присваивания
CTable& CTable::operator = (const CTable& t) {
setSize(t.width, t.height);
for (unsigned i = 0; i < height; i++)
items[i] = t.items[i];
// for (unsigned i = 0; i < width; i++)
// for (unsigned y = 0; y < height; y++)
// items[x][y] = t.items[x][y];
return *this;
};
/*
** Реализация методов класса "Матрица
*/
//----------------------------------------------------------------------------
// Вычисление определителя квадратной матрицы
tableitem CMatrix::determinant() const {
/* TODO : Обработка ошибки */
if (width != height) return 0;
if (width == 0) return 0;
CMatrix m = *this;
if (width == 1) return m[0][0];
if (width == 2)
return (m[0][0] * m[1][1] - m[1][0] * m[0][1]);
// смена знака определителя. по умолчанию - нет
bool sign = false;
// определитель
tableitem det = 1;
tableitem tmp;
unsigned x, y;
// цикл по всей главной диагонали
for(unsigned i = 0; i < height; i++) {
// если элемент на диагонали равен 0, то ищем не нулевой элемент в матрице
if (m[i][i] == 0) {
// если все элементы нулевые, то опр. = 0
if (!m.search(0, false, y, x, i, i)) return 0;
// меняем i-ую строку с y-ой
if (i != y) {
m.swaprows(i, y);
sign = !sign;
}
// меняем i-ый столбец с x-ым
if (i != x) {
m.swapcolumns(i, x);
sign = !sign;
}
// таким образом, в m[i][i], теперь ненулевой элемент.
}
// выносим элемент m[i][i] за определитель
det *= m[i][i];
tmp = m[i][i];
for (x = i; x < width; x++) {
m[i][x] = m[i][x] / tmp;
}
// таким образом m[i][i] теперь равен 1
// зануляем все элементы стоящие под (i, i)-ым,
// при помощи вычитания с опр. коеффициентом
for (y = i + 1; y < height; y++) {
tmp = m[y][i];
for (x = i; x < width; x++)
m[y][x] -= (m[i][x]*tmp);
}
}
if (sign) return det*(-1);
return det;
}; // CMatrix::determinant()
//----------------------------------------------------------------------------
// вычисление ранга матрицы
unsigned CMatrix::rang() const {
if (!width || !height) return 0;
CMatrix m = *this;
if (width == 1) return 1;
tableitem tmp;
unsigned i;
unsigned x, y;
// выбираем минимум
unsigned endi = (width > height)? height : width;
// цикл по всей главной диагонали
for(i = 0; i < endi; i++) {
// если элемент на диагонали равен 0, то ищем не нулевой элемент в матрице
if (m[i][i] == 0) {
// если все элементы нулевые, прерываем цикл
if (!m.search(0, false, y, x, i, i)) break;
// меняем i-ую строку с y-ой
if (i != y) m.swaprows(i, y);
// меняем i-ый столбец с x-ым
if (i != x) m.swapcolumns(i, x);
// таким образом, в m[i][i], теперь ненулевой элемент.
}
// выносим элемент m[i][i]
tmp = m[i][i];
for (x = i; x < width; x++) {
m[i][x] = m[i][x] / tmp;
}
// таким образом m[i][i] теперь равен 1
// зануляем все элементы стоящие под (i, i)-ым и справа от него,
// при помощи вычитания с опр. коеффициентом
for (y = i + 1; y < height; y++) {
tmp = m[y][i];
for (x = i; x < width; x++)
m[y][x] -= (m[i][x]*tmp);
}
for (x = i + 1; x < width; x++) {
tmp = m[i][x];
for (y = i; y < height; y++)
m[y][x] -= (m[y][i]*tmp);
}
}
// считаем сколько единичек на главной диагонали
unsigned cnt = 0;
for (i = 0; i < endi; i++)
if (m[i][i] == 0) break;
else cnt++;
if (!cnt) cnt++;
return cnt;
}; // rang()
// возврашает матрицу полученную из исходной вычеркиванием i-ой строки
// и j-го столбца
CMatrix CMatrix::minor (unsigned i, unsigned j) const
{
if ((i >= this->width) || (j >= this->height)) return *this;
CMatrix M(this->height-1, this->width-1);
if ((!M.width) || (!M.height)) return M;
unsigned i1, j1;
for (unsigned i2 = 0; i2 < M.height; i2++)
for (unsigned j2 =0; j2 < M.width; j2++)
{
if (i2 < i) i1 = i2;
else i1 = i2 + 1;
if (j2 < j) j1 = j2;
else j1 = j2 + 1;
M[i2][j2] = this->operator[](i1)[j1];
}
return M;
}
// транспонирование матрицы
CMatrix& CMatrix::transpon() {
if (!width || !height) return *this;
CMatrix &m = *this;
CMatrix m2(height, width);
for (unsigned x = 0; x < width; x++)
for (unsigned y = x + 1; y < height; y++)
m2[y][x] = m[x][y];
m = m2;
return *this;
};
/*
** сложение матриц
*/
CMatrix CMatrix::operator +(const CMatrix &m) const
{
CMatrix nm(m);
if (!this->width || !this->height || !m.width || !m.height) return *this;
if ((this->width != m.width) || (this->height != m.height)) return *this;
nm.setSize(this->height, this->width);
for (unsigned i = 0; i < this->height; i++)
for (unsigned j = 0; j < this->width; j++)
nm[i][j] = ((nm[i][j]) + (this->operator[](i)[j]));
return nm;
}
// вычитание матриц
CMatrix CMatrix::operator -(const CMatrix &m) const
{
CMatrix nm(m);
if (!this->width || !this->height || !m.width || !m.height) return *this;
if ((this->width != m.width) || (this->height != m.height)) return *this;
nm.setSize(this->height, this->width);
for (unsigned i = 0; i < this->height; i++)
for (unsigned j = 0; j < this->width; j++)
nm[i][j] = ((this->operator[](i)[j]) - (nm[i][j]));
return nm;
}
// обращение матрицы
CMatrix CMatrix::operator ! () const
{
CMatrix A(*this);
if (!A.getWidth() || !A.getHeight()) return A;
if (!A.determinant()) return A;
CMatrix Inv(A.getHeight(), A.getHeight());
tableitem tmp;
unsigned i, j;
unsigned x, y;
for (i = 0; i < Inv.getHeight(); i++)
Inv[i][i] = 1;
for (unsigned i = 0; i < A.getHeight(); i++)
{
if (A[i][i] == 0) {
// если все элементы нулевые, прерываем цикл
if (!A.search(0, false, y, x, i, i)) break;
// меняем i-ую строку с y-ой
if (i != y)
{
A.swaprows(i, y);
Inv.swaprows(i, y);
}
// меняем i-ый столбец с x-ым
if (i != x)
{
A.swapcolumns(i, x);
Inv.swapcolumns(i, x);
}
// таким образом, в A[i][i], теперь ненулевой элемент.
}
// выносим элемент A[i][i]
tmp = A[i][i];
for (x = 0; x < width; x++)
{
A[i][x] = A[i][x] / tmp;
Inv[i][x] = Inv[i][x] / tmp;
}
// таким образом A[i][i] теперь равен 1
// зануляем все элементы стоящие под и над (i, i)-ым
// при помощи вычитания с опр. коеффициентом
for (y = 0; y < height; y++)
{
if (y == i) continue;
tmp = A[y][i];
for (x = 0; x < width; x++)
{
A[y][x] -= (A[i][x]*tmp);
Inv[y][x] -= (Inv[i][x]*tmp);
}
}
}
return Inv;
}
// умножение матриц
CMatrix CMatrix::operator * (const CMatrix &m) const {
CMatrix nm;
unsigned w, h;
if (!this->width || !this->height || !m.width || !m.height) return nm;
if (this->width != m.height) return nm;
nm.setSize(this->height, m.width);
h = nm.height;
w = nm.width;
tableitem item;
for (unsigned i = 0; i < h; i++)
for (unsigned j = 0; j < w; j++) {
item = 0;
for (unsigned k = 0; k < this->width; k++)
item += this->operator[](i)[k] * m[k][j];
nm[i][j] = item;
}
return nm;
};
// умножение матрицы на вектор
CVector operator * (const CMatrix &m, const CVector &v)
{
CVector nv;
if (!m.getWidth() || !m.getHeight() || (m.getWidth() != v.getSize()));
unsigned w = m.getWidth();
unsigned h = m.getHeight();
nv.setSize(h);
tableitem item;
for (unsigned i = 0; i < h; i++) {
item = 0;
for (unsigned k = 0; k < w; k++)
item += m[i][k]*v[k];
nv[i] = item;
}
return nv;
};
// умножение матрицы на скаляр
CMatrix operator * (const tableitem &scalar, const CMatrix &m)
{
CMatrix nm(m);
for (unsigned i = 0; i < nm.height; i++)
for (unsigned j = 0; j < nm.width; j++)
nm[i][j] = scalar * nm[i][j];
return nm;
}
