Форум программистов, компьютерный форум CyberForum.ru

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 47, средняя оценка - 4.60
GennDALF
 Аватар для GennDALF
12 / 12 / 0
Регистрация: 24.09.2009
Сообщений: 61
11.10.2009, 08:15     Определитель n-ого порядка (непорядок с рекурсией) #1
Всем доброго времени суток!
Написал программу, которая должна считать определитель заданного порядка разложением на миноры.
Вроде уже дописал программу, но при проверке понял, что прога правильно считает только второго порядка определители, где происходит только один рекурсивный вызов.
При всех остальных порядках прога, разложив наконец до числа, этим не удовлетворяется и снова раскладывает исходную матрицу, только уже по-другим строке и столбцу
я никак не могу понять, где я забыл поставить условие выхода.
Помогите, пожалуйста, кому не лень!
C++
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#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 минут
Блин, сорри туплю! Миноры-то он правильно все выдает! Ошибка где-то в вычислениях уже, все не могу понять где..
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.10.2009, 08:15     Определитель n-ого порядка (непорядок с рекурсией)
Посмотрите здесь:

C++ Вычислить определитель квадратной матрицы второго порядка
C++ Задача с рекурсией
с++ с рекурсией C++
C++ Определитель 2мерной матрицы n-порядка
C++ Вычислить определитель матрицы третьего порядка
C++ Вычислить определитель квадратной матрицы третьего порядка
C++ Найти определитель заданной матрицы n-го порядка методом Гаусса
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
GennDALF
 Аватар для GennDALF
12 / 12 / 0
Регистрация: 24.09.2009
Сообщений: 61
13.10.2009, 14:11  [ТС]     Определитель n-ого порядка (непорядок с рекурсией) #2
что, неужели всем так лень?
mamedovvms
2915 / 836 / 93
Регистрация: 30.04.2009
Сообщений: 2,614
14.10.2009, 06:50     Определитель n-ого порядка (непорядок с рекурсией) #3
что, неужели всем так лень?
не лень, просто я уже и не помню как(математически) можно посчитать определитель матрици.
не помню как разложить на миноры, а времени читать и вспоминать это все нет
GennDALF
 Аватар для GennDALF
12 / 12 / 0
Регистрация: 24.09.2009
Сообщений: 61
14.10.2009, 08:12  [ТС]     Определитель n-ого порядка (непорядок с рекурсией) #4
Это просто - я объясню =)
Чтобы посчитать определитель можно разложить исходную квадратную матрицу по строке или столбцу (лучше это делать там где больше всего нулей). Минор - это матрица, на один порядок меньше исходной. Чтобы получить минор, из исходной матрицы вырезают одну строку и столбец. Вообще процесс разложения таков:
пусть дана исходная матрица 5х5. Тогда если мы раскладываем по первой строке, то надо первый элемент первой строки умножить на (-1) в степени (номер строки + номер столбца), (т.е. в нашем случае 1+1), и умножить на определитель от минора, полученного вырезанием первой строки и первого столбца. Дальше +, и уже второй элемент первой строки умножаем на (-1) в степени (1+2) и умножаем на минор, полученный вырезанием первой строки и второго столбца... и т.д. Но если у нас появляется в каком-то из произведений 0, то это существенно облегчит и ускорит расчеты. Именно поэтому лучше проверять где больше нулей. Раскладывать можно как по строке, так и по столбцу, но тогда у нас вместо строки, постоянно вырезается один и тот же столбец, а индекс вырезаемой строки увеличивается на один.
Чтобы посчитать определитель в каждом слагаемом, я использую рекурсию.
вот вобщем и вся недолга.. =)
Миниатюры
Определитель n-ого порядка (непорядок с рекурсией)  
Изображения
 
mamedovvms
2915 / 836 / 93
Регистрация: 30.04.2009
Сообщений: 2,614
14.10.2009, 08:27     Определитель n-ого порядка (непорядок с рекурсией) #5
как я понимаю, если у нас нет строки где есть нуливые элементы то у нас получится что надо :
берем первый символ первой строки умножаем его на определитель минора , который состоит из всех столбцов и строк кроме тех на пересечении которых находится наш элемент,и так делаем для всех элементов строки, затем оналогично делаем для миноров, и все это делается пока не останется один элемент???
GennDALF
 Аватар для GennDALF
