Aizu Online Judge（AOJ）が提供している「プログラミング入門」（ITP1）の6_D問題をC++とPython で解いてみました。
ITP1 のトピック6では、配列について学びます。「データの列を１つの変数として管理する配列を習得します。」とあります。Python では、リストに該当します。この学習コースを通じて、Python に慣れていきたいと考えています。
問題（6_D: Matrix Vector Multiplication）
問題はリンク先をご覧ください。
AOJ ITP1 6_D問題:Matrix Vector Multiplication
2次元配列を使って、行列とベクトルの積を求めます。
解答案
n行m列の行列と、m次元のベクトルの積は、n次元のベクトルとなります。これは、一次変換と呼ばれる操作です。積を数式で書くと以下となります。
$$\left( \begin{array}{c} c_1 \\ c_2 \\ \vdots \\ c_n \end{array} \right) = \begin{pmatrix} a_{11} & \ldots & a_{1m} \\ a_{21} & \ldots & a_{2m} \\ \vdots & \cdots & \vdots \\ a_{n1} & \ldots & a_{nm} \end{pmatrix} \left( \begin{array}{c} b_1 \\ b_2 \\ \vdots \\ b_m \end{array} \right)$$
n次元ベクトルの要素 $c_i$ は、以下の数式で求めることができます。
$$ c_i = \sum^m_{j = 1} a_{ij} b_j = a_{i1} b_1 + a_{i2} b_2 + \ldots a_{im} b_m $$
C++ プログラム例（ITP1 6_D）
2次元配列で行列を表現して、1次元の配列でベクトルを表現します。行列とベクトルの積の定義に従って、計算するだけです。
問題文および上の解説では、添え字を1から記しましたが、以下のプログラムは、無駄な配列が出ないように添え字を0から使っています。
#include <iostream>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
int a[n][m];
int v[m];
int c[n] = {0};
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++) {
cin >> v[j];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
c[i] += a[i][j] * v[j];
}
}
for (int i = 0; i < n; i++) {
cout << c[i] << endl;
}
return 0;
}Python プログラム例（ITP1 6_D）
Python では、リストを使います。行列の演算については、NumPy という拡張モジュールを使うこともできますが、素の Python の範囲で実装しました。
n, m = map(int, input().split())
a = [[0 for i in range(m)] for j in range(n)]
v = [0 for i in range(m)]
c = [0 for i in range(n)]
for i in range(n):
a[i] = list(map(int, input().split()))
for i in range(m):
v[i] = int(input())
for i in range(n):
for j in range(m):
c[i] += a[i][j] * v[j]
print(*c, sep="\n")上記プログラムは、すべて AOJ で「AC（Accepted＝正解）」と判定されます。
最後に
配列の応用として、行列とベクトルの積を計算しました。行列の演算は、昔は高校数学として履修していましたが、現行課程では外れています。今は大学で線形代数という科目で学ぶ方が多いと思われます。
配列を学ぶことでプログラムできる範囲が広がりました。
引き続き、ITP1 の問題を紹介していきます。
