上の閉路なし有向グラフ（DAG）のように、辺に「重み」が付いている場合において、最短経路を求めてみます。手続きは 入力： G: n 個の頂点の集合 V と m 本の有向辺の集合 E を含む閉路なし有向グラフ。 s: V の始点。 出力： V に含まれる始点以外の頂点 v…

閉路なし有向グラフ（DAG: directed acyclic graph）のトポロジカルソートです。トポロジカルソートとは、上のようなグラフがあったとき、 入力：1〜n の頂点をもつ閉路なし有向グラフ。 出力：グラフ内の辺を (u, v) とするとき、u が v の前になるように並…

ここのところで結城先生の「既約分数クイズ」のことを知りました。結城先生らしい「お話」仕立てですので、是非参照して頂きたいですが、簡単にいうと 問題：正の整数Nが与えられているとき、 以下の条件を満たす既約分数p/qを「すべて」求めるアルゴリズム…

いわゆる「フォードの円」というものを描いてみました。これについてはここで知ったものです。ありがとうございます。Ruby で描きました。描画には自作の Gem 'oekaki' を使っています。 oekaki_sample10.rb require 'oekaki' Width, Height = 500, 500 Oeka…

基数ソートは固定長の文字列のソートなどに使うアルゴリズムで、下の位（文字列の右の方）から順にソートしていって、すべての位をソートし終えたとき、全体のソートが終っているという方法です。個々のソートには高速な「計数ソート」を使うとよい（「安定…

バケットソートはバケツソート、ビンソート、計数ソート（後記：計数ソートとバケットソートはちがう）などとも言います。非常に高速ですが、ソートされる対象は 0以上の整数値（またはそれに変換できるもの）であり、その最大値が大きくなるとメモリをバカ…

自分の実装で、マージソートとクイックソートのベンチマークをしてみました。 マージソートの実装はこれ、クイックソートのはこれ（いちばん下の実装）です。 マージソート。 クイックソート。 基本的にクイックソートの方が速いようである。 ベンチマーク。…

エイト・クイーン - Wikipedia チェスの盤上に、8個のクイーンを配置する。このとき、どの駒も他の駒に取られるような位置においてはいけない。 チェスの盤面は 8×8 であり、クイーンのコマは前後左右斜めにどれだけでも進むことができます。盤面上に 8つの…

人材獲得作戦・４ 試験問題ほか: 人生を書き換える者すらいた。 さて試験問題です。 内容は、壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ、というものです。 おもしろそうなので Ruby で解いてみまし…

後記。以下の実装のほとんどはふつういうマージソートの実装ではありません。何かしら別物です。追記された merge_sort2.rb のみがふつういうマージソートの実装なので注意してください。というか、参考にしないで下さい。 アルゴリズムの基本作者: トーマス…

Haskell が遅延評価で「たらいまわし関数」を高速に実行できるなら、Ruby でも Proc で遅延評価できるので、Ruby でも「たらいまわし関数」を高速化できるのではないかと思った。でぐぐってみたら、そのものズバリの記事を発見。 おお、きちんとまとまったわ…

まだ Haskell は全然わかりませんが、Haskell では「たらいまわし関数」がすごいということなのでやってみました。「たらいまわし関数」については、このブログにも簡単な記事があって、Ruby などでやってみております。簡単にいうと、これは関数呼び出しの…