c++ - 行列式アルゴリズム C++

Question

私はプログラミングが初めてで、行列式を見つける方法を探していました。このコードはオンラインで見つけましたが、ここにあるアルゴリズムを理解するのに苦労しています。recursion のベースには問題ありませんが、continue と main ループが理解できません。アルゴリズムを説明できる人に感謝します。

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

Answer 1

このアルゴリズムは、分割統治法を使用して問題を解決します (N*N 行列の行列式を見つけます)。

このアルゴリズムは、分割統治アプローチの 1 つである再帰パターンを使用します。これは、アルゴリズムが 3 番目の条件ステートメントで自分自身を呼び出していることに気付くとわかります。

すべての再帰アルゴリズムには、コード内の最初の if ステートメントである終了条件があります。また、そもそも解決するのが難しい主要な大きな問題の最も便利な問題またはアトミックな問題の解決策であるセクションも含まれています。コードの 2 番目の if ステートメントを見ると、アトミックな問題または最も分割された問題を簡単に解決できます。あなたの場合、実際には 2*2 マトリックスの行列式を解いています。

少し難しいコードを理解するための最も重要な部分は、除算を行う部分です (これも再帰的です!)。この部分は、どちらかを征服するための鍵を握っています。少しバックトレースと数値例を実行することで、それを見つけることができます:

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

最後の提案として、1 つの分割しか必要としない 3*3 行列を試してください。頑張ってください。

この本は、アルゴリズムの研究と理解を始めるのに最適な本です。