12 / 12 / 0
Регистрация: 24.09.2009
Сообщений: 61
14.10.2009, 08:55  [ТС]     Определитель n-ого порядка (непорядок с рекурсией) #6
Именно так. Если разложить матрицу второго порядка, то ее минором будет целое единственное число.
Только у меня в программе порядок немного другой. Нельзя ведь умножать int на **int, поэтому я сразу вызываю рекурсию и высчитываю все определители первого же минора.
mamedovvms
2915 / 836 / 93
Регистрация: 30.04.2009
Сообщений: 2,614
14.10.2009, 08:59     Определитель n-ого порядка (непорядок с рекурсией) #7
я подумаю как можно ее решить без рекурсии, и постараюсь решить
GennDALF
 Аватар для GennDALF
12 / 12 / 0
Регистрация: 24.09.2009
Сообщений: 61
14.10.2009, 09:17  [ТС]     Определитель n-ого порядка (непорядок с рекурсией) #8
А вы думаете что проблема все-таки в рекурсии? Я просто когда еще тему создавал сглупил немного, решил что прога где-то там сбивается, но потом сделал вывод всех миноров и понял что они выводятся правильно, так как и надо. Единственная проблема - это число, которое он выдает, не сходится ни с моими ручными расчетами, ни с Маткадом. Вот я и не знаю где именно ошибка.

Добавлено через 9 минут
кстати, я тут задумался... программа-то все равно на ноль умножает... даже если есть ноль в произведении, она все равно будет считать все следующие миноры.
Добавил в функцию body() условие:
C++
1
2
3
4
5
6
7
8
9
10
11
12
// ....
      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
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
14.10.2009, 10:16     Определитель n-ого порядка (непорядок с рекурсией) #9
http://ru.wikipedia.org/wiki/%D0%9E%...B5%D0%BB%D1%8C

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

Добавлено через 3 минуты
надо сначала писать вычисление определителя третьего порядка рекурсивным способом, а потом его расширять до n-ого
GennDALF
 Аватар для GennDALF
12 / 12 / 0
Регистрация: 24.09.2009
Сообщений: 61
14.10.2009, 10:22  [ТС]     Определитель n-ого порядка (непорядок с рекурсией) #10
У меня переменные, написанные в верхнем регистре - это аргументы, переданные в функцию, а констант в этой программе нет. Определенны ВСЕ переменные, кроме счетчиков в циклах, в начале функции.

как-то странно... зачем так делать?
mamedovvms
2915 / 836 / 93
Регистрация: 30.04.2009
Сообщений: 2,614
14.10.2009, 10:23     Определитель n-ого порядка (непорядок с рекурсией) #11
я придумал как сделать, постараюсь сегодня реализовать
GennDALF
 Аватар для GennDALF
12 / 12 / 0
Регистрация: 24.09.2009
Сообщений: 61
14.10.2009, 21:03  [ТС]     Определитель n-ого порядка (непорядок с рекурсией) #12
А можете сказать, какие у вас мысли есть - я бы тоже подумал... ))
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.11.2009, 06:45     Определитель n-ого порядка (непорядок с рекурсией)
Еще ссылки по теме:

C++ Наибольший элемент матрици н-ого порядка в заштрихованной области
C++ Программа,вычисляющая определитель n порядка
C++ Бинарное с рекурсией
C++ Вывести на экран значения 0-ого, 3-ого и 13-ого битов числа n в формате short int
Определитель матрицы n-го порядка C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
GennDALF
 Аватар для GennDALF
12 / 12 / 0
Регистрация: 24.09.2009
Сообщений: 61
02.11.2009, 06:45  [ТС]     Определитель n-ого порядка (непорядок с рекурсией) #13
Уфф! Наконец-то доделал!
Воистину глобальными переменными вымощена дорога в ад программирования! Вчера я это понял со всей отчетливостью.
Проблема была в том, что переменная det не обнулялась при каждом новом рекурсивном вызове. Поэтому надо в рекурсивной функции объявить внутреннюю переменную и каждый раз ее заново инициализировать.
Итак, код:
C++
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
#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 Мб памяти и вылетела
Впринципе, сколько я понимаю, можно попытаться расширить возможности, но я не очень ясно представляю, как это сделать.
Yandex
Объявления
02.11.2009, 06:45     Определитель n-ого порядка (непорядок с рекурсией)
Ответ Создать тему
Опции темы

Текущее время: 02:02. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru