木構造 : アルゴリズム

木構造について記載しています。

再帰 : PHPで実装

n個の数である数で作成できるか調べる問題を再帰で求めます。 例として 1, 3, 5が与えられたとき数9が作成できるかを考えます。 再帰で求めるとき計算量はO(2n)になります。

2分探索 Binary Search : PHPで実装

2分探索をPHPで実装するサンプルです。 whileを使うサンプルと再帰を使うサンプルを掲載しています。

2分探索木 Binary Search Tree : PHPで実装

2分探索木を使うと値の探索がO(lonN)で行えます。PHPで2分探索木を実装するサンプルです。

分割統治 Divide and Conquer : PHPで実装

分割統治は元の問題を分割していき分割された問題の解を統合して最終的な解を求めます。

経路探索 幅優先探索 : PHPで実装

幅優先探索で迷路の最短経路を求めるプログラムです。 スタート(S)、ゴール(G)、通行可(0)、通行不可(1)の2次元配列あるときスタートからゴールへの経路の存在に使います。

経路探索 深さ優先探索 : PHPで実装

深さ優先探索で迷路の探索をするプログラムです。 スタート(S)、ゴール(G)、通行可(0)、通行不可(1)の2次元配列あるときスタートからゴールへの経路の存在に使います。 深さ探索はスタックを使い実装します。また再帰で簡 […]

バックトラックで迷路の全経路を取得 : PHPで実装

迷路に経路が存在するかを判定するために深さ優先探索がよく使われます。また最短経路を幅優先探索で求めることができます。 今回は迷路の始点から終点までの全経路をバックトラックで求めるサンプルを記載しています。

幅優先探索 (Breadth First Search) : PHPで実装

グラフ探索で深さ優先探索とことなり近い頂点から順に訪問していく探索を幅優先探索といいます。

深さ優先探索 (Depth First Search) : PHPで実装

深さ優先はまず行けるところまで探索し訪問可能な頂点がなくなると訪問可能な頂点が持つ頂点まで戻りもどり探索を続行します。

ダイクストラアルゴリズム 単一始点最短経路 Single Source Shortest Path : PHPで実装

重み付きグラグの最短経路を求めるダイクストラアルゴリズムのサンプルです。

バブルソート、クイックソート、リニアサーチ、バイナリサーチ : JavaScript

基本的なアルゴリズム(バブルソート、クイックソート、リニアサーチ、バイナリサーチ)をJavaScriptで書いてみる。

再帰のメモ : PHPで実装

再帰を使うと複雑な処理を簡単な処理で実現できる。