C++で正方行列の対角線上の最小値・最大値を求める方法

この問題では、サイズ n×n の正方行列が与えられます。求めるのは、行列の対角線上にある要素の中から最小値と最大値を見つけることです。具体的には、主対角線（左上から右下）と副対角線（右上から左下）それぞれについて、最小要素と最大要素を求めます。

問題を理解するための例

入力

mat[][] = {
    {3, 4, 7},
    {5, 2, 1},
    {1, 8, 6}
}

出力

主対角線の最小要素 = 2
主対角線の最大要素 = 6
副対角線の最小要素 = 1
副対角線の最大要素 = 7

解法アプローチ①：二重ループを使うシンプルな方法

最も基本的な解法は、ネストされたループ（二重ループ）を使う方法です。主対角線上の要素は i == j を満たす位置にあり、副対角線上の要素は i + j == n - 1 を満たす位置にあります。この条件を利用して、各対角線ごとに最大値と最小値を順番に調べていきます。

実装例

#include<iostream>
using namespace std;
void findMaxAndMinOfDiagonals(int mat[3][3], int n){
    if (n == 0)
        return;
    int pDiagMin = mat[0][0],
    pDiagMax = mat[0][0];
    int sDiagMin = mat[0][n - 1 ],
    sDiagMax = mat[0][n - 1];
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < n; j++) {
            if (i == j){
                if (mat[i][j] < pDiagMin)
                    pDiagMin = mat[i][j];
                if (mat[i][j] > pDiagMax)
                pDiagMax = mat[i][j];
            }
            if ((i + j) == (n - 1)) {
                if (mat[i][j] < sDiagMin){
                    sDiagMin = mat[i][j];
                }
                if (mat[i][j] > sDiagMax)
                    sDiagMax = mat[i][j];
            }
        }
    }
    cout<<("\nSmallest Element of Principal Diagonal : ")<<pDiagMin;
    cout<<("\nGreatest Element of Principal Diagonal : ")<<pDiagMax;
    cout<<("\nSmallest Element of Secondary Diagonal : ")<<sDiagMin;
    cout<<("\nGreatest Element of Secondary Diagonal : ")<<sDiagMax;
}
int main(){
    int mat[3][3] = {
        { 3, 4, 7 },
        { 0, 2, 1 },
        { 1, 7, 8 }
    };
    int n = sizeof(mat) / sizeof(mat[0]);
    findMaxAndMinOfDiagonals(mat, n);
}

出力

Smallest Element of Principal Diagonal : 2
Greatest Element of Principal Diagonal : 8
Smallest Element of Secondary Diagonal : 2
Greatest Element of Secondary Diagonal : 7

解法アプローチ②：単一ループに最適化する効率的な方法

より効率的な解法として、二重ループを単一ループに削減できます。これは、主対角線上の要素は行と列のインデックスが同じであるという性質を利用したものです。

主対角線の要素 = mat[i][i]
副対角線の要素 = mat[i][n - i - 1]

このインデックスの関係により、各行を一度だけ走査すれば両方の対角線の要素にアクセスできるため、計算量を O(n²) から O(n) に改善できます。

実装例

#include<iostream>
using namespace std;
void findMaxAndMinOfDiagonals(int mat[3][3], int n){
    if (n == 0)
        return;
    int pDiagMin = mat[0][0],
    pDiagMax = mat[0][0];
    int sDiagMin = mat[0][n - 1 ],
    sDiagMax = mat[0][n - 1];
    for (int i = 1; i < n; i++) {
        if (mat[i][i] < pDiagMin)
            pDiagMin = mat[i][i];
        if (mat[i][i] > pDiagMax)
            pDiagMax = mat[i][i];
        if (mat[i][n - 1 - i] < sDiagMin)
            sDiagMin = mat[i][n - 1 - i];
        if (mat[i][n - 1 - i] > sDiagMax)
            sDiagMax = mat[i][n - 1 - i];
    }
    cout<<("\nSmallest Element of Principal Diagonal : ")<<pDiagMin;
    cout<<("\nGreatest Element of Principal Diagonal : ")<<pDiagMax;
    cout<<("\nSmallest Element of Secondary Diagonal : ")<<sDiagMin;
    cout<<("\nGreatest Element of Secondary Diagonal : ")<<sDiagMax;
}
int main(){
    int mat[3][3] = {
        { 3, 4, 7 },
        { 0, 2, 1 },
        { 1, 7, 8 }
    };
    int n = sizeof(mat) / sizeof(mat[0]);
    findMaxAndMinOfDiagonals(mat, n);
}

出力

Smallest Element of Principal Diagonal : 2
Greatest Element of Principal Diagonal : 8
Smallest Element of Secondary Diagonal : 1
Greatest Element of Secondary Diagonal : 7

まとめ

正方行列の対角線上の最小値・最大値を求めるには、対角線上の要素のインデックス規則（主対角線は i == j、副対角線は i + j == n - 1）を活用します。二重ループでも解けますが、単一ループに最適化することで計算量を大幅に削減でき、より効率的なプログラムになります。