Определитель n-ого порядка (непорядок с рекурсией)

@GennDALF · Регистрация: 24.09.2009

Author24 — интернет-сервис помощи студентам

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

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

C++

#include <iostream>
#include <math.h>
#include <conio.h>
using namespace std;
 
void check_zero(int ** MATRIX, int ORDER, int *LC_NUMBER, bool *LC_CHECK);
int ** matrix_cut(int ** MATRIX, int ORDER, int CUT_LINE_NUMBER, int CUT_COLUMN_NUMBER);
int body(int ** MATRIX, int ORDER, int *LC_NUMBER, bool *LC_CHECK);
void matrix_output(int ** MATRIX, int STRINGS, int COLUMNS);
 
int LC = 0;
bool LC_ch = false;
double det = 0;
 
int main()
{
      int ord;
      
      cout << "<=N-th ORDER DETERMINANT=>\n\nEnter the order of determinant: ";
      cin >> ord;
 
      while (ord != -1)
      {
            int ** mat_det = new int * [ord];
            for (int c = 0; c < ord; c++)
                  mat_det[c] = new int [ord];
 
            cout << "\nEnter the matrix: \n\n";
            for (int i = 0; i < ord; i++) {
                  for (int j = 0; j < ord; j++) {
                        cout << "a" << i+1 << "_" << j+1 << " = ";
                        cin >> mat_det[i][j];
                  }
                  cout << endl;
            }
 
            matrix_output(mat_det, ord, ord);         // вывод исходной матрицы на экран
                                                      // красиво смотрится кстати
            
            {                                         // старт расчета, запуск рекурсии
            check_zero(mat_det, ord, &LC, &LC_ch);    
            body(mat_det, ord, &LC, &LC_ch);
            }
 
            cout << "Determinant = " << det;
            getch();
 
            {                                         // блок обнуления переменных
            for (int c = 0; c < ord; c++)
                  delete [] mat_det[c];
            delete [] mat_det;
            LC = 0; LC_ch = false;
            det = 0;
            }     
 
            cout << "\n\nEnter the order of determinant: ";
            cin >> ord;
      }
 
      return 0;
}
 
 
int body(int ** MATRIX, int ORDER, int *LC_NUMBER, bool *LC_CHECK)
{
      if (ORDER == 1)                           // если наконец разложили до первого порядка, то возвращаем число
            return MATRIX[0][0];
      else {
            if (*LC_CHECK) {                    // если раскладываем по строке, то так 
                  for (int i = 0; i < ORDER; i++) {
                        det += pow(-1, *LC_NUMBER + i) * MATRIX[*LC_NUMBER][i] * 
                              body( matrix_cut(MATRIX, ORDER, *LC_NUMBER, i), ORDER-1, &LC, &LC_ch);  
                  }
            }
            else {                              // если по столбцу, то так.. фишка здесь в смене индексов
                  for (int i = 0; i < ORDER; i++) {
                        det += pow(-1, i + *LC_NUMBER) * MATRIX[i][*LC_NUMBER] * 
                              body( matrix_cut(MATRIX, ORDER, i, *LC_NUMBER), ORDER-1, &LC, &LC_ch);
                  }
            }
      }
}
 
 
void check_zero(int ** MATRIX, int ORDER, int *LC_NUMBER, bool *LC_CHECK)
{     // смотрим в какой строке или в каком столбце больше нулей
      // в глобальную переменную LC присваивается номер строки или столбца
      // а в такую же глобальную LC_ch присваивается true для строки и false для столбца
 
      int ch_L = 0, ch_C = 0, max_L = 0, max_C = 0, line_num = 0, col_num = 0;
 
      for (int i = 0; i < ORDER; i++)
      {
            for (int j = 0; j < ORDER; j++)
            {
                  if (MATRIX[i][j] == 0)
                  {
                        ch_L++;
                        if (j == ORDER-1 && max_L < ch_L) {
                              max_L = ch_L;
                              line_num = i;
                        }
                  }                       // фишка опять в смене индексов
                  if (MATRIX[j][i] == 0)
                  {
                        ch_C++;
                        if (j == ORDER-1 && max_C < ch_C) {
                              max_C = ch_C;
                              col_num = i;
                        }
                  }
            }
            ch_L = 0; ch_C = 0;
      }
      if (max_L >= max_C) {
            *LC_CHECK = true;
            *LC_NUMBER = line_num;
      }
      else {
            *LC_CHECK = false;
            *LC_NUMBER = col_num;
      }
}
 
 
int ** matrix_cut(int ** MATRIX, int ORDER, int CUT_LINE_NUMBER, int CUT_COLUMN_NUMBER)
{     // делает минор из матрицы n-ого порядка, т.е. создает матрицу (n-1)ого порядка с вырезанными строкой и столбцом
 
      int order_new = ORDER - 1;
      int **mat_new = new int *[order_new];
      for (int c = 0; c < ORDER-1; c++)
            mat_new[c] = new int [order_new];
 
      int m=0, n=0;
      for (int i = 0; i < ORDER; i++) {
            if (i != CUT_LINE_NUMBER) {
                  for (int j = 0; j < ORDER; j++) {
                        if (j != CUT_COLUMN_NUMBER) {
                              mat_new[m][n] = MATRIX[i][j];
                              n++;
                        }
                        else
                              continue;
                  }
                  m++;
                  n=0;
            }
            else
                  continue;
      }
 
      //check_zero(mat_new, order_new, &LC, &LC_ch);
      matrix_output(mat_new, order_new, order_new);
      cout << endl;
      getch();
      return mat_new;
}
 
 
void matrix_output(int ** MATRIX, int STRINGS, int COLUMNS) {
      if (STRINGS == 1) {
            for (int c = 0; c < COLUMNS; c++)
                  cout << " " << MATRIX[0][c];
      }
      else {
            for (int c = 0; c < STRINGS; c++) {
                  if (c == 0) 
                        cout << '\x2f';
                  else if (c == STRINGS-1)
                        cout << '\x5c';
                  else
                        cout << '\x7c';
 
                  for (int d = 0; d < COLUMNS; d++)
                        cout << " " << MATRIX[c][d];
                  
                  if (c == 0) 
                        cout << " " << '\x5c';
                  else if (c == STRINGS-1)
                        cout << " " << '\x2f';
                  else
                        cout << " " << '\x7c';
 
                  cout << endl;
            }
            cout << endl;
      }
}

