力まかせ探索とは 力まかせ探索（ちからまかせたんさく、英: Brute-force search）またはしらみつぶし探索（英: Exhaustive search）は、単純だが非常に汎用的な計算機科学の問題解決法であり、全ての可能性のある解の候補を体系的に数えあげ、それぞれの解…

8王妃（エイトクイーン）問題とは チェスの盤上に、8個のクイーンを配置する。このとき、どの駒も他の駒に取られるような位置においてはいけない。 クイーンの動きは、上下左右斜めの8方向に、遮る物がない限り進める。将棋の飛車と角行を合わせた動きである…

ユークリッドの互除法によって2つの自然数の最大公約数を求める処理をRubyで再帰を用いて実装する。 ユークリッドの互除法とは ユークリッドの互除法（ユークリッドのごじょほう、英: Euclidean Algorithm）は、2 つの自然数の最大公約数を求める手法の一つ…

アルゴリズムの勉強としてリングバッファによるキューをRubyで実装する。 キューとは キュー（英: queue）、あるいは待ち行列はコンピュータの基本的なデータ構造の一つ。データを先入れ先出し[1]のリスト構造で保持するものである。キューからデータを取り…

アルゴリズムの勉強としてRubyでスタックを実装する。 スタックとは スタックは、コンピュータで用いられる基本的なデータ構造の1つで、データを後入れ先出し（LIFO: Last In First Out; FILO: First In Last Out）の構造で保持するものである。抽象データ型…

概要 ハッシュ法（オープンアドレス法）を用いてデータの追加・検索・削除を行う。 ハッシュ法を用いない方法と比べ、データの探索だけではなくデータの追加・削除も効率良く行う事ができる。 オープンアドレス法とは 衝突が発生した際、テーブル中の空いて…

概要 ハッシュ法（チェイン法）を用いてデータの追加・検索・削除を行う。 ハッシュ法を用いない方法と比べ、データの探索だけではなくデータの追加・削除も効率良く行う事ができる。 チェイン法とは 衝突を起こしたキー同士をポインタでつなぐ方式を連鎖法…

概要 ハッシュ法を使用せず昇順にソートされた状態のデータに新しい値の追加を行う。 バイナリサーチのアルゴリズムを用いて挿入すべき位置を見つけ値を追加し、それ以降の全要素を一つずつ後方へ移動するため、ハッシュ法を用いたデータの追加と比べ効率は…

アルゴリズムの勉強としてRubyで二分探索（バイナリサーチ）を実装する。 二分探索とは ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい…

アルゴリズムの勉強としてRubyで番兵法を用いた線形探索を実装する。 番兵法とは データの終了を示すために配置される特殊なデータを指す。この用語は、微妙に異なる以下の2つの意味で使われる。 ・実データには出現しない、データの終了を表すための専用の…

アルゴリズムの勉強としてRubyで線形探索を実装する。 線形探索とは 線形探索（せんけいたんさく、英: linear search, sequential search）は、検索のアルゴリズムの一つ。 リストや配列に入ったデータに対する検索を行うにあたって、 先頭から順に比較を行…

アルゴリズムの勉強としてRubyで分布数え上げソート（カウンティングソート、度数ソートとも呼ばれる）を実装する。 分布数え上げソートとは 分布数え上げソートはソート対象のデータをキーにして、キーの出現回数とその累積度数分布を計算して利用すること…

アルゴリズムの勉強としてRubyでヒープソートを実装する。 ヒープソートとは ヒープソート (heap sort) とはリストの並べ替えを二分ヒープ木を用いて行うソートのアルゴリズムである[2]（ヒープ領域とは無関係であることに注意する）。 アルゴリズムは、以下…

アルゴリズムの勉強としてRubyでマージソートを実装する。 マージソートとは マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボト…

アルゴリズムの勉強としてRubyでクイックソートを実装する。 クイックソートとは クイックソート (quicksort) は、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。 n個のデータをソートする際の最良計算量および平均計算量は…

アルゴリズムの勉強としてRubyでシェルソートを実装する。 シェルソートとは シェルソート（改良挿入ソート、英語: Shellsort, Shell sort, Shell's method）は、in-placeな比較ソートのアルゴリズムの一種である。シェルソートは、交換によるソート（バブル…

アルゴリズムの勉強としてRubyで選択ソートを実装する。 選択ソートとは 選択ソート（英: selection sort）は、ソートのアルゴリズムの一つ。配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えをおこなうこと。最悪計算時間がO(n2)…

アルゴリズムの勉強としてRubyで挿入ソートを実装する。 挿入ソートとは 挿入ソート（インサーションソート）は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともにO(n2)と遅いが、ア…

アルゴリズムの勉強としてRubyでバブルソートを実装する。 バブルソートとは ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が…