アルゴリズム

ベルマン−フォード・アルゴリズム(Ruby)

ベルマン−フォード・アルゴリズムは、ダイクストラ法にさらに辺の重みが負の場合も含めて最短経路を求めることができます。入出力などはダイクストラ法の場合を参照して下さい。コーディングは Ruby で行いました。返り値は配列 [@shortest, @pred] で、@pre…

ダイクストラ法(Ruby)

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

閉路なし有向グラフ(DAG)の最短経路(Ruby)

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

トポロジカルソート(Ruby)

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

基数ソート(Ruby)

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

バケットソート(と計数ソート)(Ruby)

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

マージソートとクイックソートの比較(Ruby)

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

エイト・クイーン(8 queen)問題を Ruby で解いてみる

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

与えられた迷路の最短経路を求める(Ruby)

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

マージソート(Ruby)

アルゴリズムの基本作者: トーマス・H・コルメン,長尾高弘出版社/メーカー: 日経BP社発売日: 2016/03/11メディア: 単行本この商品を含むブログ (5件) を見るマージソートのアルゴリズムだけ勉強して、自力で Ruby で実装してみました。merge_sort.rb class A…

1Ωの抵抗10個で黄金比の値に近づける(Ruby)

問題: 1Ω の抵抗 10個を使い、合成抵抗が黄金比 1.6180339887..Ωにもっとも近づく場合の値を、少数第10位まで求めよ。 aΩ と bΩ の抵抗をつなげる場合、直列つなぎにすれば合成抵抗はたんに a + b Ω になりますが、並列つなぎの場合はそれらの逆数の和の逆…

ナップサック問題(Ruby)

次のような問題があるとします。 学校でクラブ活動をするのに、選んだクラブの人数の合計が 150人以下になるようにするとします。クラブの想定人数とそれが使う敷地面積は次のように与えられています。 クラブを幾つか適当に選ぶとき、必要な敷地面積の総和…

右折禁止(アルゴリズム・パズル)

アルゴリズム・パズルを Ruby で解いてみました。 class TurnLeft class Position def initialize(x, y) @x, @y = x, y end attr_accessor :x, :y def +(dir) Position.new(@x + dir[0], @y + dir[1]) end end class Field def initialize @yoko = Array.new…

いわゆる「スライドパズル(15パズル)」もどきを Ruby で解いてみる

スライドパズルっていうおもちゃがありますよね。4×4 のマス目に空白がひとつあって(残りはコマ)、コマは空白にスライドさせて動かすしかなく、それを特定のパターンに揃えるというものです。ここではルールを少し改変して、特定のマスを別の特定のマスに…

Rubyは末尾呼び出し最適化をサポートしている

Ruby でこれはスタックオーバーフローします。 def add(n, a = 0) return a if n.zero? add(n - 1, n + a) end puts add(10000) #=>a.rb:2:in `add': stack level too deep (SystemStackError) 例えばこう対策します。 obelisk.hatenablog.com 上のとおり以…

シンプソンの公式による数値積分(Ruby)

Rubyによる情報科学入門作者: 久野靖出版社/メーカー: 近代科学社発売日: 2008/12メディア: 単行本 クリック: 5回この商品を含むブログ (13件) を見る f(x) = x^2 を [1, 10] の区間で数値積分してみます。ここでは区間を100分割します。ちなみに、正しい答…

1変数方程式を数値計算で解く(Ruby)

Rubyによる情報科学入門作者: 久野靖出版社/メーカー: 近代科学社発売日: 2008/12メディア: 単行本 クリック: 5回この商品を含むブログ (13件) を見る方程式 f(x) = 0 を ある区間 [a, b] において、f(x) が単調増加、連続、f(a) 0 であるとして、数値計算で…

末尾再帰をスタックオーバーフローせずに実行する(Ruby)

あるプログラムを書いていて、再帰がいわゆる「スタックオーバーフロー」するのに悩まされました。結局そのプログラムはカスだったのですが、スタックオーバーフローをおもしろい方法で回避することを知ったので、メモしておきます。まず、1 から n までを単…

単純なソートのおさらい(Python)

以前に Ruby でバブルソート、選択ソート、挿入ソートを実装してみました(参照)が、Python でもやってみました。リストの(浅い)コピーってどうやるのかと思った。それから、Python は Ruby とちがって「モンキーパッチ」ができないのですね。あと、range…

Tree構造を利用して問題を解いてみる・その2(Ruby)

こことはちがう Tree 構造を使って、プロジェクト・オイラーの Problem 61をもう一度解いてみました(前回)。使った Tree 構造はこちらです。コードはそれほどちがいません。クラスを増やしただけ複雑になったとみるか、Node の重複を許すためメインループ…

Ruby で Tree構造(その3)

これまでとは別の実装をしてみました(前回)。前回はノードは何でもよかったのですが、今度は Node クラスを作っています。そして、Node インスタンスとその値(value)を別にしています。Tree クラスに Node インスタンスを登録していて、Node インスタン…

Tree 構造を利用したヒープ(Ruby)

