AIZU ONLINE JUDGE

AOJ ITP1 10_D(Distance II)を解く

AOJ_ITP1_10_D

Aizu Online Judge(AOJ)が提供している「プログラミング入門」(ITP1)の10_D問題をC++とPython で解いてみました。

ITP1 のトピック10では、数学関数について学びます。「基礎的な数学関数を学習します。」とあります。この学習コースを通じて、Python に慣れていきたいと考えています。

問題(10_D: Distance II)

問題はリンク先をご覧ください。

AOJ ITP1 10_D問題:Distance II

データの距離を求める問題です。

解答案

C++ プログラム例(ITP1 10_D)

数式で定義されている距離の定義に従い、距離を求めていきます。数式を読み解ければ、プログラムは、それほど難しくないと考えています。

C++ のプログラムは、以下となります。

#include <iostream>
#include <ios>      // fixed
#include <iomanip>  // setprecision
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	cin >> n;

	vector<double> x(n);
	for (int i = 0; i < n; ++i) {
		cin >> x[i];
	}
	vector<double> y(n);
	for (int i = 0; i < n; ++i) {
		cin >> y[i];
	}

	double d1 = 0.0;
	double d2 = 0.0;
	double d3 = 0.0;
	double di = 0.0;

	for (int i = 0; i < n; ++i) {
		double d = fabs(x[i] -y[i]);
		d1 += d;
		d2 += d * d;
		d3 += d * d * d;
		di = max(di, d);
	}
	d2 = sqrt(d2);
	d3 = pow(d3, 1.0/3.0);

	cout << fixed << setprecision(5);
	cout << d1 << endl;
	cout << d2 << endl;
	cout << d3 << endl;
	cout << di << endl;

	return 0;
}

Python プログラム例(ITP1 10_D)

Python では、それぞれの距離を求めるために、内包表記でリストを作成しました。そのリストに対して sum を適用して合計を求めて、** 演算子で $n$ 乗根を求めました。

チェビシェフ距離は、リスト要素の最大値を求めています。

n = int(input())
x = list(map(float, input().split()))
y = list(map(float, input().split()))

d1 = sum([abs(xt - yt) for xt, yt in zip(x, y)])
d2 = sum([abs(xt - yt) ** 2 for xt, yt in zip(x, y)]) ** (1.0 / 2.0)
d3 = sum([abs(xt - yt) ** 3 for xt, yt in zip(x, y)]) ** (1.0 / 3.0)
di = max([abs(xt - yt) for xt, yt in zip(x, y)])

print(f"{d1:.5f}", f"{d2:.5f}", f"{d3:.5f}", f"{di:.5f}", sep="\n")

上記プログラムは、すべて AOJ で「AC(Accepted=正解)」と判定されます。

最後に

トピック10は、数学関数について学びました。C++ も Python もライブラリ(モジュール)で、数学的な機能をサポートしていました。

10_B10_C では、高校で履修した数学の内容をプログラムに落とし込みました。基本的な数学的な素養もプログラムを書くためには、必要だと考えています。

引き続き、ITP1 の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA