AOJ PG入門 #10

問1. ２点 P1(x1, y1), P2(x2, y2) の距離を求めるプログラムを作成せよ。

• input
  x1, y1, x2, y2 （実数）が空白区切りで与えられます。
• output
  P1とP2の距離を実数で１行に出力して下さい。0.0001以下の誤差があってもよいものとします。

PHP

AOJ.php

<?php
$arr = explode(" ",trim(fgets(STDIN)));
$a = ($arr[2]-$arr[0])*($arr[2]-$arr[0]);
$b = ($arr[3]-$arr[1])*($arr[3]-$arr[1]);
$ans = sqrt(($a+$b));
echo $ans."\n";
//2次元平面において、2点の距離は√(x2-x1)^2+(y2-y1)^2で求めることができる
//一行を読み取り、空白を区切りとして配列arrにまとめる
//ans = sqrt((a+b))
?>

• sqrt() 関数は、数値の平方根を返す

別解

other.php

<?php
list($x1,$y1,$x2,$y2)=explode(' ',trim(fgets(STDIN)));
echo sqrt(pow($x1-$x2,2)+pow($y1-$y2,2));

• pow関数は数値のべき乗を計算。第一引数に基数、第二引数に指数
• 例：pow(2, 3)→返り値は8(2の3乗)

Java

AOJ.java

import java.util.Scanner;
public class Main{
    public static void main(String[]args){
        double [] arr = new double [4];
        Scanner sc = new Scanner(System.in);
        for(int i =0;i<4;i++){
        arr[i] = sc.nextDouble();
        }
        double ans = Math.sqrt(Math.pow((arr[2]-arr[0]), 2) + Math.pow((arr[3] - arr[1]), 2));
        System.out.println(ans);
        sc.close();
    }
}

• 入力値が実数（浮動小数点数）なのでdouble型→それを格納する配列の型もdouble型にすることに注意

問2三角形の２辺 a, b とその間の角 C から、その三角形の面積 S、周の長さ L, a を底辺としたときの高さ h を求めるプログラムを作成して下さい。

• input
  a の長さ, b の長さ, Cの大きさ（度）（整数）が空白区切りで与えられます。
• output
  S, L, h をそれぞれ1行に出力して下さい。0.0001以下の誤差があってもよいものとします。

PHP

AOJ.php

<?php
list($a, $b, $C) = explode(" ", trim(fgets(STDIN)));

// 面積の計算
$s = 0.5 * $a * $b * sin(deg2rad($C));　//deg2rad($c) で角度をラジアンに変換

// 余弦定理で3辺目cを求める
$c = sqrt(pow($a, 2) + pow($b, 2) - 2 * $a * $b * cos(deg2rad($C)));

// 周の長さの計算
$l = $a + $b + $c;

// 高さの計算
$h = $b * sin(deg2rad($C));

// 結果を小数点8桁で表示
printf("%.8f\n", $s);
printf("%.8f\n", $l);
printf("%.8f\n", $h);
?>

• S = 1/2ab*sinC
• もう一辺　= √a^2+b^2-2abcosC
• a を底辺にして高さを求めるならhはbsinC

Java

AOJ.java

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        // 入力を受け取るためのScanner
        Scanner sc = new Scanner(System.in);

        // a, b, Cを入力（a, b は int型、C は int型）
        int a = sc.nextInt();
        int b = sc.nextInt();
        int C = sc.nextInt();

        // a, b を double に変換して計算を行う
        double aDouble = (double) a;
        double bDouble = (double) b;

        // C（角度）をラジアンに変換
        double radian = Math.toRadians(C);

        // 面積 S = 1/2 * a * b * sin(C)
        double S = 0.5 * aDouble * bDouble * Math.sin(radian);

        // 余弦定理で c を求める
        double c = Math.sqrt(aDouble * aDouble + bDouble * bDouble - 2 * aDouble * bDouble * Math.cos(radian));

        // 周の長さ L = a + b + c
        double L = aDouble + bDouble + c;

        // 高さ h = (2 * S) / a
        double h = (2 * S) / aDouble;

        // 結果を出力（小数点以下8桁）
        System.out.printf("%.8f\n", S);
        System.out.printf("%.8f\n", L);
        System.out.printf("%.8f\n", h);

        // Scannerを閉じる
        sc.close();
    }
}

• 最初からdouble型でa,b,cをうけとってもOK

別解

other.java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt(), b = sc.nextInt(), angleC = sc.nextInt();
        double angleC_rad = Math.toRadians(angleC);
        double sinC = Math.sin(angleC_rad), cosC = Math.cos(angleC_rad);
        double S=0.5*a*b*sinC;
        double c=Math.sqrt(a * a + b * b - 2 * a * b * cosC);
        double L=a+b+c;
        double h=b*sinC;
        System.out.printf("%.8f\n%.8f\n%.8f\n",S,L,h);
    }
}

• こちらでは最初はint型で数値を受け取っている

