Статический массив: объявление, заполнение, использование. Tag Archives: матрицы Матрицы в си

Безусловно, по входным данным можно восстановить матрицы, тривиальным образом их перемножить и вывести результат в заданном виде. Как пример плохого стиля программирования: наивный алгоритм приводит к почти двукратному перерасходу потребляемой памяти и существенно уступает в производительности. Существует другое решение, прийти к которому можно путем последовательного приспособления стандартных матричных операций к формату входных данных.

Наибольшую сложность, как вычислительную, так и идейную, представляет умножение матриц, в данном случае — возведение в квадрат. Нижеприведенная последовательность шагов позволит перемножать симметричные матрицы, используя их линейное представление в формате исходных данных.

Замечание 1

Подпространство симметричных матриц незамкнуто относительно умножения: произведением двух симметричных матриц может быть несимметричная матрица.

Пример

\left(\begin{array}{ccc} 1 & 1 & 3 \\ 1 & 4 & 5 \\ 3 & 5 & 0\end{array} \right) \cdot \left(\begin{array}{ccc} 4 & 0 & 0 \\ 0 & 4 & 3 \\ 0 & 3 & 2 \end{array} \right) = \left(\begin{array}{ccc} 4 & 13 & 9 \\ 4 & 31 & 22 \\ 12 & 20 & 15 \end{array} \right)

Замечание 2

Степень симметрической матрицы также является симметрической матрицей. Доказательство основано на представлении матрицы как представления линейного оператора и на свойствах эрмитовых операторов.

Во всех дальнейших выкладках подразумевается, что матрица представлена линейным массивом из \frac{n(n+1)}{2} элементов.

Для начала, заметим, что элемент c_{i,j} матрицы C=A^{2}, равен скалярному произведению (как векторов в стандартном базисе) i-ой строки матрицы A на j-ую её строку (в силу того, что в симметричной матрице j-ая строка совпадает с j-м столбцом). Следовательно, для возведения в степень симметричной матрицы необходимо и достаточно реализовать операцию скалярного перемножения двух её строк.

Тогда следует понять, как по данному представлению матрицы получить её i-ую строку. Для удобства, выпишем имеющиеся элементы в виде полной матрицы. Заметим, что первым элементом i-ой строки будет i-ый элемент первой строки, и обобщим это наблюдение. Обозначим позицию текущего интересующего нас элемента i-ой строки как j. Если j < i, то следует выбрать i-ый элемент j-ой строки, иначе следует выбрать все элементы j-ой строки, лежащие правее данного. Графически можно интерпретировать алгоритм таким образом: начиная с i-го элемента первой строки, спускаться вертикально вниз по матрице до тех пор, пока не будет достигнута i-ая строка, далее — двигаться вправо до конца строки. Наглядность алгоритма позволяет легко воплотить его программно.
Следует только пронаблюдать, как изменяются расстояния между элементами, лежащими один под другим, при движении вниз по строкам матрицы, что позволит легко перенести алгоритм на линейное представление верхней треугольной матрицы. Предлагаем читателю самому проделать это несложное, но наглядное упражнение, для лучшего понимания алгоритма.

Теперь можно перейти непосредственно к реализации.

При решении задач с большим количеством данных одинакового типа использование переменных с различными именами, не упорядоченных по адресам памяти, затрудняет программирование. В подобных случаях в языке Си используют объекты, называемые массивами.

— это непрерывный участок памяти, содержащий последовательность объектов одинакового типа, обозначаемый одним именем.

Массив характеризуется следующими основными понятиями:

Элемент массива (значение элемента массива) – значение, хранящееся в определенной ячейке памяти, расположенной в пределах массива, а также адрес этой ячейки памяти.
Каждый элемент массива характеризуется тремя величинами:

• адресом элемента — адресом начальной ячейки памяти, в которой расположен этот элемент;
• индексом элемента (порядковым номером элемента в массиве);
• значением элемента.

