2017-08-07から1日間の記事一覧

結城先生の薬品格納クイズ(Ruby)

「既約分数クイズ」に続いて、結城先生の「薬品格納クイズ」というというのをやってみます。 薬品格納クイズ 問題: 6×2=12個の区画に分かれている薬品箱があります。 ここにA, Bという二種類の薬品を格納します。 ところが、薬品Bは縦や横に隣り合った区画…

ダイクストラ法(Ruby)

前エントリでは閉路なし有向グラフ(DAG)の場合に最短経路を求めてみましたが、ダイクストラ法は閉路があり、かつ辺の重みが非負の場合に最短経路を求めることができます。入出力は、閉路があって辺の重みが非負である以外、DAG の場合と同じなので、そちら…