C++で上三角行列と下三角行列の合計を求める方法

この問題では、1つの行列が与えられます。私たちのタスクは、上三角部分と下三角部分の要素の合計をそれぞれ計算し、出力するプログラムを作成することです。

下三角行列とは

下三角行列とは、主対角線より上の要素がすべて 0 である行列のことです。対角線上およびその下側の要素のみが値を持ちます。

M00   0   0   …   0
M10   M11   0   …   0
M20   M21   M22   …   0
…
Mrow0   Mrow1   Mrow2   …   Mrow col

上三角行列とは

上三角行列とは、主対角線より下の要素がすべて 0 である行列のことです。対角線上およびその上側の要素のみが値を持ちます。

M00   M01   M02   …   M0col
0   M11   M12   …   M1col
0   0   M22   …   M2col
…
0   0   0   …   Mrow col

例で問題を理解しよう

入力: {{5, 1, 6}
{8, 2, 0}
{3, 7, 4}}
出力: 上三角の合計 = 18
下三角の合計 = 29
説明:
上三角の合計 = 5 + 1 + 6 + 2 + 0 + 4 = 18
下三角の合計 = 5 + 8 + 2 + 3 + 7 + 4 = 29

この問題に対するシンプルな解決策は、ループを使って配列を走査し、上三角要素と下三角要素をそれぞれ判別する方法です。条件としては、上三角は i <= j(行番号が列番号以下)、下三角は j <= i(列番号が行番号以下) を満たす要素が対象となります。それぞれの合計を、別々の変数 lSum と uSum に加算していきます。

実装例

この解決策の動作を示すプログラムは以下の通りです。

#include <iostream>
using namespace std;
int row = 3;
int col = 3;
void sum(int mat[3][3]) {
    int i, j;
    int uSum = 0;
    int lSum = 0;
    for (i = 0; i < row; i++)
       for (j = 0; j < col; j++) {
          if (i <= j) {
          uSum += mat[i][j];
      }
   }
   cout<<"上三角の合計は "<<uSum<<endl;
   for (i = 0; i < row; i++)
      for (j = 0; j < col; j++) {
          if (j <= i) {
             lSum += mat[i][j];
      }
   }
   cout<<"下三角の合計は "<<lSum<<endl;
}
int main() {
   int mat[3][3] = { { 5, 1, 6 },
                     { 8, 2, 0 },
                     { 3, 7, 4 }};
   sum(mat);
   return 0;
}

出力

上三角の合計は 18
下三角の合計は 29

このように、行列を一度走査するだけで、時間計算量 O(n²) で上三角と下三角の合計を効率的に求めることができます。条件分岐の判定式を正しく設定することが、この問題を解くポイントです。