ここで実装した Tree 構造を使いました。 require './tree' class Heap < Tree def self.build(ar) raise "Argument is not Array." if ar.class != Array ar1 = ar.dup q = [] t = Heap.new(a = ar1.shift) q << a t.build1(q, ar1) t end def build1(q, ar…

Tree 構造を利用した二分探索木(Ruby)

アルゴリズムを学ぼう作者: 川中真耶,杵渕朋彦,椎名俊輔出版社/メーカー: アスキー・メディアワークス発売日: 2012/05/30メディア: 大型本購入: 5人 クリック: 34回この商品を含むブログ (6件) を見る ここで実装した Tree 構造を使いました。 require './tr…

Tree構造を利用して問題を解いてみる(Ruby)

前回実装した Tree構造を使って、プロジェクト・オイラーの問61を解いてみました。問題はこれです。

Ruby で Tree構造(その2)

前に Ruby で Tree 構造を作る記事(参照)を書きましたが、もう少し汎用的に使えるものを作ってみました。

メモ付き探索(Ruby)

アルゴリズムを学ぼう作者: 川中真耶,杵渕朋彦,椎名俊輔出版社/メーカー: アスキー・メディアワークス発売日: 2012/05/30メディア: 大型本購入: 5人 クリック: 34回この商品を含むブログ (6件) を見る 次のような問題があります。 石の山があり、そこから二…

単純なソートのおさらい(Ruby)

アルゴリズムを学ぼう作者: 川中真耶,杵渕朋彦,椎名俊輔出版社/メーカー: アスキー・メディアワークス発売日: 2012/05/30メディア: 大型本購入: 5人 クリック: 34回この商品を含むブログ (6件) を見る 上から、バブルソート、選択ソート、挿入ソート。以前に…

グラフと探索(Ruby)

アルゴリズムを学ぼう作者: 川中真耶,杵渕朋彦,椎名俊輔出版社/メーカー: アスキー・メディアワークス発売日: 2012/05/30メディア: 大型本購入: 5人 クリック: 34回この商品を含むブログ (6件) を見るいま上の本を読んでいるのですが、コード例が Java なの…

ヒープソート

破壊的メソッドになります。 class Array #要素iから下へ、maxヒープ状態が満たされるようにselfを修復する def max_heapify(i) l = 2 * i + 1 r = l + 1 largest = (l <= @heap_size - 1 and self[l] > self[i]) ? l : i largest = r if r <= @heap_size - …

スタックとキュー(待ち行列)

キュー(待ち行列)の Ruby 実装例です。スタックは Array で実装されているので、キューだけ実装してみました。ただし既に Queue クラスが thread ライブラリに存在するので、クラス名は UserQueue にしました。以下は限られた長さの配列を無駄なく使うため…

最大部分配列

分割統治の例です。配列の中から、部分和が最大となる部分配列を探し出し、その最初と最後のインデックス、および最大の部分和を返します。 重要なのはメソッド fmcs(find-max-crossing-subarray)です。 class Array def fmcs(low, mid, high) left_sum = …

バブルソート

class Array def bubble_sort a = dup for i in 0..(a.size - 2) (a.size - 1).downto(i + 1) do |j| a[j], a[j - 1] = a[j - 1], a[j] if a[j] < a[j - 1] end end a end end p [6, 0, 5, 2, 3].bubble_sort #=>[0, 2, 3, 5, 6] アルゴリズムイントロダクシ…

2分探索(バイナリサーチ)

練習問題 2.3-5 数字の入った配列の中から、引数に一致する要素のインデックスを返します。そのような要素がなければ nil を返します。配列はソートされている必要があります。マージソートのように、配列を再帰的に半分づつにしていって探します。最悪実行…

マージソート

プログラムの性質上、破壊的なメソッドになります。merge_sort.rb class Array def merge(p, q ,r) left = self[p..q] + [Float::INFINITY] right = self[(q + 1)..r] + [Float::INFINITY] i = j = 0 for k in p..r if left[i] <= right[j] self[k] = left[i…

挿入ソート

insertion_sort.rb class Array def i_sort a = dup for j in 1...(a.size) key = a[j] i = j - 1 while i >= 0 and a[i] > key a[i + 1] = a[i] i -= 1 end a[i + 1] = key end a end end p [6, 0, 5, 2, 1].i_sort #=>[0, 1, 2, 5, 6] アルゴリズムイント…

Ruby で Tree 構造を作る

※注意 ここでさらに一般的な Tree の例を与えてあります。そちらをどうぞ。 Rubyクックブック ―エキスパートのための応用レシピ集作者: Lucas Carlson,Leonard Richardson,株式会社クイープ出版社/メーカー: オライリー・ジャパン発売日: 2007/04/27メディア…

クイックソート(Ruby)

いわゆる「K&R」本(『プログラミング言語C 第2版 ANSI規格準拠』p.106)に載っている配列のクイックソートを、Ruby に移植してみました。メソッド(C言語では関数)の再帰呼び出しの例として使われています。コードは殆ど本そのままですが、C言語よりは読み…