アルゴリズム

スポンサーリンク
プログラミング

rubyではbit全探索よりcombination全列挙のほうが早かった

バージョン情報 Ruby 2.3.3 本題 過去にbit全探索の記事を書いていたことを思い出した。 ここにあるRubyの例で、全組み合わせの列挙をcombinationを使う方法を書いているんだけど、この記事によれば遅いって書いて...
プログラミング

RubyでLCSを求める

去年LCS長を求めるプログラムをRubyで書いた。 今回は、LCSそのものを求めるプログラムを書いた。 class String def lcs(target) lcs_len = Array.new(size + 1) ...
プログラミング

【動的計画法】ロッド切り出し問題

12月、1月はCODEVS4に集中してたり、2月はうわおえを更新してたりで、アルゴリズムイントロダクションを勧められていなかったが再開! 動的計画法を解説している書籍やサイトでは、ナップザック問題を取り上げている場合が多い気がする。 でも...
プログラミング

rubyの2分探索木実装

理屈は知っていても、なかなか自分で実装することはないであろう2分探索木を実装する。 class BinaryTree attr_accessor :root def initialize self.root = nil...
プログラミング

「ラングトンのアリ」のシミュレータ作った

ラングトンの蟻とも言う。 タイトルの通りで、JavaScriptを使ってラングトンのアリシミュレータを作った。 ラングトンのアリの説明はwikipediaに任せる。 これはwikipediaにある拡張ラングトンのアリに対応しており、フ...
プログラミング

バケツソートをRubyで

バケツソート、これは内部で使っている挿入ソート部分以外で比較をしないソート。 なんかwikipediaのバケツソートのページを見ると、計数ソートと同じだとか、計数ソートのコードや図が乗っているという無茶苦茶な状態なので、英語版のwikipe...
プログラミング

rubyで計数ソート

バブルソート、挿入ソート、選択ソート、ヒープソート、マージソート、クイックソート、ノームソートなどなどなどなど、、 これらはソートの為に値と値を比較するで、ある一定の計算量は必要になっています。 が、スリープソート、計数ソート、基数ソート...
プログラミング

スリープソート

スリープソートがかっこ良すぎる。 JavaScriptで書くとすると下記のコードなんだけど、要は数字の分だけスリープして出力している。 例えば というデータの並びだったとすると、10ミリ秒後に10、3ミリ秒後に3を出力することでソート済...
プログラミング

[ruby] ヒープソート実装

ヒープソートも書いた。 配列 a[] を下の図のように使えば、ヒープを表すことができるため、ヒープの実装には配列を使う。 子の添字を取得することも用意で、左の子は添字 * 2 + 1、右の子は添字 * 2 + 1で求めることができる...
プログラミング

[Ruby] 最大部分配列問題を解く

最大部分配列問題。 配列内のある部分を足しあわせたとき、その合計が最大化する部分を探す問題。 例えば配列 があったときに、足しあわせた合計が最大になる部分は、添字1〜4の。要素の合計は15になる。 分割統治法を利用して解くことになる。...
スポンサーリンク
タイトルとURLをコピーしました