Aizu Online Judge（AOJ）が提供している「プログラミング入門」（ITP1）の7_D問題をC++とPython で解いてみました。
ITP1 のトピック7では、再び構造化プログラムについて学びます。「繰り返し処理や配列を組み合わせることで、構造化プログラミングの理解を深めます。」とあります。この学習コースを通じて、Python に慣れていきたいと考えています。
問題（7_D: Matrix Multiplication）
問題はリンク先をご覧ください。
AOJ ITP1 7_D問題:Matrix Multiplication
行列の積を計算します。
解答案
ITP1 の問題6_D で行列とベクトルの積を求めました。今回は、行列と行列の積を求めます。$n \times m$ の行列 $A$ と $m \times l $ の行列 $B$ の積である、$n \times l$ の行列 $C$ について、数式で書くと以下となります。
$$\begin{pmatrix} c_{11} & \ldots & c_{1l} \\ c_{21} & \ldots & c_{2l} \\ \vdots & \cdots & \vdots \\ c_{n1} & \ldots & c_{nl} \end{pmatrix} = \begin{pmatrix} a_{11} & \ldots & a_{1m} \\ a_{21} & \ldots & a_{2m} \\ \vdots & \cdots & \vdots \\ a_{n1} & \ldots & a_{nm} \end{pmatrix} \begin{pmatrix} b_{11} & \ldots & b_{1l} \\ b_{21} & \ldots & b_{2m} \\ \vdots & \cdots & \vdots \\ b_{m1} & \ldots & b_{ml} \end{pmatrix}$$
行列 $C$ の各要素 $c_{ij}$ は次の式で得られます。
$$c_{ij} = \sum^m_{k = 1} a_{jk}b_{kj}$$
初めて見る方は、複雑な式だと感じるかもしれません。
C++ プログラム例（ITP1 7_D）
2次元配列で行列を表現して、前述の行列の積の定義に従って、計算するだけです。
問題文および上の解説では、添え字を1から記しましたが、以下のプログラムは、無駄な配列が出ないように添え字を0から使っています。これは、問題6_Dの場合と同じです。
$a_{jk}$、$b_{kj}$ は、それぞれ最大1万、積の最大は1億になります。それを最大100回加えるため、合計の最大値は100億になります。32ビット整数は、約20億までの数字しか格納できないため、行列積の要素は、long long int 型の整数 answer に格納します（25 行目）。（この記述は、2023年2月19日に追記しました。）
#include <iostream>
using namespace std;
int main()
{
int n, m, l;
cin >> n >> m >> l;
int a[n][m], b[m][l];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
}
}
for (int j = 0; j < m; ++j) {
for (int k = 0; k < l; ++k) {
cin >> b[j][k];
}
}
for (int i = 0; i < n; ++i) {
for (int k = 0; k < l; ++k) {
long long int answer = 0;
for (int j = 0; j < m; ++j) {
answer += a[i][j] * b[j][k];
}
cout << answer << " \n"[k == l - 1];
}
}
return 0;
}Python プログラム例（ITP1 7_D）
Python では、リストを使います。行列の演算については、NumPy という拡張モジュールを使うこともできますが、素の Python の範囲で実装しました。
変数 $l$ を使うとコーディングチェックツール pylint が警告を出力しました。1と見間違いやすいからだと思われます。このプログラムは、ループ変数を3個必要とするため、適当な変数名がなく、変数名 $l$ を許容することにしました。
n, m, l = map(int, input().split())
a = [[0 for i in range(m)] for j in range(n)]
b = [[0 for i in range(l)] for j in range(m)]
c = [[0 for i in range(l)] for j in range(n)]
for i in range(n):
a[i] = list(map(int, input().split()))
for i in range(m):
b[i] = list(map(int, input().split()))
for i in range(n):
for j in range(l):
for k in range(m):
c[i][j] += a[i][k] * b[k][j]
for i in range(n):
print(*c[i])上記プログラムは、すべて AOJ で「AC（Accepted＝正解）」と判定されます。
最後に
構造化プログラムの応用として、行列の積を計算しました。行列の演算は、昔は高校数学として履修していました。今は大学で線形代数という科目で学ぶ方が多いと思われます。
トピック7まで進み、プログラムできる範囲が広がりました。
引き続き、ITP1 の問題を紹介していきます。
