C++で指定された要素数から作成できる（異なる次数の）行列の数を求める方法

問題概要

本記事では、要素の総数が与えられたときに、そのデータから形成できる異なる次数（サイズ）の行列の総数を求める方法を解説します。行列の次数は m×n という形式で表され、m は行数、n は列数を表します。

例 1

入力： int numbers = 6

出力： 与えられた要素数から形成できる異なる次数の行列の数: 4

解説： 行列に含められる要素の総数として 6 が与えられています。6 個の要素から作成できる行列の次数は (1, 6)、(2, 3)、(3, 2)、(6, 1) の 4 通りです。

例 2

入力： int numbers = 40

出力： 与えられた要素数から形成できる異なる次数の行列の数: 8

解説： 要素の総数として 40 が与えられています。40 個の要素から作成できる行列の次数は (1, 40)、(2, 20)、(4, 10)、(5, 8)、(8, 5)、(10, 4)、(20, 2)、(40, 1) の 8 通りです。

アルゴリズムの考え方

• 異なる次数の行列を作成するために使用できる要素の総数を入力します。
• 計算処理を行うため、その値を関数に渡します。
• 異なる次数の行列の個数を保持する一時変数 count を用意します。
• i を 1 から number まで順に処理する FOR ループを開始します。
• ループ内で number % i == 0 が成立する場合（i が number の約数である場合）、count を 1 増やします。
• count を返します。
• 結果を出力します。

この問題は、実質的に「与えられた数の約数の個数を求める」問題と同じです。行数 m を決めれば列数 n は「要素数 ÷ m」として自動的に決まるため、要素数の約数がいくつあるかを数えれば、それがそのまま答えになります。

サンプルコード

#include <iostream>
using namespace std;

// 指定された要素数を持つ（異なる次数の）行列の数を数える関数
int total_matrices(int number){
    int count = 0;
    for (int i = 1; i <= number; i++){
        if (number % i == 0){
            count++;
        }
    }
    return count;
}

int main(){
    int number = 6;
    cout<<"与えられた要素数から形成できる異なる次数の行列の数: "<<total_matrices(number);
    return 0;
}

出力

上記のコードを実行すると、次のような出力が得られます。

与えられた要素数から形成できる異なる次数の行列の数: 4

計算量について

このアルゴリズムの時間計算量は O(N)、空間計算量は O(1) です。N が大きい場合は、1 から √N までだけを調べることで、時間計算量を O(√N) まで改善することも可能です。