Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [C] Нахождение определителя матрицы

Автор: GemBird 4.6.2006, 19:26

Уважаемый модераторы и учасники форума!

Необходим исходный код на C для нахождения определителя n-го порядка.

Для 2-го, 3-го порядка ясно как сделать, это легко! А вот начиная с 4-го начинаются трудности.
Нужен алгоритм. А какой? Сам составить не могу. Кто может помочь?

Завтра здача курсовой, войдите в мое положение smile

Автор: skyboy 4.6.2006, 19:37

в чём отличие между определением определителя ( smile

) 4-го и 54-го порядка?

Код


sum= 0;
// a - массив размерности n x n
for(int i= 0; i< n; i++)
 {
  proizv= 1;
  for(j= 0, k= i; j< n; j++, k= (k==n-1)?0: k+1 )
   proizv*= a[i][k];
  sum+= proizv;
 }
for(int i= 0; i< n; i++)
 {
  proizv= 1;
  for(j= 0, k= i; j< n; j++, k= (k==0)?n - 1: k-1 ) 
   proizv*= a[i][k];
  sum-= proizv;
 }
// теперь  в sum - значение определителя. Если я ничего не перепутал. Проверь - компилятора под рукой нет.

Автор: GemBird 4.6.2006, 20:42

skyboy, ты не так понял, ничего, если на ты?
Мне не сумму элементов массива нужно, а именно определитель!!!

Где определитель 2-го порядка равен:
| a11  a12|
| a21  a22| = a11*a22 - a12*a21

определитель 3-го порядка равен:
| a11  a12  a13|
| a21  a22  a23| = a11 * | a22  a23| - a12 * | a21  a23| + a13 * | a21  a22|
| a31  a32  a33|              | a32  a33|             | a31  a33|               | a31  a32|

определитель 4-го порядка равен:
| a11  a12  a13  a14|
| a21  a22  a23  a24| =a11*| a22  a23  a24|-a12*| a21 a23 a24|+a13*| a21 a22 a24|-a14*| a21 a22 a23|
| a31  a32  a33  a34|           | a32  a33  a34|         | a31 a33 a34|          | a31 a32 a34|          | a31 a32 a33|
| a41  a42  a43  a44|           | a42  a43  a44|         | a41 a43 a44|          | a41 a42 a44|          | a41 a42 a43|

Вот в чем разница между определителем 4-го и 54-го порядка! Не так-кто все просто! smile

Заданы значения всех aij.
Сможешь написать алгоритм для n-го порядка?

Автор: skyboy 4.6.2006, 22:35

не понял. где ты увидел сумму элементов массива? Коль у меня алгоритм даёт неверный результат - так и скажи. Компилятора С у меня под рукой нет. А алгоритм следующий:
посмотри на определение опеределителя, скажем, 4-го порядка. Предварительно распиши его, как сумму/ разность произведений. Ты увидишь, что каждое слагаемое этой суммы это произведение элемнтов матрицы, лежащие на диагонали. В случае знака "+" эта диагональ направлениа ссверу-вниз и слева-направо, а при знаке "- ": сверху-вниз и справа-налево. Оттого меняется индекс элемента при определении произведения "лесенкой".

Добавлено @ 22:36
ничего, если на "ты".

Автор: skyboy 4.6.2006, 23:31

Вот. Нашёл компилятор и отладил. Давненько я на С не смотрел.. Это ж надо - в первую секцию for-цикла оператор "запятая" присобачил...
Вот такое получилось:

Код


#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <stdlib.h>
int Det(int** matr,int N)
{
int sum,mul;
sum= 0;
if(2==N)
 {
  sum= matr[0][0] * matr[1][1] - matr[0][1] * matr[1][0];
  return sum;
 }
for(int i= 0;i< N; i++)
 {
  mul= 1;
  int k= i;
  for(int j=0; j< N; j++)
   {
    mul*= matr[j][k];
    k= k==N-1?0: k + 1;
   }
  sum+= mul;
 }
for(i= 0;i< N; i++)
 {
  mul= 1;
  int k= i;
  for(int j=0; j< N; j++)
   {
    mul*= matr[j][k];
    k= k==0?N - 1: k - 1;
   }
  sum-= mul;
 }

return sum;
}