Добавлено через 26 минут
Блин, сорри туплю! Миноры-то он правильно все выдает! Ошибка где-то в вычислениях уже, все не могу понять где..

@GennDALF · 13.10.2009, 14:11 **[ТС]**

что, неужели всем так лень?

@mamedovvms · 14.10.2009, 06:50

что, неужели всем так лень?

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

@GennDALF · 14.10.2009, 08:12 **[ТС]**

Это просто - я объясню =)
Чтобы посчитать определитель можно разложить исходную квадратную матрицу по строке или столбцу (лучше это делать там где больше всего нулей). Минор - это матрица, на один порядок меньше исходной. Чтобы получить минор, из исходной матрицы вырезают одну строку и столбец. Вообще процесс разложения таков:
пусть дана исходная матрица 5х5. Тогда если мы раскладываем по первой строке, то надо первый элемент первой строки умножить на (-1) в степени (номер строки + номер столбца), (т.е. в нашем случае 1+1), и умножить на определитель от минора, полученного вырезанием первой строки и первого столбца. Дальше +, и уже второй элемент первой строки умножаем на (-1) в степени (1+2) и умножаем на минор, полученный вырезанием первой строки и второго столбца... и т.д. Но если у нас появляется в каком-то из произведений 0, то это существенно облегчит и ускорит расчеты. Именно поэтому лучше проверять где больше нулей. Раскладывать можно как по строке, так и по столбцу, но тогда у нас вместо строки, постоянно вырезается один и тот же столбец, а индекс вырезаемой строки увеличивается на один.
Чтобы посчитать определитель в каждом слагаемом, я использую рекурсию.
вот вобщем и вся недолга.. =)

@mamedovvms · 14.10.2009, 08:27

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

@GennDALF · 14.10.2009, 08:55 **[ТС]**

Именно так. Если разложить матрицу второго порядка, то ее минором будет целое единственное число.
Только у меня в программе порядок немного другой. Нельзя ведь умножать int на **int, поэтому я сразу вызываю рекурсию и высчитываю все определители первого же минора.

@mamedovvms · 14.10.2009, 08:59

я подумаю как можно ее решить без рекурсии, и постараюсь решить

@GennDALF · 14.10.2009, 09:17 **[ТС]**

А вы думаете что проблема все-таки в рекурсии? Я просто когда еще тему создавал сглупил немного, решил что прога где-то там сбивается, но потом сделал вывод всех миноров и понял что они выводятся правильно, так как и надо. Единственная проблема - это число, которое он выдает, не сходится ни с моими ручными расчетами, ни с Маткадом. Вот я и не знаю где именно ошибка.

