アルゴリズム

ブレゼンハムのアルゴリズム(Ruby)

ja.wikipedia.org「ブレゼンハムのアルゴリズム」とは画面に線分を描くアルゴリズムです。コードはここの Java 版を移植させていただきました。Ruby コードです。描画に Cairo を使っています。 require "cairo" class Draw W = 400 Side = 10 def initializ…

四則演算のパーサー(Ruby)

ある問題を解いていて、四則演算のパーサーってどんな風に書くのだろうと思って考えてみました。いわゆる「逆ポーランド記法」にパースできればあとは簡単なので、その方針で考えたのですが、自力ではちょっと荷が重かったですね。ということで検索してみた…

Ruby で二分探索木

勉強のために Ruby で二分探索木を書いてみました。 二分探索木の Ruby 実装 · GitHub なお、以下のコードは説明のためなので、Gist のコードを多少簡略化しています。 木(Tree)のクラスと要素(Node)のクラスを定義します。Node は Struct クラスを使っ…

選択ソート(C言語、Go言語)

選択ソートは決められた範囲の中から最小値(もしくは最大値)を選んでいくという、わかりやすいソートです。C言語版。 selection_sort.c #include <stdio.h> void selection_sort(int ar[], int len) { int i, j, min, tmp; for (i = 0; i < len - 1; i++) { min = i</stdio.h>…

高速な素数の判定(Ruby)

素数は約数を 2個(1 とそれ自身)もつ自然数ですね。ですから、自然数 n が素数かどうかを判定するには、n がそれ自身より小さい自然数(1 を除く)で割ることができるかどうかを確かめればよいわけです。このとき、割る数は を超える必要がないことは明ら…

ヒープソート(C言語、Go言語)

(追記)ヒープを作るのに、何だかふつうとはちがう(オリジナルの?)アルゴリズムを採用してしまったようですね。これでもちゃんと動作しますが、ふつうの方法よりも多少効率が悪いようです。最後にふつうの実装も載せます。 ヒープソートですが、まず「(…

バブルソート(C言語、Go言語)

バブルソートはわかりやすいソートです。隣どうしを比較して、前の方が値が大きければ値を交換します。それを繰り返し行うことでソートします。ただ、わかりやすく実装も簡単ですが、効率はよくありません。ソートのアルゴリズムとしてはまず使わないのでは…

クイックソート(C言語、Go言語)

クイックソートを C言語と Go言語で実装してみました。クイックソートは、配列の中からひとつ任意にサンプルを取ってきます。これを「ピボット」といいます。あとは、配列からピボットを除いたものを、その値がピボットより大きいか小さいかで二つの配列に分…

マージソート(C言語、Go言語)

マージソートを C と Go で実装してみました。このソートは二つの配列をマージ(統合)する作業がキモです。それぞれソートされた二つの配列を、統合してひとつのソートされた配列を作るわけですね。これができればあとは簡単です。C言語。 merge_sort.c #in…

挿入ソート(C言語、Go言語)

C言語で挿入ソートです。挿入ソートは遅いけれどわかりやすい。カードで考えると、(ソート済の)並んだカードの正しい位置に、残ったカードをそれぞれ一枚ずつ挿入していく(なのでそれもソート済になっている)というやり方で全体をソートします。 inserti…

「絶対左折禁止」の迷路を解く(Ruby)

ブログにスターを頂いて、上のサイトを知りました。オリジナルの様々な迷路が出題されている、すばらしくおもしろそうなブログです。皆さんも御覧になってはいかがでしょうか? …とは別にステマでも何でもないのですが、そこで「絶対左折禁止」という迷路が…

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

以前 Ruby で解いたのの Go言語版です。Go言語のお勉強に移植してみました。まずは実行結果。 $ go build solve_maze.go $ time ./solve_maze ************************** *S* *$$$$ * *$* *$ *$ ************* * *$*$$$* $ ************ * *$$$ * $$$$$$$ *…

Go言語で汎用両端キューの実装

Go でキューの実装は、上記事で append を使って簡単にしています。なるほどと思いました。 ふつうはこれで充分ですよね。スタックは2本のキューで実装できるので、これも簡単です。しかし、任意の型を入れられるキュー、しかもメモリを効率よく使うキューが…

ふたたび Ruby で 8 queen(関数型プログラミングっぽく)

ここで Ruby で「8 クイーン問題」を解いてみましたが、関数型プログラミングのお勉強に Common Lisp のコード例を移植してみました。参考にしたのはこのサイトです。 実行するとこんな感じです。 ---------- No.1 ...@.... .@...... ......@. ..@..... ....…

n進グレイコード(Ruby)

ゆえあって n進グレイコードへの変換式を作ることになった。 グレイコード - Wikipedia グレイコードについてはここにあるとおりである。2進グレイコードなら、ネットを検索すればたくさん出てくる。具体例は、Ruby のハッシュで表すとこんな感じだ。 {"0"=>…

最長共通部分列(Ruby)

文字列の「部分列」とは、文字列から任意の文字を取り除いたものをいう。文字列 X と Y があって、文字列 Z が X と Y 両方の部分列になっている場合、Z を X, Y の「共通部分列」という。共通部分列の最長のものが、「最長共通部分列」である。たとえば文字…

フロイド−ワーシャル・アルゴリズム(Ruby)

フロイド−ワーシャル・アルゴリズムは、グラフの全点から全点へのすべての最短経路を求めます。重みは負値を許しますが、負閉路は許しません。上のようなグラフは次のようなハッシュで表現されます。頂点を表わすオブジェクトは何でもかまいません。 g = {a:…

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

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

ダイクストラ法(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)

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

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…