Coding_Gamesメモ_The_Travelling_Salesman_Problem

Coding_Games

Coding_Gamesメモ_The_Travelling_Salesman_Problem

javaの学習にCoding_Games を知り、学習の記録としてメモ。
To debug:

System.err.println( );

を使うとデバックしやすくなる。（エラー出力は評価に影響しない）

内容

指定された道順で移動する距離を求める

ルール

指定された方法で各地点を1度だけ訪れ、もとの地点に戻る移動距離を出力

移動ルートのルール

  • 現在の地点から一番近い地点を次の目的地にする
  • 距離が同じ地点があればリストの順番が低い方を優先する
  • 通過していない地点が無ければ次の目的地は最初の地点になる

移動距離のルール

ユークリッド距離を使用
sqrt(deltaX2 + deltaY2)

インプット

1行目 地点の数 (N)
2行目以降 地点ごとのXとYの座標

アウトプット

指定された方法を使用して計算された合計を小数点以下、四捨五入した整数

使用したクラス

Math

(double) = Math.pow((double) a , (double) b)
ab a のb 乗

(long) = Math.round( (double) x )
xの四捨五入を行う
引数が(float) だと戻値が(int) になる

(double) = Math.sqrt( (double) x )
xの平方根を出力する

考え方

最初の地点から直線距離で一番近い場所を探ていき距離を足していく、最後に最初の地点までの距離を足す
小数点以下も足さないと計算が合わなくなる

Coding_Games:https://www.codingame.com/
Math (Java Platform SE 8) - Oracle Cloud:http://docs.oracle.com/javase/jp/8/docs/api/java/lang/Math.html