Адрес массива – адрес начального элемента массива.

Имя массива – идентификатор, используемый для обращения к элементам массива.

Размер массива – количество элементов массива

Размер элемента – количество байт, занимаемых одним элементом массива.

Графически расположение массива в памяти компьютера можно представить в виде непрерывной ленты адресов.

Представленный на рисунке массив содержит q элементов с индексами от 0 до q-1 . Каждый элемент занимает в памяти компьютера k байт, причем расположение элементов в памяти последовательное.

Адреса i -го элемента массива имеет значение

Адрес массива представляет собой адрес начального (нулевого) элемента массива. Для обращения к элементам массива используется порядковый номер (индекс) элемента, начальное значение которого равно 0 . Так, если массив содержит q элементов, то индексы элементов массива меняются в пределах от 0 до q-1 .

Длина массива – количество байт, отводимое в памяти для хранения всех элементов массива.

ДлинаМассива = РазмерЭлемента * КоличествоЭлементов

Для определения размера элемента массива может использоваться функция

int sizeof (тип);

Например,

sizeof (char ) = 1;
sizeof (int ) = 4;
sizeof (float ) = 4;
sizeof (double ) = 8;

Объявление и инициализация массивов

Для объявления массива в языке Си используется следующий синтаксис:

тип имя[размерность]={инициализация};

Инициализация представляет собой набор начальных значений элементов массива, указанных в фигурных скобках, и разделенных запятыми.

int a = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // массив a из 10 целых чисел

Если количество инициализирующих значений, указанных в фигурных скобках, меньше, чем количество элементов массива, указанное в квадратных скобках, то все оставшиеся элементы в массиве (для которых не хватило инициализирующих значений) будут равны нулю. Это свойство удобно использовать для задания нулевых значений всем элементам массива.

int b = {0}; // массив b из 10 элементов, инициализированных 0

Если массив проинициализирован при объявлении, то константные начальные значения его элементов указываются через запятую в фигурных скобках. В этом случае количество элементов в квадратных скобках может быть опущено.

int a = {1, 2, 3, 4, 5, 6, 7, 8, 9};

При обращении к элементам массива индекс требуемого элемента указывается в квадратных скобках .

Пример на Си

1
2
3
4
5
6
7
8

#include
int main()
{
int a = { 5, 4, 3, 2, 1 }; // массив a содержит 5 элементов
printf("%d %d %d %d %d\n" , a, a, a, a, a);
getchar();
return 0;
}

Результат выполнения программы:

Однако часто требуется задавать значения элементов массива в процессе выполнения программы. При этом используется объявление массива без инициализации. В таком случае указание количества элементов в квадратных скобках обязательно.

int a;

Для задания начальных значений элементов массива очень часто используется параметрический цикл:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include
int main()
{
int a;
int i;
// Ввод элементов массива
for (i = 0; i<5; i++)
{
printf("a[%d] = " , i);
scanf("%d" , &a[i]);
}
// Вывод элементов массива
for (i = 0; i<5; i++)
printf("%d " , a[i]); // пробел в формате печати обязателен
getchar(); getchar();
return 0;
}

Результат выполнения программы

Многомерные массивы

В языке Си могут быть также объявлены многомерные массивы. Отличие многомерного массива от одномерного состоит в том, что в одномерном массиве положение элемента определяется одним индексом, а в многомерном - несколькими. Примером многомерного массива является матрица.

Общая форма объявления многомерного массива

тип имя[размерность1][размерность2]...[размерностьm];

Элементы многомерного массива располагаются в последовательных ячейках оперативной памяти по возрастанию адресов. В памяти компьютера элементы многомерного массива располагаются подряд, например массив, имеющий 2 строки и 3 столбца,

int a;

будет расположен в памяти следующим образом

Общее количество элементов в приведенном двумерном массиве определится как

КоличествоСтрок * КоличествоСтолбцов = 2 * 3 = 6.

