Матричный определитель алгоритма переполнения стека
Я новичок в программировании, и я искал способ найти определитель матрицы. Я нашел этот код в сети, но у меня возникли проблемы с пониманием алгоритма здесь. У меня нет проблем для основы рекурсии, но у меня есть проблемы с пониманием продолжения и основного цикла. Большое спасибо всем, кто может объяснить мне алгоритм.
int determ(int a[MAX][MAX],int n) {
int det=0, p, h, k, i, j, temp[MAX][MAX];
if(n==1) {
return a[0][0];
} else if(n==2) {
det=(a[0][0]*a[1][1]-a[0][1]*a[1][0]);
return det;
} else {
for(p=0;p<n;p++) {
h = 0;
k = 0;
for(i=1;i<n;i++) {
for( j=0;j<n;j++) {
if(j==p) {
continue;
}
temp[h][k] = a[i][j];
k++;
if(k==n-1) {
h++;
k = 0;
}
}
}
det=det+a[0][p]*pow(-1,p)*determ(temp,n-1);
}
return det;
}
}
Решение
Этот алгоритм использует подход «разделяй и властвуй» для решения задачи (поиска определителя матрицы N * N).
Алгоритм использует рекурсивный шаблон, который является одним из подходов «разделяй и властвуй». Вы можете узнать это, заметив, что алгоритм вызывает себя в третьем условии.
Каждый рекурсивный алгоритм имеет условие выхода, которое является первым оператором if в вашем коде. и они также содержат раздел, который является решением наиболее удобной проблемы или атомарной проблемы главной большой проблемы, которую трудно решить в первую очередь. Атомарная проблема или наиболее разделенная проблема может быть легко решена, как вы можете видеть во втором операторе if вашего кода. В вашем случае это фактически решение определителя матрицы 2 * 2.
Самая важная часть вашего кода для понимания, которая тоже немного сложна, — это часть, которую вы делите (что тоже рекурсивно!).
Эта часть имеет ключ к победе либо. Делая небольшой обратный след и числовые примеры, вы можете узнать это:
det = det + a[0][p] * pow(-1,p) * determ(temp,n-1);
Для окончательного предложения попробуйте матрицу 3 * 3, для которой требуется только одно деление.
Удачи с этим.
Эта книга — отличное начало для изучения и понимания алгоритмов.
Другие решения
Других решений пока нет …