本サイトAIZU ONLINE JUDGE ITP1_10_D へはこちらから
問題：ミンコフスキー距離
２つのデータがどれだけ似ているかを、それらの距離で測る手法は、クラスタリングや分類など、様々なところで使われています。ここでは、２つの \(n\) 次元ベクトル \(x={x1,x2,…,xn}\) と \(y={y1,y2,…,yn}\) の距離を計算してみましょう。
このようなデータの距離を測る指標のひとつとして、次のミンコフスキー距離が知られています。
$$D_{xy} = (\sum_{i=1}^n |x_i – y_i|^p)^{\frac{1}{p}}$$
p=1 のとき
$$D_{xy} = |x_1 – y_1| + |x_2 – y_2| + … + |x_n – y_n|$$
となり、これはマンハッタン距離とよばれます。
p=2 のとき
$$D_{xy} = \sqrt{(|x_1 – y_1|)^{2} + (|x_2 – y_2|)^{2} + … + (|x_n – y_n|)^{2}}$$
となり、これは一般的に使われるユークリッド距離になります。
p=∞ のとき
$$D_{xy} = max_{i=1}^n (|x_i – y_i|)$$
となり、これはチェビシェフ距離と呼ばれます。
２つの n 次元ベクトルが与えられるので、p がそれぞれ 1、2、3、∞ のミンコフスキー距離を求めるプログラムを作成してください。
Input
１行目に整数 n が与えられます。２行目にベクトル x の要素 \( {x1,x2,…xn} \)、３行目にベクトル y の要素 \( {y1,y2,…yn} \) が空白区切りで与えられます。入力はすべて整数値です。
Output
p がそれぞれ 1、2、3、∞ の順番にそれぞれ１行に距離を出力してください。ただし、0.00001 以下の誤差があってもよいものとします。
Constraints
- 1≤n≤100
- 0≤xi,yi≤1000
Sample Input
3
1 2 3
2 0 4Sample Output
4.000000
2.449490
2.154435
2.000000解答例
n = int(input())
X = list(map(int, input().split()))
Y = list(map(int, input().split()))
# p=1,2,3
for p in range(1, 4):
print("{0:.6f}".format(sum([abs(a-b)**p for a, b in zip(X, Y)])**(1/p)))
# p=infinity
print("{0:.6f}".format(max([abs(a-b) for a, b in zip(X, Y)])))解説
以下のように解いていきます。
1つの整数の読み込み
キーボードから文字列を受け取る際に使用するinput関数をint関数で囲み、整数を受け取ります。
# input関数をint関数で囲み、整数値として変数に代入
n = int(input())※サイト内「AIZU ONLINE JUDGE ITP1_1_Bをpythonで解いてみた」の、input関数とはに使用方法が書かれておりますのでぜひご覧ください。
ベクトル X,ベクトル Yの読み込み
ここでは、map関数を使用します。第二引数のinput().split()で空白区切りの文字列を取得した値を、一つずつint関数に当てはめてint型に変換、さらにlist関数で囲み、リストとして変数Xに設定します。同じようにベクトルYも取得します。
# input().split()で空白区切りの文字列を取得 → intに変換 → list関数で囲み、リストとしてXに設定
X = list(map(int, input().split()))
# input().split()で空白区切りの文字列を取得 → intに変換 → list関数で囲み、リストとしてYに設定
Y = list(map(int, input().split()))※サイト内「AIZU ONLINE JUDGE ITP1_1_Cをpythonで解いてみた」の、map関数とはにも使用方法が書かれておりますのでよかったらご覧ください。
p=1,2,3のミンコフスキー距離の表示
ここで使用するabs関数、zip関数について説明します。
abs関数とは
abs関数は引数に数値を設定することで、その絶対値を取得する事ができる関数です。使い方は以下です。
x = abs(-10)
print(x)
# 出力
# 10
y = abs(10)
print(y)
# 出力
# 10zip関数とは
zip関数は複数のリストを同時に取得できる関数です。
zip(リスト1, リスト2, …)実際の使い方は以下のようになります。複数のリストから要素を同時に取り出しそれぞれの変数(name, age)に入れます。
names = ['taro', 'hanako', 'jiro']
ages = [25, 30, 27]
# 複数のリストから同時に要素を取り出し、変数に代入する
for name, age in zip(names, ages):
print(name, age)
# 出力
# taro 25
# hanako 30
# jiro 27今回は、\(D_{xy} = (\sum_{i=1}^n |x_i – y_i|^p)^{\frac{1}{p}}\)の公式に沿って記述します。
リストX、リストYから要素を一つずつ取り出し、絶対値をとってp乗します。リストの総数まで足し合わせたら、\(\frac{1}{p}\)乗します。これをp=1,2,3で行います。
# 1から3までのループ処理を行う
for p in range(1, 4):
# zip関数でX, Yから1要素ずつa, bに取り出す → abs関数で絶対値をとりp乗 → sum関数で総数を算出 → 1/p乗する
print("{0:.6f}".format(sum([abs(a-b)**p for a, b in zip(X, Y)])**(1/p)))p=infinityのミンコフスキー距離の表示
p=∞のミンコフスキー距離はチェビシェフ距離と呼ばれ、各座標の差(の絶対値)の最大値を2点間の距離とします。\(D_{xy} = max_{i=1}^n (|x_i – y_i|)\)の公式に沿って考えると、リストX、リストYから要素を一つずつ取り出し、絶対値の中で最大値がチェビシェフ距離です。
# zip関数でX, Yから1要素ずつa, bに取り出す → abs関数で絶対値をとる → max関数で最大値を求める
print("{0:.6f}".format(max([abs(a-b) for a, b in zip(X, Y)])))最後に、もう一度プログラムを確認してみましょう。
# input関数をint関数で囲み、整数値として変数に代入
n = int(input())
# input().split()で空白区切りの文字列を取得 → intに変換 → list関数で囲み、リストとしてXに設定
X = list(map(int, input().split()))
# input().split()で空白区切りの文字列を取得 → intに変換 → list関数で囲み、リストとしてYに設定
Y = list(map(int, input().split()))
# 1から3までのループ処理を行う
for p in range(1, 4):
# zip関数でX, Yから1要素ずつa, bに取り出す → abs関数で絶対値をとりp乗 → sum関数で総数を算出 → 1/p乗する
print("{0:.6f}".format(sum([abs(a-b)**p for a, b in zip(X, Y)])**(1/p)))
# zip関数でX, Yから1要素ずつa, bに取り出す → abs関数で絶対値をとる → max関数で最大値を求める
print("{0:.6f}".format(max([abs(a-b) for a, b in zip(X, Y)])))
コメント