問3. n 人の学生を含むクラスでプログラミングの試験を行った。それぞれの得点をs1, s2 ... snとしたときの、標準偏差を求めるプログラムを作成せよ。

• input
  複数のデータセットが入力として与えられる。各データセットは以下の形式で与えられる：
  学生の数 n
  s1 s2 ... sn
  n が 0 のとき入力の終わりとする。
• output
  各データセットに対して、標準偏差を１行に出力せよ。ただし、0.0001以下の誤差があってもよい。

PHP

AOJ.php

<?php
while(true){
$n = trim(fgets(STDIN));
if($n == 0)break;
    $datas= explode(" ",trim(fgets(STDIN)));

$ave = array_sum($datas)/$n;
$variance_sum = 0;
foreach($datas as $data){
    $variance_sum += pow(($data-$ave),2);
}
$variance = $variance_sum/$n;
$std_dev = sqrt($variance);
printf("%.8f\n",$std_dev);

}
//データ数nを入力から受け取る.n が 0 のとき入力の終わりとする。
//平均値$aveをもとめる
//各値、$aveを引いた数を求めて二乗＆2乗した値をすべて足す
//足した数をデータ数で割る
?>

Java

AOJ.java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        while (true) {
            int n = sc.nextInt();
            if (n == 0) break;
            
            int[] datas = new int[n];
            for (int i = 0; i < n; i++) {
                datas[i] = sc.nextInt();
            }
            
            // 合計値をdoubleで保持
            double sum = 0;
            for (int data : datas) {
                sum += data;
            }
            
            // 平均値
            double ave = sum / n;
            
            // 分散の合計をdoubleで保持
            double vari_sum = 0;
            for (int vari_data : datas) {
                vari_sum += Math.pow(vari_data - ave, 2);
            }
            
            // 分散と標準偏差をdouble型で計算
            double variance = vari_sum / n;
            double std_dev = Math.sqrt(variance);
            
            // 標準偏差を小数点以下8桁まで表示
            System.out.printf("%.8f\n", std_dev);
        }
        
        sc.close();
    }
}

問4.２つのn次元ベクトルが与えられるので、pがそれぞれ 1、2、3、∞のミンコフスキー距離を求めるプログラムを作成してください。

「距離」や「類似度」を測るための数学的な指標の一つ。多次元空間における点間の距離を計算するためにこれらの指標が使われる。問題文の前にそのいくつかを紹介する。

マンハッタン距離

• 定義: 2点P(x1,y1)とQ(x2,y2) の間のマンハッタン距離は、各軸の差の絶対値を足し合わせたもの。直感的には、格子状の街（マンハッタン）のような道を歩いて移動する距離を表す
• 式:|x1-x2|+|y1-y2|
• さらに高次元の場合は以下のように拡張できる
  nΣi=1|Xi-Yi| ※xiと𝑦𝑖yiは各次元での座標
• マンハッタン距離は、直線的に道を歩くような場合に使う。たとえば、都市の格子状の道路で車が移動する場合に近い
• 「道を曲がりながら進む」感じだから、対角線方向に進むことはできない

ユークリッド距離

• 定義: 2点間のユークリッド距離は、直線距離（最短距離）を意味する。日常生活で言う「2点間の直線的な距離」。2次元平面上では、ピタゴラスの定理を使って計算される
• 式：√(x1-x2)^2+(y1-y2)^2
• さらに高次元の場合は以下のように拡張できる
  √nΣi=1(Xi-Yi)^2 ※xiと𝑦𝑖yiは各次元での座標
• ユークリッド距離は「最短経路」を測定する。たとえば、2地点間を真っ直ぐ進むときの距離
  「最短距離」という直感的な意味を持つため、通常は多くの距離計算で使われる

チェビシェフ距離

• 定義: 2点間のチェビシェフ距離は、各軸での差の絶対値の最大値。直感的には、チェビシェフ距離は、棋盤の上で「最短のキングの移動」をしたときの距離に似ている（キングは縦、横、斜めすべての方向に移動できるが、最短の移動は各軸の差が最大の方向を選ぶこと）
• 式：max(|x1-x2|,|y1-y2|)
• 高次元の場合は、次のように拡張できる
  1≤i≤n
  max∣xi−yi∣
• チェビシェフ距離は、どの軸での差が最大かを見て、その最大値を距離として採用する

ミンコフスキー距離

• ミンコフスキー距離は、一般的な距離の計算式で、マンハッタン距離やユークリッド距離、チェビシェフ距離を包含するような形式。パラメータpを変えることで、さまざまな距離を得ることができる
• 式：(nΣi=1∣xi−yi∣^p)^1/p
• pは距離のパラメータ
• P＝１のとき、マンハッタン距離に相当
• P=２のとき、ユークリッド距離に相当
• P→∞のとき、チェビシェフ距離に相当

問題文

• input
  １行目に整数nが与えられます。２行目にベクトルxの要素{x1,x2,...xn}、３行目にベクトルyの要素{y1,y2,...yn}が空白区切りで与えられます。入力はすべて整数値です。
