プログラミング [ruby] Priority Queueの実装 RubyにPriority Queueがないので、皆さん自作の実装を持っていると思う。 もちろん私も私のPriority Queueがあるので公開しますね。 Priority Queue??? そもそも、Priority Queueとは... 2020.03.26 プログラミング
プログラミング rubyではbit全探索よりcombination全列挙のほうが早かった バージョン情報 Ruby 2.3.3 本題 過去にbit全探索の記事を書いていたことを思い出した。 ここにあるRubyの例で、全組み合わせの列挙をcombinationを使う方法を書いているんだけど、この記事によれば遅いって書いて... 2020.01.27 プログラミング
プログラミング RubyでLCSを求める 去年LCS長を求めるプログラムをRubyで書いた。 今回は、LCSそのものを求めるプログラムを書いた。 class String def lcs(target) lcs_len = Array.new(size + 1) ... 2015.05.19 プログラミング
プログラミング 【動的計画法】ロッド切り出し問題 12月、1月はCODEVS4に集中してたり、2月はうわおえを更新してたりで、アルゴリズムイントロダクションを勧められていなかったが再開! 動的計画法を解説している書籍やサイトでは、ナップザック問題を取り上げている場合が多い気がする。 でも... 2015.03.03 プログラミング
プログラミング rubyの2分探索木実装 理屈は知っていても、なかなか自分で実装することはないであろう2分探索木を実装する。 class BinaryTree attr_accessor :root def initialize self.root = nil... 2014.12.12 プログラミング
プログラミング 「ラングトンのアリ」のシミュレータ作った ラングトンの蟻とも言う。 タイトルの通りで、JavaScriptを使ってラングトンのアリシミュレータを作った。 ラングトンのアリの説明はwikipediaに任せる。 これはwikipediaにある拡張ラングトンのアリに対応しており、フ... 2014.11.25 プログラミング
プログラミング バケツソートをRubyで バケツソート、これは内部で使っている挿入ソート部分以外で比較をしないソート。 なんかwikipediaのバケツソートのページを見ると、計数ソートと同じだとか、計数ソートのコードや図が乗っているという無茶苦茶な状態なので、英語版のwikipe... 2014.11.16 プログラミング
プログラミング rubyで計数ソート バブルソート、挿入ソート、選択ソート、ヒープソート、マージソート、クイックソート、ノームソートなどなどなどなど、、 これらはソートの為に値と値を比較するで、ある一定の計算量は必要になっています。 が、スリープソート、計数ソート、基数ソート... 2014.11.09 プログラミング
プログラミング スリープソート スリープソートがかっこ良すぎる。 JavaScriptで書くとすると下記のコードなんだけど、要は数字の分だけスリープして出力している。 例えば というデータの並びだったとすると、10ミリ秒後に10、3ミリ秒後に3を出力することでソート済... 2014.11.03 プログラミング
プログラミング [ruby] ヒープソート実装 ヒープソートも書いた。 配列 a[] を下の図のように使えば、ヒープを表すことができるため、ヒープの実装には配列を使う。 子の添字を取得することも用意で、左の子は添字 * 2 + 1、右の子は添字 * 2 + 1で求めることができる... 2014.10.28 プログラミング