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

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

Rubyによる情報科学入門作者:久野 靖近代科学社Amazon方程式 f(x) = 0 を ある区間 [a, b] において、f(x) が単調増加、連続、f(a) 0 であるとして、数値計算で解いてみます。具体的には n の平方根を求めてみます。 区間2分法 区間の中点をとってその点での…

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

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

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

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

ここで実装した 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…

（※注記）以下のコードは未熟なので、二分探索木については（よろしければ）こちらをどうぞ。（2019/1/18） アルゴリズムを学ぼう作者: 川中真耶,杵渕朋彦,椎名俊輔出版社/メーカー: アスキー・メディアワークス発売日: 2012/05/30メディア: 大型本購入: 5人…

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

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

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

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

アルゴリズムを学ぼう作者: 川中真耶,杵渕朋彦,椎名俊輔出版社/メーカー: アスキー・メディアワークス発売日: 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.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] アルゴリズムイント…

これは非常に未熟な記事です。特に初心者の方はあまりこの記事を真に受けないで下さい。（2019/5/22）※注意 ここでさらに一般的な Tree の例を与えてあります。そちらをどうぞ。 Rubyクックブック ―エキスパートのための応用レシピ集作者: Lucas Carlson,Leo…

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