• output
  pがそれぞれ 1、2、3、∞の順番にそれぞれ１行に距離を出力してください。ただし、0.00001 以下の誤差があってもよいものとします。

PHP

AOJ.php

<?php
$n = trim(fgets(STDIN));
$x = explode(" ",trim(fgets(STDIN)));
$y = explode(" ",trim(fgets(STDIN)));
$manhattan_sum = 0;
for($i=0;$i<$n;$i++){
    $manhattan_sum += abs($x[$i]-$y[$i]);
}
$euqlid_sum = 0;
for($i=0;$i<$n;$i++){
    $euqlid_sum += pow(($x[$i]-$y[$i]),2);
}
$euqlid = sqrt($euqlid_sum);
$mincof_sum = 0;
for($i=0;$i<$n;$i++){
    $mincof_sum +=pow(abs($x[$i]-$y[$i]),3);
}
$mincof = pow($mincof_sum,1/3);
$cheb_arr = [];
for($i=0;$i<$n;$i++){
    $cheb_arr[]= abs($x[$i]-$y[$i]);
}
$cheb = max($cheb_arr);
printf("%.8f\n",$manhattan_sum);
printf("%.8f\n",$euqlid);
printf("%.8f\n",$mincof);
printf("%.8f\n",$cheb);
//nをうけとる
//ベクトルxの要素を受け取り配列にまとめる
//ベクトルyの要素を受け取り配列にまとめる
//マンハッタン距離を計算する→$sumを用意しn回ループで$sum+=abs(x[i]-y[i])
//ユークリッド距離を計算する→$sumを用意しn回ループで$sum+=pow(($x[i]-$y[i]),2)→sqrt($sum)
//ミンコフスキー距離を計算する→$sumを用意しn回ループで$sum+=pow(abs(x[i]-y[i]),3)→pow($sum,1/3)
//チェビシェフ距離を計算する→$arrを用意し、n回ループでmax($x[i]-$y[i])を格納→max($arr)

?>

別解

other.php

<?php
  $n = trim(fgets(STDIN));
  $x = explode(" ", trim(fgets(STDIN)));
  $y = explode(" ", trim(fgets(STDIN)));
  $p1 = 0;
  $p2 = 0;
  $p3 = 0;
  $max = array();
  for($i=0; $i < $n; $i++) {
    $q = $x[$i] - $y[$i];　　
    if ($q < 0) { $q = $q * -1; }　// 差の絶対値を取る
    array_push($max, $q);
    $p1 += $q;　//マンハッタン距離：絶対値の和を計算
    $p2 += pow($q, 2);　// ユークリッド距離：差の2乗を加算
    $p3 += pow($q, 3); //ミンコフスキー距離：差の3乗を加算
  }
  print($p1 . "\n" . sqrt($p2) . "\n" . pow($p3, (1 / 3)) . "\n" . max($max));
?>

Java

AOJ.java

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
public class Main{
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int [] x = new int [n];
        int [] y = new int [n];
        for(int i = 0;i<n;i++){
            x[i] = sc.nextInt();
        }
        for(int i = 0;i<n;i++){
            y[i] = sc.nextInt();
        }
        double manhattan = 0;
        double euqlid_sum = 0;
        double mincof_sum = 0;
        ArrayList<Double> cheb_arr = new ArrayList<Double>();
        for(int i =0;i<n;i++){
            int q = Math.abs(x[i]-y[i]);
            manhattan += q;
            euqlid_sum += Math.pow(q,2);
            mincof_sum += Math.pow(q,3);
            cheb_arr.add((double)q);
        }
        double mincof = Math.pow(mincof_sum,1.0/3);
        double euqlid = Math.sqrt(euqlid_sum);
        double cheb = Collections.max(cheb_arr);
        System.out.printf("%.6f\n%.6f\n%.6f\n%.6f\n", manhattan, euqlid, mincof, cheb);
        sc.close();
    }
}

• リストのようなコレクション全体を一度に処理することなく、単一の値を処理する設計のメソッド（Math.maxなど）は引数にリストはとれない
  →Collectionsクラスのメソッドで対応
• オートボクシング（Autoboxing）: プリミティブ型から対応するラッパークラスへの変換。たとえば、int から Integer への変換
• アンボクシング（Unboxing）: ラッパークラスから対応するプリミティブ型への変換。たとえば、Integer から int への変換
• ArrayListはDoubleオブジェクトを格納するためのものだが、qはint型のプリミティブ値
  →Javaでは、オートボクシングは通常行われるが、それは同じ型間の変換に限られる。つまり、int → Integer や double → Double のように、プリミティブ型からラッパークラスへの変換は可能だが、int → Double のように、異なるプリミティブ型同士ではオートボクシングは行われない
  →int 型の値であるqを Double 型に変換するには、明示的なdouble型へのキャストが必要
• printf で出力フォーマットを指定する場合、フォーマット文字列は1つの文字列である必要がある