void main()
{
randomize();
int** a;
int N;
cout<<"Input value\n";
cin>>N;
a= (int**)malloc(N * sizeof(int*));
for(int i= 0; i< N; i++)
 a[i]= (int*)malloc(N * sizeof(int));
for(i =0; i< N; i++)
 for(int j= 0; j< N; j++)
  a[i][j]= random(5);
cout<<"\n\n";
for(i= 0; i< N; i++)
 {
  for(int j= 0; j< N; j++)
   cout<<a[i][j]<<"\t";
  cout<<"\n";
 }
cout<<"\n\n"<<Det(a,N)<<"\n\n\n";
getch();
}

Добавлено @ 23:39
Код не рекурсивный, а итеративный - возможно, будет работать быстрее рекурсивного варианта с алгебраическими дополнениями.

Автор: maxim1000 5.6.2006, 00:18

Цитата(skyboy @ 4.6.2006, 22:31

)

for(i= 0;i< N; i++)

определитель - сумма n! слагаемых
тут, насколько я понял, их 2n...

Автор: skyboy 5.6.2006, 08:25

maxim1000, сложно скопмилировать и посмотреть? smile

Определитель - это сумма 2n слагаемых, каждое из которых - это произведение n элементов. Причём из этих 2n n идут со знаком "+", а остальные - со знаком "-"

Добавлено @ 08:36
Хм. Исправил баг с вычисление определителя порядка 2.

Автор: maxim1000 5.6.2006, 10:54

Цитата(skyboy @ 5.6.2006, 07:25

)

сложно скопмилировать и посмотреть?

зачем?
про 2n это и так видно

Цитата(skyboy @ 5.6.2006, 07:25

)

Определитель - это сумма 2n слагаемых, каждое из которых - это произведение n элементов. Причём из этих 2n n идут со знаком "+", а остальные - со знаком "-"

хм... видимо, у нас разные источники...
я привык такому определению:
определитель - сумма произведений всевозможных последовательностей (i,xi), i=1..n, xi - из интервала 1..n и все разные
знак каждого слагаемого определяется чётностью перестановки
чётность перестановки xi можно определить, например, так:
чётность количества необходимых замен соседних элементов, чтобы привести к перестановке xi=i

Автор: skyboy 5.6.2006, 11:52

maxim1000, я не говорил, что я изобрёл велосипед. Просто подход к подсчёт опреелителя может біть не один(т.е. алгоритм рассчёта)
давай на примере, а?
матрица:
1  2
3  4
определитель = 1 * 4 - 2 * 3 = -2. Через дополнения распишется так же. Пока - неинтересно.
матрица:
1 5 6
4 0 3
2 1 0
определитель = 1·0·0 + 5·3·2 + 6·4·1 - 6·0·2 - 1·3·1 - 0·5·4= 51
Через алгебраические дполнения:
1·|0 3| - 5·|4 3| + 6·|4 0| = 1·(-3) - 5·(0 - 6) + 6·(4 - 0)= 30+24-3= 51
   |1 0|      |2 0|        |2 1|
