JavaScript での再帰のその他の例-jsチュートリアル-php.cn

JavaScript での再帰のその他の例

高洛峰

リリース： 2016-11-28 11:36:08

オリジナル

891 人が閲覧しました

その他の例

2 番目の再帰例は、2 つの自然数の最大公約数を見つけることです (懐かしい中学校時代に戻ったことはありますか)。以下のプログラムは、古典的なユークリッド除算法を使用しています。

[javascript]
//最大公約数
// a と b が両方とも正の整数であると仮定します
function gcd(a, b){
if (a < b) return gcd(b, a);//確実に a >= b
var c = a % b;
if (c === 0)
else
return gcd(b, c)
}

//最大公約数

// a と b は両方とも正の整数であると仮定します
function gcd(a, b){
if (a < b) return gcd(b, a);//ensure a >= b
var c = a % b;
if ( c === 0)
return b;
else
return gcd(b, c);
}
数学的再帰定義計算に変換できる上記の条件または解に加えて、再帰的手法も適用できます。関連するデータへの構造とは、リンクされたリスト、グラフ、ツリーなど、再帰的な形式で定義された問題です。

それでは、迷路の例を見てみましょう。迷路は数学的な図に抽象化できます。道路の各分岐点は点であり、その間の道路はエッジです。 2 つの特別なポイントがそれぞれ入口と出口として定義されます。

以下はJavaScriptで定義された点とグラフです。各ポイントには番号とラベルとして ID が含まれており、隣接するポイントは配列に保存されます。グラフには点を追加する方法、より便利な点IDを直接追加する方法、エッジを追加する方法があります。

[javascript]

//頂点を定義します
function Vertex(id){
stem.id=id;
stem.adjacent=[];
//defineグラフ
function Graph(){
varstem={}, vertices={};
//グラフに頂点を追加
function add(vertex){
if (vertexinstanceof Array){
for (var i=0) , v=vertex; i vertex.id]=vertex; // ID から頂点を作成それらをグラフに追加します
function addIds(ids){
var id;
for (var i=0; i id=ids[id ] =Vertex( id);
} }
}
// 2 つの頂点の間にエッジを作成
function connect(i1, i2){
var v1=vertices[i1], v2=vertices[i2]
if (v1 && v2 ){
誰誰誰誰誰誰誰誰v1.adjacent.push(v2);
ステムを返す

//頂点を定義します
function Vertex(id){
var Stem={};
stem.id=id;
stem.adjacent=[];
return Stem;
}
//グラフを定義します
function Graph (){
var Stem={}, vertices={};
//グラフに頂点を追加します
function add(vertex){
if (vertex instanceof Array){
for (var i=0, v=vertex; i vertices[v[i].id]=v[i];
}
}
vertices[vertex.id]=vertex;
}
// ID から頂点を作成し、追加しますそれらをグラフに追加します
関数 addIds(ids){
var id;
for (var i=0; i id=ids[i];
vertices[id]=Vertex(id) ;
}
}
// 2 つの頂点の間にエッジを作成します
function connect(i1, i2){
var v1=vertices[i1], v2=vertices[i2];
if (v1 && v2){
v1.隣接.push(v2);
v2.adjacent.push(v1);
}
}
stem.vertices=vertices;
stem.add=add;
stem.addIds=addIds;
stem.connect=connect;
return ステム;
} 私たちが迷路を抜け出す思考回路は、入り口から始まり、出口に到達するまですべての隣接する点を通過することです。出口に到達した場合は、遍路全体を退出して入口に戻り、途中で通過した各点を記録し、最後に入口から出口までを書き出す。これは最適な方法ではなく、得られる結果は必ずしも最適な回線ではありませんが、入口と出口の間が通過できていれば、必ず 1 本の回線に到達できます。迷路を探索し、結果を出力します

function walkOut(entry, exit){

//迷路から出て結果を出力してみます
function walkOut(entry, exit){
var Visited = [], path = [];

function walk(vertex){
if (vertex === exit) {//出口を検索します
path.push(vertex);
return true;
}
if (visited.indexOf(vertex) > -1) {//頂点が訪問されました
return false;
}
Visited.push(vertex);//各頂点を記憶します
var Connected = vertex.adjacent;
var length = Connected.length;
if (length === 0) {//頂点は孤立しています
return false;
}
for (var i = 0; i if (walk(connected[i])) {//各隣接する頂点を試します
path.push(vertex);
return true;
}
}
}

function printPath(){
var footprint = '';
var length = path.length;
for (var i = length - 1; i > -1; i--) {
footprint += path [i].id;
フットプリント += i === 0 ? '' : '' > ';
}
print(footprint);
}

if (walk(entry)) {
printPath();
}
else {
print('出不去！');
}
}我軬可试验

[javascript]
function testMaze(){
var g=Graph();
g.addIds([1, 2, 3, 4, 5, 6]);
g.connect(1, 2);
g.connect(1, 3);
g.connect(1, 4);
g.connect(2, 3);
g.connect(3, 5); //你可画出这个图
walkOut(g.vertices[1], g.vertices[5]);//1 > 2＞ 3＞ 5
walkOut(g.vertices[1], g.vertices[6]);//出不去！
walkOut(g.vertices[2], g.vertices[5]);//2 > 1> 3＞ 5
}

function testMaze(){
var g=Graph();
g.addIds([1, 2, 3, 4, 5, 6]);
g.connect(1, 2);
g .connect(1, 3);
g.connect(1, 4);
g.connect(2, 3);
g.connect(3, 5); //你可画出这个图
walkOut(g.vertices[1], g.vertices[5]);//1 > 2＞ 3＞ 5
walkOut(g.vertices[1], g.vertices[6]);//出不去！
walkOut(g.vertices[2], g.vertices[5]);//2 > 1> 3＞ 5
} もちろん、実際の生活の中で、私たちは、各ネットワークポートで選択された回線を使用するだけで、このようなセキュリティ方法を使用して、考えられるあらゆる迷走を実行することもできます。