Добавлено через 9 минут
кстати, я тут задумался... программа-то все равно на ноль умножает... даже если есть ноль в произведении, она все равно будет считать все следующие миноры.
Добавил в функцию body() условие:

C++

// ....
      if (*LC_CHECK) {  // если раскладываем по строке, то так 
            for (int i = 0; i < ORDER; i++) {
                  if (MATRIX[*LC_NUMBER][i] == 0)
                        continue;
                  else {
                        det += pow(-1, *LC_NUMBER + i) * MATRIX[*LC_NUMBER][i] * 
                              body( matrix_cut(MATRIX, ORDER, *LC_NUMBER, i), ORDER-1, &LC, &LC_ch);}
            }
      }
 
// ....

а ответ сразу другой получился, не такой как раньше

к чему бы это?..

accept · 14.10.2009, 10:16

http://ru.wikipedia.org/wiki/%... 0%BB%D1%8C

большие буквы приняты для констант
а у тебя MATRIX[*LC_NUMBER][i] где здесь переменная, где константа - сразу и не скажешь, это придётся лазить и смотреть, где они определены

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

@GennDALF · 14.10.2009, 10:22 **[ТС]**

У меня переменные, написанные в верхнем регистре - это аргументы, переданные в функцию, а констант в этой программе нет. Определенны ВСЕ переменные, кроме счетчиков в циклах, в начале функции.

как-то странно... зачем так делать?

@mamedovvms · 14.10.2009, 10:23

я придумал как сделать, постараюсь сегодня реализовать

@GennDALF · 14.10.2009, 21:03 **[ТС]**

А можете сказать, какие у вас мысли есть - я бы тоже подумал... ))

@GennDALF · 02.11.2009, 06:45 **[ТС]**

Уфф! Наконец-то доделал!
Воистину глобальными переменными вымощена дорога в ад программирования! Вчера я это понял со всей отчетливостью.
Проблема была в том, что переменная det не обнулялась при каждом новом рекурсивном вызове. Поэтому надо в рекурсивной функции объявить внутреннюю переменную и каждый раз ее заново инициализировать.
Итак, код:

C++

#include <iostream>
#include <math.h>
#include <conio.h>
using namespace std;
 
