Вычисление детерминанта матриц на основе рекурсивного алгоритма - C (СИ)
Формулировка задачи:
Помогите с написанием программы для вычисления детерминанта матриц на основе рекурсивного алгоритма.
Находил подобную программу на Delphi, Pascal и отрывками на C++, а вот на С нету
Решение задачи: «Вычисление детерминанта матриц на основе рекурсивного алгоритма»
textual
Листинг программы
#include <conio.h>
#include <stdio.h>
#define n 4
int main (void)
{
int Minor (int *ptr, int *ptr2, int nn, int row, int col);
long int Determinant (int *ptr, int nn);
long int det;
//int i, j;
int M[n][n] = {
{3, 5, 7, 8},
{-1, 7, 0, 1},
{0, 5, 3, 2},
{1, -1, 7, 4}
};
int *ptr;
ptr = &M[0][0];
det = Determinant (&M[0][0], n);
printf("\n\t Determinant = %d", det);
printf("\n\n Press any key: ");
_getch();
return 0;
}
int Minor (int *ptr, int *ptr2, int nn, int row, int col)
{
int ki, kj, di = 0, dj;
for (ki = 0; ki < nn - 1; ki++)
{
if (ki == row)
di = 1;
dj = 0;
for (kj = 0; kj < nn - 1; kj++)
{
if (kj == col)
dj = 1;
*(ptr2 + ki*nn + kj) = *(ptr +(ki + di)*nn + (kj + dj));
}
}
}
long int Determinant (int *ptr, int nn)
{
long int i, j, d = 0, k = 1;
int R[n][n] = {0};
int *ptr2, **ptr3;
ptr2 = &R[0][0];
ptr3 = &ptr;
if (nn < 1)
return 1;
else if (nn == 1)
d = *ptr;
else if (nn == 2)
d = *ptr * *(ptr + nn + 1) - *(ptr + nn) * *(ptr + 1);
else
for (i = 0; i < nn; ++i)
{
Minor (*ptr3, &R[0][0], nn, i, 0);
d += k * *(ptr + i*nn) * Determinant (&R[0][0], nn - 1);
k = -k;
}
return d;
}
Объяснение кода листинга программы
В этом коде реализован алгоритм вычисления определителя матрицы. Определитель вычисляется путем последовательного применения операций элементарного преобразования матрицы. Список действий:
- Ввод матрицы M. Матрица M размером 4x4 заполняется значениями.
- Вычисление определителя. Вызывается функция Determinant, которая возвращает определитель матрицы.
- Вывод определителя. Результат вычисления определителя выводится на экран.
- Ввод ключа. Программа ожидает нажатия любой клавиши, чтобы продолжить выполнение. Функция Minor используется внутри функции Determinant и рекурсивно вызывает себя для вычисления миноров матрицы R. Вот список действий в функции Determinant:
- Базовый случай. Если размер матрицы меньше или равен 1, то определитель равен 1.
- Случай размера 2. Если размер матрицы равен 2, то определитель вычисляется как произведение диагональных элементов матрицы.
- Рекурсивный случай. Если размер матрицы больше 2, то для каждого элемента в первом столбце матрицы R вызывается функция Minor, которая вычисляет минор этого элемента.
- Сложение и умножение. К полученному значению d добавляется произведение текущего элемента матрицы и определителя матрицы R, уменьшенного на 1.
- Меняем знаки. Знак k меняется на противоположный, чтобы обеспечить циклическое перебор строк.
- Рекурсивный вызов. Вызывается рекурсивный случай для следующей строки.
- Возврат результата. Результат вычисления определителя возвращается из функции.