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

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

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

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

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

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

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

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

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

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

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

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

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