// объявление прототипов функций
void check_zero(int ** MATRIX, int ORDER, int *LC_NUMBER, bool *LC_CHECK);
int ** matrix_cut(int ** MATRIX, int ORDER, int CUT_LINE_NUMBER, int CUT_COLUMN_NUMBER);
int body(int ** MATRIX, int ORDER, int *LC_NUMBER, bool *LC_CHECK);
void matrix_output(int ** MATRIX, int STRINGS, int COLUMNS);
 
 
// объявление глобальных переменных
int LC = 0;
bool LC_ch = false;
double det = 0;
 
 
int main()
{
      int ord;
      
      cout << "<=N-th ORDER DETERMINANT=>\n\nEnter the order of determinant: ";
      cin >> ord;
 
      int ** mat_det = new int * [ord];
      for (int c = 0; c < ord; c++)
            mat_det[c] = new int [ord];
 
      while (ord != -1)
      {
            int ** mat_det = new int * [ord];
            for (int c = 0; c < ord; c++)
                  mat_det[c] = new int [ord];
 
            cout << "\nEnter the matrix: \n\n";
            for (int i = 0; i < ord; i++) {
                  for (int j = 0; j < ord; j++) {
                        cout << "a" << i+1 << "_" << j+1 << " = ";
                        cin >> mat_det[i][j];
                  }
                  cout << endl;
            }
 
            {
            matrix_output(mat_det, ord, ord);         // вывод исходной матрицы на экран
            cout << endl;                             // красиво смотрится кстати
            //getch();
            }
            
            {                                         // старт расчета, запуск рекурсии
            det = body(mat_det, ord, &LC, &LC_ch);
            }
 
            cout << "Determinant = " << det;
            getch();
 
            {                                         // блок обнуления переменных
                  for (int c = 0; c < ord; c++)
                        delete [] mat_det[c];
                  delete [] mat_det;
                  LC = 0; LC_ch = false;
                  det = 0;
            }     
 
            cout << "\n\n\nEnter the order of determinant: ";
            cin >> ord;
      }
 
      return 0;
}
 
 
int body(int ** MATRIX, int ORDER, int *LC_NUMBER, bool *LC_CHECK)
{
      double DET = 0;
 
      if (ORDER == 1)                           // если наконец разложили до первого порядка, то возвращаем число
            return MATRIX[0][0];
      else 
      {
            check_zero(MATRIX, ORDER, &LC, &LC_ch);    
 
            if (*LC_CHECK)                      // если раскладываем по строке, то так
            {   
                  for (int i = 0; i < ORDER; i++) 
                  {
                        if (MATRIX[*LC_NUMBER][i] == 0)
                              continue;
                        else 
                        {
                              DET += pow(-1, *LC_NUMBER + i) * MATRIX[*LC_NUMBER][i] * 
                                    body( matrix_cut(MATRIX, ORDER, *LC_NUMBER, i), ORDER-1, &LC, &LC_ch);
                        }
                  }
            }
            else                                // если по столбцу, то так.. фишка здесь в смене индексов
            {
                  for (int i = 0; i < ORDER; i++) 
                  {
                        if (MATRIX[i][*LC_NUMBER] == 0)
                              continue;
                        else 
                        {
                              DET += pow(-1, i + *LC_NUMBER) * MATRIX[i][*LC_NUMBER] * 
                                    body( matrix_cut(MATRIX, ORDER, i, *LC_NUMBER), ORDER-1, &LC, &LC_ch);
                        }
                  }
            }
      }
      return DET;
}
 
 
void check_zero(int ** MATRIX, int ORDER, int *LC_NUMBER, bool *LC_CHECK)
{     // смотрим в какой строке или в каком столбце больше нулей
      // в глобальную переменную LC присваивается номер строки или столбца
      // а в такую же глобальную LC_ch присваивается true для строки и false для столбца
 
      int ch_L = 0, ch_C = 0, max_L = 0, max_C = 0, line_num = 0, col_num = 0;
 
      for (int i = 0; i < ORDER; i++)
      {
            for (int j = 0; j < ORDER; j++)
            {
                  if (MATRIX[i][j] == 0)
                  {
                        ch_L++;
                        if (j == ORDER-1 && max_L < ch_L) {
                              max_L = ch_L;
                              line_num = i;
                        }
                  }                       // фишка опять в смене индексов
                  if (MATRIX[j][i] == 0)
                  {
                        ch_C++;
                        if (j == ORDER-1 && max_C < ch_C) {
                              max_C = ch_C;
                              col_num = i;
                        }
                  }
            }
            ch_L = 0; ch_C = 0;
      }
      if (max_L >= max_C) {
            *LC_CHECK = true;
            *LC_NUMBER = line_num;
      }
      else {
            *LC_CHECK = false;
            *LC_NUMBER = col_num;
      }
}
 
 
int ** matrix_cut(int ** MATRIX, int ORDER, int CUT_LINE_NUMBER, int CUT_COLUMN_NUMBER)
{     // делает минор из матрицы n-ого порядка, 
      // т.е. создает матрицу (n-1)ого порядка с вырезанными строкой и столбцом
 
      int order_new = ORDER - 1;
      int **mat_new = new int *[order_new];
      for (int c = 0; c < ORDER-1; c++)
            mat_new[c] = new int [order_new];
 
      int m=0, n=0;
      for (int i = 0; i < ORDER; i++) {
            if (i != CUT_LINE_NUMBER) {
                  for (int j = 0; j < ORDER; j++) {
                        if (j != CUT_COLUMN_NUMBER) {
                              mat_new[m][n] = MATRIX[i][j];
                              n++;
                        }
                        else
                              continue;
                  }
                  m++;
                  n=0;
            }
            else
                  continue;
      }
 
      //check_zero(mat_new, order_new, &LC, &LC_ch);
      //matrix_output(mat_new, order_new, order_new);
      //cout << endl;
      //getch();
      return mat_new;
}
 
 
void matrix_output(int ** MATRIX, int STRINGS, int COLUMNS) {
      if (STRINGS == 1) {
            for (int c = 0; c < COLUMNS; c++)
                  cout << " " << MATRIX[0][c];
      }
      else {
            for (int c = 0; c < STRINGS; c++) {
                  if (c == 0) 
                        cout << '\x2f';
                  else if (c == STRINGS-1)
                        cout << '\x5c';
                  else
                        cout << '\x7c';
 
                  for (int d = 0; d < COLUMNS; d++)
                        cout << " " << MATRIX[c][d];
                  
                  if (c == 0) 
                        cout << " " << '\x5c';
                  else if (c == STRINGS-1)
                        cout << " " << '\x2f';
                  else
                        cout << " " << '\x7c';
 
                  cout << endl;
            }
            // cout << endl;
      }
}

Точно считает 10 порядков, дальше проверять было лень.

Один раз забил матрицу 22-ого порядка: программа крепко задумалась, съела 130 Мб памяти и вылетела

Впринципе, сколько я понимаю, можно попытаться расширить возможности, но я не очень ясно представляю, как это сделать.

@GennDALF 15 / 14 / 2 Регистрация: 24.09.2009 Сообщений: 68
	13.10.2009, 14:11 [ТС]	2
	что, неужели всем так лень? 0

@mamedovvms 2923 / 844 / 324 Регистрация: 30.04.2009 Сообщений: 2,633
	14.10.2009, 06:50	3
	что, неужели всем так лень? не лень, просто я уже и не помню как(математически) можно посчитать определитель матрици. не помню как разложить на миноры, а времени читать и вспоминать это все нет 0

@GennDALF 15 / 14 / 2 Регистрация: 24.09.2009 Сообщений: 68
	14.10.2009, 08:12 [ТС]	4
	Это просто - я объясню =) Чтобы посчитать определитель можно разложить исходную квадратную матрицу по строке или столбцу (лучше это делать там где больше всего нулей). Минор - это матрица, на один порядок меньше исходной. Чтобы получить минор, из исходной матрицы вырезают одну строку и столбец. Вообще процесс разложения таков: пусть дана исходная матрица 5х5. Тогда если мы раскладываем по первой строке, то надо первый элемент первой строки умножить на (-1) в степени (номер строки + номер столбца), (т.е. в нашем случае 1+1), и умножить на определитель от минора, полученного вырезанием первой строки и первого столбца. Дальше +, и уже второй элемент первой строки умножаем на (-1) в степени (1+2) и умножаем на минор, полученный вырезанием первой строки и второго столбца... и т.д. Но если у нас появляется в каком-то из произведений 0, то это существенно облегчит и ускорит расчеты. Именно поэтому лучше проверять где больше нулей. Раскладывать можно как по строке, так и по столбцу, но тогда у нас вместо строки, постоянно вырезается один и тот же столбец, а индекс вырезаемой строки увеличивается на один. Чтобы посчитать определитель в каждом слагаемом, я использую рекурсию. вот вобщем и вся недолга.. =) Миниатюры Изображения 0

@mamedovvms 2923 / 844 / 324 Регистрация: 30.04.2009 Сообщений: 2,633
	14.10.2009, 08:27	5
	как я понимаю, если у нас нет строки где есть нуливые элементы то у нас получится что надо : берем первый символ первой строки умножаем его на определитель минора , который состоит из всех столбцов и строк кроме тех на пересечении которых находится наш элемент,и так делаем для всех элементов строки, затем оналогично делаем для миноров, и все это делается пока не останется один элемент??? 0

@GennDALF 15 / 14 / 2 Регистрация: 24.09.2009 Сообщений: 68
	14.10.2009, 08:55 [ТС]	6
	Именно так. Если разложить матрицу второго порядка, то ее минором будет целое единственное число. Только у меня в программе порядок немного другой. Нельзя ведь умножать int на **int, поэтому я сразу вызываю рекурсию и высчитываю все определители первого же минора. 0

@mamedovvms 2923 / 844 / 324 Регистрация: 30.04.2009 Сообщений: 2,633
	14.10.2009, 08:59	7
	я подумаю как можно ее решить без рекурсии, и постараюсь решить 0

accept 4866 / 3288 / 468 Регистрация: 10.12.2008 Сообщений: 10,570
	14.10.2009, 10:16	9
	http://ru.wikipedia.org/wiki/%... 0%BB%D1%8C большие буквы приняты для констант а у тебя MATRIX[LC_NUMBER][i] где здесь переменная, где константа - сразу и не скажешь, это придётся лазить и смотреть, где они определены Добавлено через 3 минуты* надо сначала писать вычисление определителя третьего порядка рекурсивным способом, а потом его расширять до n-ого 0

@GennDALF 15 / 14 / 2 Регистрация: 24.09.2009 Сообщений: 68
	14.10.2009, 10:22 [ТС]	10
	У меня переменные, написанные в верхнем регистре - это аргументы, переданные в функцию, а констант в этой программе нет. Определенны ВСЕ переменные, кроме счетчиков в циклах, в начале функции. как-то странно... зачем так делать? 0

@mamedovvms 2923 / 844 / 324 Регистрация: 30.04.2009 Сообщений: 2,633
	14.10.2009, 10:23	11
	я придумал как сделать, постараюсь сегодня реализовать 1

@GennDALF 15 / 14 / 2 Регистрация: 24.09.2009 Сообщений: 68
	14.10.2009, 21:03 [ТС]	12
	А можете сказать, какие у вас мысли есть - я бы тоже подумал... )) 0

	02.11.2009, 06:45