мой вариант - всего лишь "приведенный" вариант определения определителя через алгебраические дополнения. А алгоритм выглядит так(на примере последней матрицы порядка 3).
Шаг 1. Допишем справа такую же матрицу без последней колонки(сама эта матрица нужна только для прояснения, алгоритм не требует копирования данных)
1 5 6 | 1 5
4 0 3 | 4 0
2 1 0 | 2 1
Шаг 2. Сформируем произведения элементов, имеющих одинаковый цвет:
1 5 6 | 1 5
4 0 3 | 4 0
2 1 0 | 2 1
Эти произведения(1·0·0, 5·3·2 и 6·4·1) войдут в сумму со знаком "+".
Шаг 3. Допишем слева такую же матрицу без первой колонки.
5 6 | 1 5 6
0 3 | 4 0 3
1 0 | 2 1 0
Шаг 4. Сформируем произведения элементов, имеющие одинаковый цвет
5 6 | 1 5 6
0 3 | 4 0 3
1 0 | 2 1 0
Эти произведения(1·3·1, 5·4·0 и 6·0·2) войдут в сумму со знаком "-".
Суммируем полученные произвдеения с учётом знака и получаем 0 + 30 + 24 - 3 - 0 - 0= 51
Нерекурсивный алгоритм.

Добавлено @ 12:00
Твоё определение правильное. А я определения не давал вовсе   smile

Просто рекурсивный алгоритм вычисляет одни и те же произведения при различных алгебраических дополнениях. А приведенный мною - только единожды.
При разложении на алгебраические дополнения матриц порядка 3 выполняется 9 умножений и 5 сложений. А в "моём" способе - 12 умножений и 5 сложений. Вроде бы, приведёный мною метод медленнее, да? Зато при порядке матрицы = 4 рекурсивный способ имеет 40 умножений и 23 сложения, тогда как приведённый итеративный - только 24 умнодений/7 сложений. Как считаешь, какой способ подсчитает определитель для матрицы 10х10 быстрее? smile

Автор: maxim1000 5.6.2006, 12:53

n!=2n только для 3-х
для двух предусмотрительно был введён частный случай ;)
стоит рассмотреть алгоритм для матрицы 4
может, и там придётся отступить от алгоритма? smile

Цитата(skyboy @ 5.6.2006, 10:52

)

Просто рекурсивный алгоритм вычисляет одни и те же произведения при различных алгебраических дополнениях

не замечал такого...
пример, если можно

Автор: skyboy 5.6.2006, 13:21

определитель 4-го порядка равен:
| a11  a12  a13  a14|
| a21  a22  a23  a24| =a11*| a22  a23  a24|-a12*| a21 a23 a24|+a13*| a21 a22 a24|-a14*| a21 a22 a23|
| a31  a32  a33  a34|           | a32  a33  a34|         | a31 a33 a34|          | a31 a32 a34|          | a31 a32 a33|
| a41  a42  a43  a44|           | a42  a43  a44|         | a41 a43 a44|          | a41 a42 a44|          | a41 a42 a43|

| a22  a23  a24|= a22*|a33 a34|-a23*|a32 a34|+a24*|a32 a33|=a22*(a33*a44 - a34*a43)-a23*(a32*a44 - a34*a42)+a24*(a32*a43-a42*a33)
| a32  a33  a34|           |a43 a44|         |a42 a44|           |a42 a43|
| a42  a43  a44|

| a21  a23  a24|= a21*|a33 a34|-a23*|a32 a34|+a24*|a31 a33|=a21*(a33*a44 - a34*a43)-a23*(a32*a44 - a34*a42)+a24*(a31*a43-a41*a33)
| a31  a33  a34|           |a43 a44|          |a42 a44|          |a41 a43|
| a41  a43  a44|

| a21  a22  a24|= a21*|a32 a34|-a22*|a31 a34|+a24*|a31 a32|=a21*(a32*a44 - a34*a41)-a22*(a32*a44 - a34*a42)+a24*(a31*a42-a41*a32)
| a31  a32  a34|           |a42 a44|          |a41 a44|          |a41 a42|
| a41  a42  a44|

| a21  a22  a23|= a21*|a32 a33|-a22*|a31 a33|+a23*|a31 a32|=a21*(a32*a43 - a33*a42)-a22*(a31*a43 - a33*a41)+a23*(a31*a42-a32*a41)
| a31  a32  a33|           |a42 a43|         |a41 a43|           |a41 a42|
| a41  a42  a43|

