Алгоритм детерминанта матрицы C++

Я новичок в программировании, и я искал способ найти определитель матрицы. Я нашел этот код в Интернете, но у меня возникли проблемы с пониманием алгоритма здесь. У меня нет проблем с базой рекурсии, но у меня проблемы с пониманием продолжения и основного цикла. Большое спасибо всем, кто может объяснить мне алгоритм.

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;
  }
}

c++ algorithm matrix determinants
person user3144334    schedule 19.01.2014    source источник
comment
Он вычисляет определитель из миноров. Внутренний цикл формирует миноры в temp. Кроме того, это ужасный способ вычисления определителя.   -  person Joker_vD    schedule 19.01.2014
comment
@user3144334 user3144334 Младший — это матрица с одной отброшенной строкой и одним столбцом. Во всех младших классах отбрасывается первая строка, и чтобы отбросить столбец p, вы должны пропустить его при копировании элементов из a в temp.   -  person Joker_vD    schedule 19.01.2014
comment
Вычисление определителя со сверхэкспоненциальной сложностью, молодец... и даже pow(-1,p), чтобы с первого взгляда было видно, насколько хорош код...   -  person Marc Glisse    schedule 19.01.2014

Ответы (1)


arrow_upward
7
arrow_downward

Этот алгоритм использует подход «разделяй-властвуй» для решения задачи (нахождение определителя матрицы N*N).

Алгоритм использует рекурсивный шаблон, который является одним из подходов «разделяй и властвуй». Вы можете узнать это, заметив, что алгоритм вызывает сам себя в третьем операторе условия.

У каждого рекурсивного алгоритма есть условие выхода, которое является первым оператором if в вашем коде. и они также содержат раздел, который является решением самой удобной проблемы или атомарной проблемой основной большой проблемы, которую трудно решить в первую очередь. Атомарная проблема или проблема с наибольшим количеством разделений может быть легко решена, поскольку вы можете увидеть второй оператор if вашего кода. В вашем случае это фактически решение определителя матрицы 2 * 2.

Самая важная часть вашего кода для понимания, которая тоже немного сложна, — это часть, в которой вы выполняете деление (что тоже рекурсивно!). В этой части тоже есть ключ к победе. Выполнив небольшую обратную трассировку и числовые примеры, вы можете узнать это:

det = det + a[0][p] * pow(-1,p) * determ(temp,n-1);

Для окончательного предложения попробуйте матрицу 3 * 3, для которой требуется только одно деление. Удачи с этим.

Эта книга отлично подходит для начала изучения и понимания алгоритмов

person Novin Shahroudi    schedule 19.01.2014
comment
Большое спасибо, я только хочу спросить, что делает оператор continue? если j == p, то вы переходите сразу к det=det+a[0][p]*pow(-1,p)*determ(temp,n-1); или что-то другое ? - person user3144334; 19.01.2014
comment
@user3144334 user3144334 О, вы просто не знаете, что делает continue... for (...) { if (x) { continue; } b; c; } эквивалентно for (...) { if (!x) { b; c; } }. - person Joker_vD; 19.01.2014
comment
Он продолжает цикл for для еще одного выполнения. проверьте это: cplusplus.com/doc/tutorial/control — продолжить можно используется во всех операторах с условием: tutorialspoint.com/cplusplus/cpp_continue_statement.htm - person Novin Shahroudi; 19.01.2014