Количество байт памяти, требуемых для размещения массива, определится как

КоличествоЭлементов * РазмерЭлемента = 6 * 4 = 24 байта.

Инициализация многомерных массивов

Значения элементов многомерного массива, как и в одномерном случае, могут быть заданы константными значениями при объявлении, заключенными в фигурные скобки {} . Однако в этом случае указание количества элементов в строках и столбцах должно быть обязательно указано в квадратных скобках .

Пример на Си

1
2
3
4
5
6
7
8
9

#include
int main()
{
int a = { 1, 2, 3, 4, 5, 6 };
printf("%d %d %d\n" , a, a, a);
getchar();
return 0;
}

Однако чаще требуется вводить значения элементов многомерного массива в процессе выполнения программы. С этой целью удобно использовать вложенный параметрический цикл .

Пример на Си

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#define _CRT_SECURE_NO_WARNINGS
#include
int main()
{
int a; // массив из 2 строк и 3 столбцов
int i, j;
// Ввод элементов массива
for (i = 0; i<2; i++) // цикл по строкам
{
for (j = 0; j<3; j++) // цикл по столбцам
{
printf("a[%d][%d] = " , i, j);
scanf("%d" , &a[i][j]);
}
}
// Вывод элементов массива
for (i = 0; i<2; i++) // цикл по строкам
{
for (j = 0; j<3; j++) // цикл по столбцам
{
printf("%d " , a[i][j]);
}
printf("\n" ); // перевод на новую строку
}
getchar(); getchar();
return 0;
}

Передача массива в функцию

Обработку массивов удобно организовывать с помощью специальных функций. Для обработки массива в качестве аргументов функции необходимо передать

• адрес массива,
• размер массива.

Исключение составляют функции обработки строк, в которые достаточно передать только адрес.

При передаче переменные в качестве аргументов функции данные передаются как копии. Это означает, что если внутри функции произойдет изменение значения параметра, то это никак не повлияет на его значение внутри вызывающей функции.

Если в функцию передается адрес переменной (или адрес массива), то все операции, выполняемые в функции с данными, находящимися в пределах видимости указанного адреса, производятся над оригиналом данных, поэтому исходный массив (или значение переменной) может быть изменено вызываемой функцией.

Пример на Си Дан массив из 10 элементов. Поменять местами наибольший и начальный элементы массива. Для операций поиска максимального элемента и обмена использовать функцию.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#define _CRT_SECURE_NO_WARNINGS
#include
// Функция обмена
void change(int *x, int n)
{
// x - указатель на массив (адрес массива)
// n - размер массива
int i;
int max, index;
max = x;
index = 0;
// Поиск максимального элемента
for (i = 1; i {
if (x[i]>max)
{
max = x[i];
index = i;
}
}
// Обмен
x = x;
x = max;
}
// Главная функция
int main()
{
int a;
int i;
for (i = 0; i<10; i++)
{
printf("a[%d] = " , i);
scanf("%d" , &a[i]);
}
change(a, 10); // вызов функции обмена
// Вывод элементов массива
for (i = 0; i<10; i++)
printf("%d " , a[i]);
getchar();
getchar();
return
p = p * x[i];
}
return p;
}
// Главная функция
int main()
{
int a; // объявлен массив a из 5 элементов
int i;
int pr;
// Ввод элементов массива
for (i = 0; i<5; i++)
{
printf("a[%d] = " , i);
scanf("%d" , &a[i]); // &a[i] - адрес i-го элемента массива
}
pr = func(a, 5); // вычисление произведения
printf("\n pr = %d" , pr); // вывод произведения четных элементов
getchar(); getchar();
return 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}}
  };  Ввод, вывод и прочая обработка такого массива осуществляется аналогично обработке двумерного массива, только уже в трех вложенных

Вообще-то программировать расчёт определителей не нужно. Их умеет считать, скажем, встроенная функция МОПРЕД из Excel:

• набираем элементы матрицы в смежных ячейках, например, матрица размерностью 4*4 показана на картинке;
• в нужной ячейке вводим формулу (в нашем случае =МОПРЕД(A1:D4) и нажимаем Enter:)

Не труднее вычислить и в MathCAD - просто нажать кнопку на панели матриц...

Но иногда нужен алгоритм, а не ответ... вот немного кода на консольном C++, на совершенство он не претендует, но нули в матрице или "не тот" порядок элементов смущать функцию determinant не должны. Пример из main - 1001-й на работу с динамической матрицей средствами C++ :) Остальное закомментировано в исходнике.

#define bool int #define true 1 #define false 0 int search (double **a, int m, int n, double what, bool match, unsigned int &uI, unsigned int &uJ, unsigned int starti, unsigned int startj) { // Поиск в матрице a[m][n] элемента с указанным значением what // Возвращаеются его номер строки и столбца uI, uJ, если элемент найден. // match - искать равный элемент или отличный от указанного. // Вернёт 0 - не найдено, не 0 - найдено if ((!m) || (!n)) return 0; if ((starti >= n) || (startj >= m)) return 0; for (unsigned int i = starti; i < n; i++) for (unsigned int j = startj; j < m; j++) { if (match == true) { if (a[i][i] == what) { uI = i; uJ = j; return 1; } } else if (a[i][j] != what) { uI = i; uJ = j; return 1; } } return 0; } void swaprows (double **a, int n, int m, unsigned int x1, unsigned int x2) { //Меняет в матрице a[n][m] строки с номерами x1 и x2 местами if ((!n) || (!m)) return; if ((x1 >= n) || (x2 >= n) || (x1 == x2)) return; double tmp; for (unsigned int x = 0; x < m; x++) { tmp = a[x]; a[x] = a[x]; a[x] = tmp; } return; }; void swapcolumns (double **a, int n, int m, unsigned int x1, unsigned int x2) { //Меняет в матрице a[n][m] столбцы с номерами x1 и x2 местами if ((!n) || (!m)) return; if ((x1 >= m) || (x2 >= m) || (x1 == x2)) return; double tmp; for (unsigned int x = 0; x < n; x++) { tmp = a[x]; a[x] = a[x]; a[x] = tmp; } return; }; double determinant (double **a, unsigned int n) { //Вычисление определителя квадратной матрицы a[n][n] unsigned int m = n; if (m == 0) return 0; if (m == 1) return a; if (m == 2) return (a * a - a * a); bool sign = false; // смена знака определителя. по умолчанию - нет double det = 1; // определитель double tmp; unsigned int x, y; for (unsigned int i = 0; i < n; i++) { // цикл по всей главной диагонали if (a[i][i] == 0) { // если элемент на диагонали равен 0, то ищем ненулевой элемент в матрице if (!search(a,m,n,0, false, y, x, i, i)) return 0; // если все элементы нулевые, то опр. = 0 if (i != y) { // меняем i-ую строку с y-ой swaprows(a,m,n,i, y); sign = !sign; } if (i != x) { // меняем i-ый столбец с x-ым swapcolumns(a,m,n,i, x); sign = !sign; } // таким образом, в a[i][i], теперь ненулевой элемент. } // выносим элемент a[i][i] за определитель det *= a[i][i]; tmp = a[i][i]; for (x = i; x < m; x++) { a[i][x] = a[i][x] / tmp; } // таким образом a[i][i] теперь равен 1 // зануляем все элементы стоящие под (i, i)-ым, // при помощи вычитания с опр. коеффициентом for (y = i + 1; y < n; y++) { tmp = a[y][i]; for (x = i; x < m; x++) a[y][x] -= (a[i][x]*tmp); } } if (sign) return det*(-1); return det; }; #include int main () { const int n=4; int data = { 5,4,3,2, 11,-1,2,7, 0,1,0,4, -13,79,1,2 }; int i,j,k=0; double **a = new double * [n]; for (i=0; i