(a31*a42-a32*a41) вычисляется дважды, так же как и (a32*a44 - a34*a42), (a32*a43-a42*a33),(a31*a43-a41*a33),(a32*a44 - a34*a41) и (a33*a44 - a34*a43) - вот это и есть то, что рекурсивный алгоритм считает несколько раз. При размерностях, больших 4-х, количество повторений будет больше, чем 2. И расти оно будет без ограничений. Так смысл делать ту же работу несколько раз? Ещё и тратить время и память на вызов функции...

Автор: maxim1000 5.6.2006, 13:43

Цитата(skyboy @ 5.6.2006, 12:21

)

a21*(a32*a43 - a33*a42)

эээ неее...
таких выражений эта программа не вычисляет
конечно же, если начинать выносить за скобки и тому подобное, то количество вычислений уменьшится, пример тому - подсчёт определителя методом Гаусса (который я, кстати, и посоветовал в такой же теме в Алгоритмах)
но в том-то и дело, что предложенная программа вычисляет просто сумму произведений, без всяких скобок
а в этом случае слагаемых должно быть ровно n!...

Автор: skyboy 5.6.2006, 14:32

maxim1000, где-то я и в самом деле спутал. Это я про программу. А касательно

Цитата(maxim1000 @ 5.6.2006, 13:43

)

a21*(a32*a43 - a33*a42)
эээ неее...
таких выражений эта программа не вычисляет

А как считается определитель второго порядка в твоём методе?
И это... сорри за упрямство smile

Автор: maxim1000 5.6.2006, 15:26

а я ещё никакого метода не приводил smile

ну если всё же идти по определению, то:
есть две перестановки двух для (1,2) : (1,2) и (2,1)
первая чётная, вторая - нет
вот и получаем:
a11*a22 + (-1)*a12*a21

но я имел в виду, что программа-то не выносит ничего за скобки, не группирует, а потому при вычислении определителя третьего порядка способ для второго нигде не используется...

Автор: GemBird 5.6.2006, 23:24

skyboy РЭСПЕКТ smile

Разобрался! Объяснил по полной!
Я еще нашел пример рекурсивного решения...

Код



#include<conio.h> 
#include<stdio.h> 
#include<stdlib.h> 
#include<alloc.h> 
#include<math.h> 

float det(float**,int);
void main() 
{ 
int n,i,j,d=0; 
float **ms;

do 
{ 
clrscr(); 
puts("Enter size of matrix\n"); 
scanf("%d",&n); 
} 
while(n<2); 

ms=calloc(n,sizeof(float*));
for(i=0;i<n;i++)
{
    *(ms+i)=calloc(n,sizeof(float));
}

for(i=0;i<n;i++) 
for(j=0;j<n;j++) 
{printf("Enter [%d][%d] ",i+1,j+1);scanf("%f",&ms[i][j]);} 

for(i=0;i<n;i++) 
{ 
for(j=0;j<n;j++) 
printf("%3d",ms[i][j]); 
puts("\n"); 
} 
d=det(ms,n); 
printf("Determinant is %d\n",d); 
getch(); 
} 

float det(float**ms,int n) 
{ 
int i,j,z,a,d; 
int q=0; 
int **ms1; 
 if(n==2){q=ms[0][0]*ms[1][1]-ms[0][1]*ms[1][0];} 
  else 
   { 
            ms1=calloc(n,sizeof(float*));
            for(i=0;i<n;i++)
            {
                *(ms1+i)=calloc(n,sizeof(float));
            }

       for(i=0;i<n;i++) 
    { 
      for(j=0;j<n-1;j++) 
      for(z=0;z<n;z++) 
         { 
          if(j<i) 
          ms1[z][j]=ms[z][j]; 
          else 
          ms1[z][j]=ms[z][j+1]; 
         } 
    q+=pow(-1,i+n+1)*det(ms1,n-1)*ms[n-1][i]; 
     } 
       } 

return q; 
}

Цитата

Коль у меня алгоритм даёт неверный результат - так и скажи.

Ты зла не держи, я ж обидеть не хотел! smile