Внимание! Об обновлениях смотри внизу этой страницы. Последнее обновление – от 18.04.2018.
Введение
Класс DMatrix разработан на языке C++ (в среде Borl a nd Builder 6) и предназначен для встраивания в исходный код с целью упрощения программирования операций с матрицами.
Класс позволяет использовать при программировании переопределенные операции: присвоение, сложение матриц, умножение матриц, умножение матрицы на число (справа). Например, код C++, использующий объекты данного класса, может выглядеть так:
A = B;
A = B + C;
A = B * C;
A = B * c;
где A , B и C – объекты класса, с – переменная типа float , double или long double .
Кроме того, класс содержит функции обращения матрицы, вычисления определителя и транспонирования:
A = B. Inverse (); -обращение матрицы B ;
d = B . det ( ); -вычисление определителя матрицы B ;
A = B. T ( ); -транспонирование матрицы B .
Значения ячеек матрицы имеют тип long double , что позволяет производить операции с большой точностью. В некоторых достаточно сложных прикладных задачах, построенных на итеративных алгоритмах, увеличение точности вычислений приводит к ускорению сходимости алгоритма, то есть даже ускоряет работу программы.
Важное преимущество нашего класса заключается в реализации подхода «динамическая матрица».
В прикладных задачах, связанных с обработкой потоков информации, встает задача оперативного формирования матриц на основе данных (сигналов), поступающих по нескольким каналам. При этом, во-первых, данные не должны пропадать из-за нехватки времени, они должны без временных задержек наполнять матрицы, позволяя математическому алгоритму быстро приступать к их обработке. Во-вторых, память компьютера должна использоваться рационально, чтобы избежать переполнения памяти при больших потоках информации.
Объект класса DMatrix можно изобразить в виде стакана:
Матрица, хранящаяся в данном объекте, имеет размерность m*n . Как правило, в случае работы с потоком данных число n – это количество переменных, содержащихся в потоке, и/или каких-то рассчитанных величин, например, производных по времени от переменных потока.
Рациональное использование памяти при работе с динамической матрицей подразумевает динамическое выделение памяти для строк матрицы (низ стакана) и динамическое освобождение памяти от использованных строк (верх стакана).
При операциях с матрицами, таких, как сложение, умножение, вычисление определителя и др., обработке подвергаются только актуальные данные, для указания на которые служит переменная k.
При обработке сигналов от устройств часто возникают задача формирования и решения в реальном времени систем уравнений. Для этой цели сделаны классы LSM и PROJECTION, работающие с нашими динамическими матрицами. В них реализованы алгоритмы решения систем линейных алгебраических уравнений с гибкой системой настройки параметров. Алгоритмы базируются на методе наименьших квадратов с «коэффициентом экспоненциального забывания» и проекционном решающем алгоритме. Настройки этих алгоритмов позволяют адаптировать их как для чистки входящих сигналов, так и для быстрого реагирования решения на скачки сигналов на входе. Таким образом, программист (или эксплуатант), подбирая эти настройки, должен найти оптимальный баланс между точностью решения и быстротой реагирования.
Переменные и функции класса DMatrix
Класс содержит переменные:
int m ; - количество строк матрицы
int n ; - количество столбцов матрицы
int k; - указатель на последнюю строку матрицы. При операциях в качестве актуальных строк матрицы используются строки массива с индексами(k-m), … , (k -1).
int M; - количество указателей на строки матрицы
long double **data; - указатель на двумерный массив значений ячеек матрицы
booloblom; - признак аварийного результата выполнения операции
Класс содержит функции:
long double __ fastcall det ( void ); - расчет определителя матрицы
DMatrix __ fastcall T ( void ); - транспонирование матрицы
DMatrix __ fastcall Inverse ( void ); - расчет обратной матрицы
void __ fastcall Ini ( m 0, n 0, M 0, k 0); - инициализация переменных объекта-матрицы и выделение памяти
void __ fastcall de _ allocate ( void ); - чистка памяти: удаление m строк матрицы из диапазона (k-m), … , (k -1) и указателей наэти строки
void __ fastcall Allocate ( int k 0); - выделение памяти для указанной строки
void __ fastcall Delete ( int k 0); - чистка памяти: удаление указанной строки
Работа с матрицами
Пример 1.
Рассмотрим простейший пример – сложение двух матриц:
Сначала нужно добавить в проект наш класс. Если используется среда Borland Builder , то необходимо добавить в проект файл dmatrix . cpp и подключить его в unit ’е, в котором мы будем работать с матрицами; для этого напишем в header -файле директиву#include " d matrix.h " .
Добавим на форму кнопку Button 1 и надпись Label1. В функцию Button1Click поместим следующий код.
Объявим 3 матрицы:
DMatrixA, B, C; (слагаемые и результат, C = A + B ),
опишем свойства этих матриц и выделим память для строк и столбцов матриц:
A.m = 2;
A.n = 2;
A.k = 2;
A.M = 2;
A.oblom = false;
A.data = new long double*;
for (inti = 0; i < A.k; i++)A.data[i] = new long double;
То же самое можно написать более компактным образом, с помощью функции Ini:
A . Ini (2, 2, 2, 2);
В результате выполнения функции Ini (m 0, n 0, M 0, k 0) задаются значения переменных A.m, A.n, A.M, A.k, выделяется память для A.M указателей на строки и выделяется память для A.k строк.
Примечание по работе Ini :
Иногда нет смысла сразу выделять память под строки. В этом случае можно написать:A.Ini(2, 2, 2).После выполнения функции Ini с тремя аргументами будет присвоено A.k = 0, о чем не стоит забывать, т.к. A.k = 0 указывает на матрицу из 0 строк; если мы хотим указать на матрицу из A.m строк, то A.k должен быть не меньше A . m .
Можно также сделать двухместный вызов этой функции:A.Ini(2, 2), в этом случае не будет выделена память для указателей на строки и будет присвоено A. M = 0.
Так же поступим с матрицами B и C :
B . Ini (2, 2, 2, 2);
C . Ini (2, 2, 2, 2);
Зададим значения ячеек матриц A и B:
A.data = 1;
A.data = 2;
A.data = 3;
A.data = 4;
B.data = 5;
B.data = 6;
B . data = 7;
B . data = 8;
и, наконец, сложим матрицы:
C = A + B ;
В результате сложения в массиве C.data появится требуемый результат, который можно вывести на экран. Например:
Label 1-> Caption = FloatToStr ( C . data ); - на форме отобразится значение ячейки (1-я строка, 1-й столбец), равное 6.
После получения результата и его выгрузки освободим память:
if(A.data)A.de_allocate();
if(B.data)B.de_allocate();
if(C.data)C.de_allocate();
Важное замечание по поводу работы функции de_allocate():эта функция удаляет только строки в диапазоне (k-m), … , (k -1)(имеются в виду индексы массива data в C++ коде, то есть нумерация идет с 0). То есть «рабочую» часть нашего стакана.Перед запуском de_allocate() надо быть уверенным, что все прочие строки, лежащие вне данного диапазона, были удалены ранее. В нашем примере k = m, поэтому функцию выполнять можно; вопрос постепенного удаления «отслуживших» строк рассмотрим в следующем примере.
Исходный код рассмотренного примера – .
Пример 2.
Предположим, что требуется оценивать некоторую характеристику потока измерений, поступающих в компьютер с внешних устройств. Например, это данные с N датчиков.
В каждый момент времени имеем N значений, из которых можно составить строку матрицы, то есть можно сказать, что на вход приходят строки. Пусть характеристика, которую надо вычислять – детерминант. Для того, чтобы его вычислить, нам нужно иметь N строк, т.к. матрица должна быть квадратной.
Опишем матрицу и выделим память (только для указателей на строки):
X . Ini ( N , N , 10000);// Не указали значение k - не выделилось место под строки
X . k = 1;
while ( X . k <= X . M )
{
X . Allocate ( X . k - 1);// Выделяем память для строки
if ( X . k > X . m ) X . Delete ( X . k - X . m - 1);// Удаляем последнюю использованную, но пока не удаленную строку
// Заполняем новую строку (симуляция сигналов)
for(i = 0; i < N; i++)
X.data[i] = (((rand() % RAND_MAX)+1.0)/RAND_MAX);// Равномерно распределенная на случайная величина
if ( X . k >= X . m ) det = X . det ();// Появилось m строк - можно считать определитель
X . k ++;
}
Полный текст пр ограммы - . В исходном коде добавлено умножение матрицы на себя, дискриминант берется от матрицы-произведения. Отображение результатов на форме сделано с помощью таймера.
Исходя из значения X.M можно оценить, сколько раз в секунду Ваш компьютер находит значение определителя матрицы размера N * N (всего определитель вычисляется (X.M- N +1) раз). Увеличивая размер матрицы, можно получить представление о возможностях алгоритма.
Важное замечание: в этом примере мы освобождали и выделяли память для строк на каждом шаге. Для повышения быстродействия иногда имеет смысл перераспределять память с интервалом в несколько шагов, большими кусками. То есть через несколько шагов добавлять / удалять сразу по несколько строк матрицы.
Так как функция de_allocate() освобождает память от строк с индексами из диапазона(k-m), … , (k -1), важно перед запуском функции указать правильное значение k. Для этого в исходном коде после главного цикла указано:X.k--; , чтобы сбросить последнее увеличение X.k на единицу.
Динамическая идентификация состояния системы
Для демонстрации возможностей работы с классом предлагается пример (с исходниками) .
При запуске программы (matrix.exe) открывается форма, на которой можно задавать матрицы и производить простейшие операции с ними. В исходном тексте можно увидеть, каким образом используется наш класс при программировании на C++.
При нажатии на кнопку «Динамические операции» открывается форма для решения следующей задачи.
Пусть у нас есть 4 сигнала, поступающих на вход:X 1 , X 2 , X 3 и Y . Мы предполагаем, что эти 4 переменные связаны между собой линейным уравнением:
C 1 * X 1 + C 2 * X 2 + C 3 * X 3 = Y
В качестве одного или нескольких входных параметров может использоваться как физический сигнал, так и расчетные величины, например, производные или отфильтрованные данные.
Требуется оценить в каждый момент времени коэффициенты состояния системы C 1 , C 2 , C 3 , то есть решить уравнение относительно C i .
В идеальных условиях, при отсутствии шума и при постоянных X 1 , X 2 , X 3 и Y в каждый момент времени мы получаем одно и то же уравнение, имеющее бесконечное множество решений. На практике мы имеем шум и изменяющиеся значения сигналов, в результате чего получается система из большого количества несовместных уравнений.
Для приближенного решения несовместной системы существует несколько вычислительных подходов; в нашей программе реализована комбинация 2-х методов:МНК (Метод наименьших квадратов) с «коэффициентом экспоненциального забывания» и обобщенный проекционный алгоритм.
Использование подхода МНК обусловлено необходимостью получения на каждом шаге невырожденной матрицы для последующего решения системы уравнений проекционным алгоритмом. Для увеличения гибкости настройки вводится коэффициент экспоненциального забывания W 2 , смысл которого состоит в усреднении вновь полученной методом МНК системы с аналогичной системой, полученной на предыдущем шаге. Чем больше значение W 2 , тем больший вес имеют предыдущие значения. Коэффициент принадлежит интервалу ;
Если процесс – единственный, этого делать не надо, по умолчанию Thr = 0.
То же касается и инициализации объектов LSM и PROJECTION. В этих классах в функциях инициализации добавлена еще одна переменная (по умолчанию также равная 0):
LSMLsm;
Lsm .Ini (…, …, [ номер процесса ]);
PROJECTIONProjection ;
Projection . Ini 0(…, [номер процесса]);
Все исходники, доступные к скачиванию с данной страницы, обновлены с учетом этих изменений.
Объявление двумерного массива в СИ имеет следующий синтаксис:тип имя[размер №1][размер №2];
Размеры двумерного массива в СИ указываются в отдельных парных квадратных скобках после имени и могут быть любыми положительными целочисленными значениями. На практике принято значение первой размерности называть строками, а второй – столбцами. Как и в случае одномерного массива, в стандарте С89 регламентируется, что размеры двумерного массива должны быть целочисленными константами.
Стандарт С99 допускает объявление динамических двумерных массивов путём использования выражений при указании размеров матрицы, если в это выражение входят значения определенных ранее переменных (выражение должно иметь положительный целочисленный результат). Например:
int n,m;
printf("Введите размеры матрицы: ”);
scanf("%d %d”,&n,&m);
double a[n][m]; При объявлении двумерного массива в СИ допускается производить инициализацию значений элементов матрицы:
тип имя[размер №1][размер №2] = {
{значение № 11, ... значение № 1N},
...
{значение № M1, ... значение № MN}
}; Примеры объявлений с инициализацией:
int a = { //Объявлен двумерный массив
{1,2,3,4}, // 1 2 3 4
{5,6}}; // 5 6 0 0
Double b = { //Объявлен двумерный массив
{1.0, 2.0, 3.0, 4.0, 5.0}, // 1 2 3 4 5
{6.0, 7.0} // 6 7 0 0 0
}; // 0 0 0 0 0
int a = {{1,2,3,4,5},{6,7,8,9,0}}; Допускается не указывать количество строк в двумерном массиве (указываются пустые квадратные скобки). В таком случае размер массива будет определен по числу инициализирующих значений строк. Количество столбцов матрицы всегда необходимо указывать. Например:
double b = {{1,2,3,4},{5,6,7,8}}; Объявление константных матриц (значения их элементов изменить нельзя) начинается с ключевого слова const, за которым следует объявление матрицы с инициализацией. Пример:
const int matrix = {
{1,2,3,4,5},
{6,7,8,9}
}; Обращение к элементу матрицы осуществляется путем указания имени матрицы, а после имени в отдельных парных квадратных скобках индексы элемента (строка и столбец):
имя[строка][столбец] Индексация в языке СИ начинается с нуля, поэтому для матрицы размером, например, пять строк и десять столбцов правильными будут индексы строк от нуля до четырех, а столбцов – от нуля до девяти включительно.
Каждый отдельный элемент матрицы может рассматриваться как простая переменная и, соответственно, выступать в выражениях в качестве RValue или LValue значений.
Ввод и вывод матриц в языке СИ осуществляется поэлементно. Так как матрица имеет двойную размерность, то ввод и вывод осуществляется во вложенных циклах. Например:
double a;
for(int i=0;i<5;i++)
for(int j=0;j<10;j++)
scanf("%lf”,&a[i][j]);
...
for(int i=0;i<5;i++){
for(int j=0;j<10;j++)
printf("%8.2lf\t”,a[i][j]);
printf("\n”);
} Присвоение матрицы матрице также осуществляется поэлементно. Например, необходимо присвоить целочисленную матрицу x целочисленной матрице y. Фрагмент программы:
int x, y;
...
for(int i=0;i<5;i++)
for(int j=0;j<10;j++)
y[i][j] = x[i][j];
... В языке СИ допускается создание массивов размерностью три и более(т.е трехмерных, четырехмерных и т.д.). Например, объявление трёхмерного целочисленного массива с инициализацией будет иметь вид:
int a={ //это трехмерный массив
{{1,2},{3,4}},
{{5,6},{7,8}}
}; Ввод, вывод и прочая обработка такого массива осуществляется аналогично обработке двумерного массива, только уже в трех вложенных
I . На кого рассчитан модуль.
Данный модуль рассчитан учащегося в старшей школе или студента. Должны быть освоены такие темы как работа с циклами, с указателями, необходимо знать, что такое одномерный массив.
II . Мотивация
Мы уже знаем, для чего нам могут понадобиться одномерные массивы. Например, мы можем сохранить в одномерном массиве коэффициенты квадратного уравнения и посчитать корни, используя дискриминант. А если нам нужно посчитать много таких уравнений? Неужели каждый раз перезаписывать новые коэффициенты на место старых? А если необходимо будет вернуться к уже посчитанным? Или нам нужно решить систему из нескольких уравнений, т.е. нужно одновременно работать со всеми? Если нам просто нужно хранить таблицу каких-то значений, например, измерений при опыте, как нам это сделать, используя полученные уже знания?
Для каждого из вышеназванных случаев можно просто объявить несколько одномерных массивов, но вот приятно ли будет работать с таким количеством? Ведь каждый нужно будет назвать и обработать отдельно. Ситуация похожа на ту, когда мы только вводили понятие одномерного массива. Тут и приходят на помощь массивы двумерные.
III. Изложение материала модуля
Обычным представлением таких массивов являются таблицы значений, содержащие информацию в строках и столбцах. Чтобы определить отдельный табличный элемент, нужно указать два индекса: первый (по соглашению) указывает номер строки, а второй (опять же по соглашению) указывает номер столбца.
Рисунок иллюстрирует двумерный массив a . Массив содержит три строки и четыре столбца, так что, еще говорят, - это массив три на четыре. Вообще, массивы с m строками и n столбцами называют массивами m на n .
Каждый элемент в массиве а определяется именем элемента в форме a [ i ][ j ]; a – это имя массива, а i и j – индексы, которые однозначно определяют каждый элемент в а . Заметим, что имена элементов первой строки имеют первый индекс 0 , имена элементов в четвертом столбце имеют второй индекс 3 .
Типичная ошибка программирования
Неправильная ссылка на элемент двумерного массива a [ x ] [ y ] как a [ x , y ]. На самом деле, a [ x , y ] воспринимается как a [ y ] , потому что С оценивает выражение (содержащее операцию последования - запятую) x , y просто как y (последнее из разделенных запятыми выражений).
Многомерные массивы могут получать начальные значения в своих объявлениях точно так же, как массивы с естественным индексом. Например, двумерный массив b можно объявить и дать ему начальные значения таким образом:
int b = {{1,2}, {3,4}};
Значения группируются в строки, заключенные в фигурные скобки. Таким образом, элементы b иb получают начальныезначения 1 и 2, а элементы b и b получают начальные значения 3 и 4. Если начальных значений в данной строчке не хватает для их присвоения всем элементам строки, то остающимся элементам присваиваются нулевые начальные значения. Таким образом, объявление
int b = {{1,},{3,4}};
будет означать, что b получает начальное значение 1, b получает начальное значение 0.
Объем памяти в байтах, занимаемый двухмерным массивом, вычисляется по следующей формуле:
Количество байтов = размер_1-го_измерения*размер_2-го_измерения*sizeof(базовый тип)
Например, двумерный массив 4-байтовых целых чисел размерностью 10*5 занимает участок памяти объемом
то есть 200 байтов.
Передача массива в функцию.
Рассмотрим небольшую программу вывода элементов двумерного массива:
#include
void printArray(int a)
for (int i = 0; i<=1;i++)
for (int j=0; j<=2; j++)
printf(“%i, ”,&a[i][j]);
printf(“\n”);
int array = {{1,2,3},{4,5,6}};
printf(“Values in array on rows:”);
printgArray(array);
Values in array on rows:
Программа вызывает функцию printArray для вывода элементов массива. Заметим, что описание функции указывает параметр – массив как int a . Когда мы задаем как аргумент функции одномерный массив, скобки в списке параметров функции пусты. Размерность первого индекса многомерного массива также не требуется, но все последующие размерности индексов необходимы. Компилятор использует размерности этих индексов для определения соответствующих ячеек памяти для доступа к элементам многомерных массивов. В памяти все элементы массива хранятся последовательно, независимо от количества индексов (размерности массива). В двумерном массиве первая строка хранится в памяти перед второй строкой.
Наличие размерностей индексов в объявлении параметра дает возможность компилятору сообщить функции о том, как расположены элементы в массиве. В двумерном массиве каждая строка является одномерным массивом. Чтобы определить местоположение элемента в некоторой строке, функция должна точно знать, сколько элементов находится в каждой строке. Тогда функция может пропустить соответствующее количество ячеек памяти при обращении к массиву. Таким образом, при обращении к a функция знает, что для доступа ко второй строке (строка 1) нужно пропустить в памяти три элемента первой строки, а затем обратиться к третьему элементу этой строки (элементу 2).
Многие типовые операции с массивами используют конструкцию for . Так, следующий цикл определяет сумму всех элементов массива a :
for (row = 0; row < 3; row++)
for (column = 0; column < 3; column ++)
total += a ;
Внутренняя структура for суммирует элементы одной строки массива. Внешняя структура for начинает работу с установки row (т.е. индекса строки) в нуль, так что во внутренней структуре for могут быть просуммированы элементы второй строки. Далее внешняя структура for увеличивает row до значения 2, так что могут быть просуммированы элементы третьей строки. После завершения работы вложенной структурыfor печатается результат.
Задача
Учащиеся одного из ВУЗов как-то поспорили, у кого наивысший средний бал за только что сданную сессию. Заодно захотели выяснить, кто получил наилучшую и наихудшую оценки. Для интереса представим, что мы живем в Америке, и оценки выставляются по 100-бальной шкале.
Указание:
Программа должна «знать» имена студентов, выводить их на экран. То же самое с таблицей успеваемости. Подразумевается, что номера столбцов эквивалентны номерам экзаменов.
Размышления о решении задачи
Для начала давайте определимся, что нам нужно для решения этой задачи. Первое, на что мы обращаем внимание – это то, что в условие явно сказано слово «таблица». Значит, скорее всего, для работы с ней мы будем использовать двумерный массив. Каждая строка в нем – это успеваемость отдельного студента. Как и сказано в условии, номер столбца будет определять номер сданного экзамена, номер строки – студента. Именно с этим массивом мы и будем работать, вычисляя средний бал, минимум и максимум. Видно, что необходимо будет создать три функции для получения нужных нам данных и функцию вывода таблицы оценок на экран. Все, что нужно для написания этой части программы, мы уже знаем.
Теперь разберемся с именами. Неплохо было бы их скомпоновать в таблицу, для того, чтобы по номеру студента можно было определить его имя и наоборот. Мы уже знаем. Что строка – это одномерный массив символов. Значит, можно создать двумерный массив, в котором номер строки будет определять номер студента, а номер столбца – соответствующую букву имени. Но тогда придется создать массив с наибольшим количеством ячеек по горизонтали из возможных. Т.е., если у нас есть четыре студента:
То необходимо будет создать таблицу, подобную изображенной на рисунке:
Серым цветом на рисунке показаны пустые клетки нашего массива. На эти клетки будет отведено место в памяти, но вот пользоваться они не будут. Так зачем они нам нужны? Нет ли способа избежать такой ситуации? Оказывается, есть. Об этом будет рассказано ниже, а затем мы вернемся к решению нашей задачи.
Формулировка задачи:
Всем добрый день)
Мне хотелось бы по возможности получить Вашу помощь с данным заданием, провел за ним достаточно времени, хочу разобраться, где у меня ошибки.
Собственно само задание:
"Напишите программу, которая создает матрицу 5*5 и заполняет ее полностью +. Пользователю должно быть предложено меню:
Матрица выглядит так:
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
Опции:
(1) Заполнить все поля знаком 0
(2) Заполнить обе диагонали 0
(3) Заполнить заданное поле 0 (столбец, строка)
(4) Обновить: Заполнить все поля снова +
(5) Конец программы "
Пример выведения для 2 опции:
Матрица выглядит сейчас так:
0 + + + 0
+ 0 + 0 +
+ + 0 + +
+ 0 + 0 +
0 + + + 0
Какие у меня проблемы:
1. Почему-то матрица в случае вывода через arr [i][j] заполняется не +, а левыми символами
2. В случае с выбором 2 опции, вроде бы диагонали заданы правильно, но появляются "лишние" нули и выводится не один раз (почему не один раз я знаю, но не совсем понимаю, как это корректно исправить)
3. Как правильно задать именно нужный адрес с клавиатуры и "прикрутить" его к матрице, чтобы именно это поле менялось на ноль.
4. Как сделать лучше реализацию цикла do while, чтобы программа продолжала выполняться, пока не будет нажата кнопка 5.
5. Как реализовать вывод "красивше"?
Вот мой код:
#include
Код к задаче: «Заполнение матрицы символами»
Textual
#include
