【C++入門】行列が上三角行列かどうかを判定するプログラムの書き方

正方行列 M[r][c](r は行数、c は列数、r = c)が与えられたとき、この行列 M が上三角行列であるかどうかを判定するプログラムを C++ で作成します。

上三角行列とは?

上三角行列とは、主対角線(対角成分)およびその上側の要素は非ゼロであり、主対角線より下側の要素がすべてゼロであるような行列のことです。

下図の例を見てみましょう。

この図では、赤く強調された要素が主対角線より下側の要素にあたり、これらがすべてゼロになっています。それ以外の要素(主対角線上およびその上側)は非ゼロです。このような行列が上三角行列と呼ばれます。

入力例と出力例

入力: m[3][3] = { {1, 2, 3},
   {0, 5, 6},
   {0, 0, 9}}
出力: yes

入力: m[3][3] = { {3, 0, 1},
   {6, 2, 0},
   {7, 5, 3} }
出力: no

1つ目の例では、主対角線より下側の要素がすべて 0 であるため「yes」となります。一方、2つ目の例では下側に非ゼロの要素(6 や 7 など)が存在するため「no」と判定されます。

アルゴリズム

判定の手順は以下の通りです。

開始
ステップ1 → マクロを定義する:#define size 4
ステップ2 → 行列が上三角行列かどうかをチェックする関数を宣言する
   bool check(int arr[size][size])
      ループ:int i = 1 から i < size まで i++ ずつ繰り返す
         ループ:int j = 0 から j < i まで j++ ずつ繰り返す
            もし (arr[i][j] != 0) ならば
               false を返す
            終了
      終了
   終了
   true を返す
ステップ3 → main() 関数内で
   int arr[size][size] を宣言し、値で初期化する
   もし (check(arr)) ならば
      「上三角行列です」と出力する
   そうでなければ
      「上三角行列ではありません」と出力する
   終了
終了

ポイントは、行番号 i が列番号 j より大きい位置(つまり主対角線より下側)の要素だけを走査することです。そこにひとつでも非ゼロの要素があれば、その行列は上三角行列ではないと即座に判断できます。

C++ サンプルコード

#include <bits/stdc++.h>
#define size 4
using namespace std;
// 行列が上三角行列かどうかをチェックする関数
bool check(int arr[size][size]){
   for (int i = 1; i < size; i++)
      for (int j = 0; j < i; j++)
         if (arr[i][j] != 0)
            return false;
   return true;
}
int main(){
   int arr[size][size] = { { 1, 1, 3, 2 },
      { 0, 3, 3, 2 },
      { 0, 0, 2, 1 },
      { 0, 0, 0, 1 } };
   if (check(arr))
      cout << "これは上三角行列です";
   else
      cout << "これは上三角行列ではありません";
   return 0;
}

実行結果

これは上三角行列です

計算量について

このアルゴリズムは、行列の下半分の要素を一度ずつ調べるため、時間計算量は O(n²)(n は行列のサイズ)となります。また、追加のメモリを使用しないため、空間計算量は O(1) です。行列のサイズが大きくなっても効率的に動作します。