VPF::найти определитель для динамич. матрицы

wolver17

Дата 6.4.2012, 19:28 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 45
Регистрация: 15.5.2011

Репутация: нет
Всего: 1

Значит, собственно нужно найти определитель любой квадратной матрицы. Нашёл в Инете код, работает для любой матрицы, хоть 3*3 хоть 10*10, но он на pascal'e...
Переделал в cpp и переделал в динамич. массивы - в итоге считает только для 3*3, 4*4, если выше брать размерность матрицы, начинаются глюки в рекурсивно высчитываемых минорах, не могу разобраться где исправить, чтобы заработало так же прекрасно как и на pascal(((
Помогите пожалуйста!
Ниже привожу исходник на pascal и мой cpp-код:

Код


const n=4; { размерность матрицы }
type matr=array[1..n,1..n] of longint;
var a,b:matr;
    i,j,dt,z:longint;
procedure PrintMatr(m:matr;n:integer);
{ процедура вывода матрицы на экран }
var i,j:integer;
  begin
  for i:=1 to n do
    begin
    for j:=1 to n do
      write(m[i,j]:3);
    writeln;
    end;
  end;
procedure GetMatr(a:matr; var b:matr; m,i,j:integer);
{ Вычеркивание из матрицы строки и столбца }
var ki,kj,di,dj:integer;
  begin
  di:=0;
  for ki:=1 to m-1 do
    begin
    if (ki=i) then di:=1;
    dj:=0;
    for kj:=1 to m-1 do
      begin
      if (kj=j) then dj:=1;
      b[ki,kj]:=a[ki+di,kj+dj];
      end;
    end;
  end;
Function Determinant(a:matr;n:integer):longint;
{ Вычисление определителя матрицы }
var i,j,d,k:longint;
    b:matr;
  begin
  d:=0; k:=1;
  if (n<1) then
    begin
    writeln('Determinant: Cann''t run. N=',n); halt;
    end;
  if (n=1)
    then d:=a[1,1]
  else if (n=2)
    then d:=a[1,1]*a[2,2]-a[2,1]*a[1,2]
  else { n>2 }
    for i:=1 to n do
      begin
      GetMatr(a,b,n,i,1);
      writeln('i=',i,' a[',i,',1]=',a[i,1]);
      PrintMatr(b,n-1);
      d:=d+k*a[i,1]*Determinant(b,n-1);
      k:=-k;
      end;
  Determinant:=d;
  end;
begin
{ Заполнение матрицы случайными числами }
randomize;
z:=1;
for i:=1 to n do
for j:=1 to n do
begin
  a[i,j]:=z;{random(5);}
  z:=z+1;
end;
{ Печать исходной матрицы }
PrintMatr(a,n);
{ Вычисление и вывод определителя }
dt:=Determinant(a,n);
writeln('=========');
writeln('Determinant=',dt);
end.

Код


#include<iostream.h>
#include<conio.h>
#include<math.h>
#include<stdlib.h>
#include<process.h>
int n=5;         // размерность матрицы
void PrintMatr(float **,int);
float Determinant(float **, int);
float **a,**b;
int i,j,z=0;
float dt;
void main()
{
clrscr();
randomize();    //заполнение матрицы рандом числами от 0 до 5
a=new float*[n];
for(int i=0;i<n;i++)
{
   a[i]=new float[n];
   for(int j=0;j<n;j++)
   {
      a[i][j]=random(5);
   }
}
PrintMatr(a,n);      //печать исходной матрицы
getch();
dt=Determinant(a,n); //вычисление и вывод детерминанта
cout<<"========="<<endl;
cout<<"Determinant="<<dt<<endl;
getch();
for(i=0;i<n;i++)
{
delete []a[n];
delete []b[n];
}
}

//-----------вывод матрицы на экран-------------------------------
void PrintMatr(float **m,int n)
{
int i,j;
  for(i=0;i<n;i++)
  {
     for(int j=0;j<n;j++)
    cout<<m[i][j]<<" ";
  cout<<endl;
  }
}

// --------------вычёркивание из матрицы строки и столбца------------------
void GetMatr(float **a, float **b, int m,int i,int j)
{
int ki,kj,di,dj;
  di=0;
  for(ki=0;ki<m-1;ki++)
  {
  if (ki==i)
     di=1;
  dj=0;
  for(kj=0;kj<m-1;kj++)
  {
  if (kj==j)
     dj=1;
  b[ki][kj]=a[ki+di][kj+dj];
  }
  }
}

//-------------вычисление детерминанта матрицы-----------------------
float Determinant(float **a, int n)
{
int i,j,d,k;
float **b=new float*[n];
/*if(z==0)    
{
for(int i=0;i<n;i++) //хз надо или нет 
{
   b[i]=new float[n];
   for(int j=0;j<n;j++)
   {
      b[i][j]=0;
   }
}
}
z=1;*/
  d=0;
  k=1;
  if(n<1)
  {
  cout<<"Determinant: Cann''t run. N="<<n;
  exit(1);
  }
  if(n==1)
     d=a[0][0];
  else
  if(n==2)
     d=a[0][0]*a[1][1]-a[1][0]*a[0][1];
  else // n>2
     for(i=0;i<n;i++)
     {
    GetMatr(a,b,n,i,0);
    {
    cout<<"i="<<i<<" a["<<i<<",0]="<<a[i][0]<<endl; //пошаговое получение миноров матрицы,
    PrintMatr(b,n-1);                                                       //можно закоментить, если не надо.   
    getch();
    }
    d=d+k*a[i][0]*Determinant(b,n-1);
    k=-k;
     }
return(d);
}

disputant

Дата 6.4.2012, 19:37 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 210
Регистрация: 28.11.2011

Репутация: нет
Всего: 3

Цитата(wolver17 @ 6.4.2012, 19:28)

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

Я бы сказал так - метод, который O(n!), и не должен применяться для матриц больше 4x4 smile

Что бы не воспользоваться обычным простым O(n^3) методом?...

Скажу честно - не разбирался с вашим кодом, но сразу видно, что с памятью у вас (в смысле, у программы smile

), мягко говоря, нехорошо...

Например, вы удаляете a[i], но не удаляете выделенную память в a, удаляете в main память, выделенную для b[i], но нигде ее не выделяете (в Determinant не в счет, там b - локальная переменная, и, кстати, память там не освобождается...

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

Это сообщение отредактировал(а) disputant - 6.4.2012, 19:44

wolver17

Дата 6.4.2012, 19:47 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 45
Регистрация: 15.5.2011

Репутация: нет
Всего: 1

Цитата(disputant @ 6.4.2012, 19:37)

Цитата(wolver17 @ 6.4.2012, 19:28)

Я бы сказал так - метод, который O(n!), и не должен применяться для матриц больше 4x4 smile

Что бы не воспользоваться обычным простым O(n^3) методом?...

затем, что мне в проекте надо считать до 10*10 матрицы.
и чем вам не угождает больше 3*3? переполнения дин. памяти там нету. и на паскале ж работает любой размер, чем вдруг с++ хуже?

Добавлено @ 19:55
[QUOTE=disputant,6.4.2012, 19:37]

Цитата(17 @ 6.4.2012, 19:28)

Например, вы удаляете a[i], но не удаляете выделенную память в a, удаляете в main память, выделенную для b[i], но нигде ее не выделяете (в Determinant не в счет, там b - локальная переменная, и, кстати, память там не освобождается...

разве я не правильно освобождаю память в delete для двумерн. массива? насчёт b[i] - не могу никак прокоментить сам хз smile

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

Это сообщение отредактировал(а) wolver17 - 6.4.2012, 19:56

disputant

Дата 6.4.2012, 23:03 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 210
Регистрация: 28.11.2011

Репутация: нет
Всего: 3

Цитата(wolver17 @ 6.4.2012, 19:47)

C++ не хуже smile

Просто если тривиальным методом приведения к треугольной матрице определитель матрицы 10x10 будет считаться грубо в 30 раз дольше определителя 3x3, то рекурсивным методом по минорам - в 600000 раз, только и всего...

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

Код


double * a = new double[n*n];

(правда, при этом обращение a[i][j] не работает, его надо заменять на a[i*n+j] (можно выкручиваться иначе, чтобы работала запись с двумя индексами, но стоит ли оно того?)

и не забывайте освобождать память там, где выделили...

Это сообщение отредактировал(а) disputant - 6.4.2012, 23:08

wolver17

Дата 6.4.2012, 23:34 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 45
Регистрация: 15.5.2011

Репутация: нет
Всего: 1

Цитата(disputant @ 6.4.2012, 23:03)

не столь важно, что скорость упадёт, не на калькуляторе ж считаем))
тем более, если паскаль считает на ура, то я 100% уверен, что и с++ будет тоже считать так же.
проблема только в том, что возможно где-то при конвертации с паскаля на с++ я допустил ошибку, но никак не могу найти где...
если раскоментить три строки кода, которые отвечает за вывод на экран миноров + вычеркнутый элем. алгебраич. дополнения, - видно, что в матрице > 4*4 первые пару итераций рекурсии идут норм, а вот потом начинаются сбои в числах.
по debug не могу понять где проблема(
если кто-то сможет перекодировать паскаль-код (он 100% рабочий!) на с++ или поможет найти в моём коде ошибку, буду очень очень признателен!!!

disputant

Дата 7.4.2012, 09:00 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 210
Регистрация: 28.11.2011

Репутация: нет
Всего: 3

Мля, ну если так важно именно таким...
Вот втупую переведенный на C++ код. Проверять не стал, смотрите сами.

Только еще раз говорю - не метод это! Как и ожидалось, если для 10 он мучил 4 (!!!) секунды (что там делать 4 секунды нормальным способом?!), то для 11 - уже 43 секунды...

Код


#include <stdio.h>
#include <stdlib.h>

const int n = 4; // размерность матрицы
typedef int matr[n][n];

void PrintMatr(const matr& m, int n)
{
    // процедура вывода матрицы на экран
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            printf(" %3d", m[i][j]);
    printf("\n");
}

void GetMatr(const matr& a, matr& b, int m, int i, int j)
{
    // Вычеркивание из матрицы строки и столбца
    int ki, kj, di, dj;
    di = 0;
    for(ki = 1; ki < m; ++ki)
    {
        if (ki == i) di = 1;
        dj = 0;
        for(kj = 1; kj < m; ++kj)
        {
            if (kj == j) dj = 1;
            b[ki-1][kj-1] = a[ki+di-1][kj+dj-1];
        }
    }
}

int Determinant(const matr& a, int n)
{
    // Вычисление определителя матрицы
    int i, j, d, k;
    matr b;
    d = 0; k = 1;
    if (n < 1) {
        printf("Determinant: Cann't run. N= %d\n",n);
        abort();
    } else if (n == 1)
    {
        d = a[0][0];
    } else if (n == 2)
    {
        d = a[0][0]*a[1][1]-a[1][0]*a[0][1];
    } else
    {
        for(i = 1; i <= n; ++i)
        {
            GetMatr(a,b,n,i,1);
            printf("i= %d  a[%d,1] = %d\n",i,i,a[i-1][0]);
            PrintMatr(b,n-1);
            d += k * a[i-1][0]*Determinant(b,n-1);
            k = -k;
        }
    }
    return d;
}

int main()
{
    matr a,b;
    int  i, j, dt, z;
    // Заполнение матрицы случайными числами
    z = 1;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            a[i][j] = rand()%5;
    // Печать исходной матрицы
    PrintMatr(a,n);
    // Вычисление и вывод определителя
    dt = Determinant(a,n);
    printf("=========\n");
    printf("Determinant = %d\n",dt);
}

borisbn

Дата 7.4.2012, 11:39 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 21
Всего: 135

Вот готовое решение. Здесь же. На vigrad'e.

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »