JavaScript によるデータ構造とアルゴリズムの実装と応用: Stack/Recursion/Hanno

まとめ

この記事では、Stack データ構造の基本的な操作とそのいくつかの応用について紹介します。

括弧の一致検出、式の評価、関数の呼び出しにおける Stack の応用について説明します。

再帰は特別な種類の関数呼び出しです。再帰はプログラミングにおいて非常に重要であり、理解するのが難しいため、再帰についての私の理解を説明します。

***スタックと再帰を使用して、古典的なゲーム「ハノイの塔」をエレガントに解く方法を説明します。

この記事では、式の評価とハノイの塔の HTML5 デモも紹介します。

スタック

導入

Stack はスタックです。以下は Wikipedia の定義です。

コンピュータサイエンスにおいて、特殊なシリアルデータ構造は、データの追加 (英語: push) とデータの出力 (英語: pop) の操作が、リンクされたシリアルまたは配列の一方の端 (トップポインタ、英語: top と呼ばれる) でのみ許可されるという点で特殊です。あるいは、スタックは 1 次元配列または接続されたシリアル接続の形式で実装することもできます。

定義によれば、スタックに対する操作は、プッシュ、ポップ、スタックの最上位要素 (top) の取得の 3 つだけであることがわかります。さらに、スタックはスタックの最上位要素のみを操作できます。つまり、片側のみで操作できます。

スタックに最後に入力された要素が最初にポップアウトされるため、スタックは Last In First Out (LIFO) 構造とも呼ばれます。

スタックの操作は非常に簡単です。スタックを実装するには、単一のリンク リスト (LinkedList) と配列を使用できます。

ただし、JavaScript では、Array に pop() および push() 操作が付属しており、Array[Array.length-1] を使用して top() 操作を実装できます。したがって、別の Stack 型を実装する必要はなく、Array を使用して表現するだけで済みます。

応用

Stack の LIFO プロパティにより、多くの実用的な問題を解決するのに適しています。以下では、そのアプリケーションを 3 つ取り上げて説明します。

括弧の一致検出

通常、エディタでコードを書く場合、一部のエディタでは括弧が互いに一致しているかどうかを自動的に検出します。一致していない場合は、エラー メッセージが表示されます。

Stack の LIFO 機能を使用すると、この機能を簡単に実装できます。

アルゴリズムの疑似コードは次のとおりです。

 //新しいスタックを作成する 
 s =新しいスタック()
 // 終了するまで文字を読み取ります 
 c != EOF まで読み取られている間: 
     //文字が「(」「[」「{」などの開き括弧の場合は、スタックにプッシュします 
     c が開いている場合:
        s.push(c) 関数
     //文字が ')' ']' '}' のような閉じ括弧の場合 
    それ以外  c が閉じている場合: 
         //スタックが空の場合、またはスタックの先頭の要素が開き括弧と一致しない場合は、エラーが報告されます 
         s が空の場合、または f s.pop() が c に対応していない場合: 
            エラーを返します!
 //*** スタックが空でない場合はエラーを報告します 
 s が空でない場合: 
    エラーを返します!
 //エラーが返されない場合は、通常に戻ります 
返品OK

アルゴリズムの原理は、閉じ括弧に遭遇すると、常にそれに一致する最後の開き括弧を探すというものです。開き括弧が見つからない場合、または最後の開き括弧が一致しない場合は、エラーが報告されます。

常に最後の要素だけを見つける必要があるため、開いた括弧をスタックにプッシュし、一致したときにポップします。

Stack の特性により、このアルゴリズムは単純かつ明確であり、消費される時間の計算量は線形レベル O(n) です。

式の評価

Stack の強力な機能により、式の評価にも使用できるようになります。

2+4/(3-1)という式を考えてみましょう。

この式には 3 種類の記号があります。

1. オペランド: 2 4 2 2
2. 演算子: + / -
3. 括弧: ()

これを計算するアルゴリズムは次のとおりです。

 // 2 つのスタックを割り当てます。ops は演算子スタック、nums は数値スタックです。  
 ops =新しいスタック、nums =新しいスタック
// 式の最後まで文字を読み取ります 
式内の c を読み取り中にEOF にならない: 
     //左括弧の場合は演算子スタックに入る 
     c が'(' の場合:
        ops.push(c) 
     //数字の場合はデジタルスタックを入力します 
    それ以外  c が数値の場合:
        nums.push(c) 
     //演算子の場合 
    それ以外  c が演算子の場合: 
         //演算子スタックの最上位要素の優先度がcより高いか等しい場合、単一の演算が実行されます 
         ops.top()はc と同等かそれより優先されます:
            op = ops.pop()
            opn2 = nums.pop()
            opn1 = nums.pop() 
             // 単一の演算を実行し、オペランドをデジタルスタックに格納します 
            nums.push( cal(op,opn1,opn2) ) 
     //右括弧の場合 
    それ以外  c が')'の場合: 
         //スタックの一番上の要素が左括弧でない限り、演算子スタックがポップされ、計算結果がデジタルスタックに格納されます 
        op = ops.pop() 
         op != '('の場合:
            opn2 = nums.pop()
            opn1 = nums.pop()
            nums.push( cal(op,opn1,opn2) )
            op = ops.pop()
 //デジタルスタックの最上位要素を返す 
 nums.top()を返す

以下は式評価のデモです。

関数呼び出し

コードをデバッグしているときに、関数エラーが発生すると、次のような同様のエラー プロンプトが表示されることがよくあります。

 /Users/tim/Codes/JavaScript/dsaginjs/DSinJS/Stack/InfixExpression.js:59   
     prioty[a] ) prioty[b]を返します。
                     ^
構文エラー: 予期しないトークン)
    Module._compile (module.js: 439 : 25 )で
    Object.Module._extensions..js (module.js: 474 : 10 )で
    Module.load で (module.js: 356 : 32 )
    Function.Module._load (module.js: 312 : 12 )で
    Function.Module.runMain (module.js: 497 : 10 )で
    起動時 (node.js: 119 : 16 )
    node.js: 902 : 3で 

実際のところ、1 か所でミスをしただけなのに、なぜこれほど多くのエラー メッセージが出力されたのでしょうか?

その理由は、インタープリターがエラーを報告する関数のすべての呼び出し関数のスタックを出力するためです。

関数が呼び出されると、呼び出された関数に切り替える必要がありますが、関数呼び出しが終了すると、元の位置に戻らなければなりません。

スタックを使用すると、これを秩序だった方法で実現できます。つまり、関数が呼び出されると、現在の関数の変数とコンテキストがスタックにプッシュされます。関数呼び出しが終了すると、スタックがポップされ、以前のコンテキストと変数が取得されます。

#p#

再帰

関数呼び出しの特殊なケースは、自分自身を呼び出すもので、再帰と呼ばれます。

最も簡単な例、階乗を解く:

関数階乗(n) { 
     n == 0 ? 1を返します: n * 階乗(n- 1 );
 }

再帰は非常に便利なツールですが、初心者にとっては理解が難しいことがよくあります。再帰についての私の理解についてお話ししたいと思います。

1. 再帰には終了条件が必要であり、そうでなければ無限に再帰することになる。
2. 各再帰では問題を絞り込む必要があります。そうしないと、終了条件に到達できず、再帰が無限になってしまいます。

明らかに、再帰は自分自身を呼び出すことであり、理髪店で鏡を見るのと非常に似ています。終了条件がなければ、自分自身がいくつあるかを知ることはできません。

[[111099]]

実際、再帰を使用して問題を解決する本質は、元の問題よりも小さく、同じ方法で処理できる問題を見つけることです。さらに、再帰がいつ終了するか、つまり再帰の終了条件を決定する必要があります。

たとえば、階乗を求めるには次のようにします。

• 3 の階乗はどうやって求めますか? 3 の階乗は 2 の階乗の 3 倍に等しくなります。
• 2 の階乗はどうやって求めますか? 2 の階乗は 1 の階乗の 2 倍に等しくなります。
• 1 の階乗はどうやって求めますか? 1 の階乗は 1 と 0 の階乗を掛けたものに等しくなります。
• 0 の階乗はどうやって求めますか? 0 の階乗は 1 であることが既にわかっているので、0 の階乗を求める必要はありません。

このように問題を分析すると、n の階乗はどのように計算するのでしょうか?

答えは、n が 0 の場合は 1 を返し、それ以外の場合は n-1 の階乗を n 倍したものを返します。

したがって、階乗の再帰式は次のようになります。

関数階乗(n) { 
     n == 0 ? 1を返します: n * 階乗(n- 1 );
 }

階乗再帰の終了条件は n==0 です。問題を絞り込む方法は、n-1 の問題が n の問題と同じであることを見つけることです。

明らかに、再帰の基礎は関数呼び出しであり、関数呼び出しの基礎はスタックです。したがって、各再帰のコストは、スタックを継続的にプッシュおよびポップする必要があり、多くのスペースを消費し、冗長な計算が発生する可能性もあります。

考えられる解決策としては、末尾再帰、動的プログラミングなどがあります。

ハノイの塔

ハノイの塔は古典的なゲームです。

Wikipedia の説明は次のとおりです。

極はA、B、Cの3つあります。ロッド A には N (N>1) 個の穴あきディスクがあり、ディスクのサイズは下から上に向かって小さくなります。次の規則に従って、すべてのディスクをポール C に移動する必要があります。

1. 一度に移動できるディスクは 1 つだけです。
2. 大きなお皿を小さなお皿の上に積み重ねることはできません。

[[111100]]

ハノイの塔には多くの解法があります。***Ya の解法は再帰的方法だと思います。ハノイの塔の解法がわからない場合は、読み続ける前に再帰的方法を使用して解いてみてください。

確かに、最初は再帰的に解決する方法がわからなかったのですが、解決策を読んでみると、エレガントで独創的であることがわかりました。

ハノイの塔の再帰疑似コードは次のとおりです。

 //ルールに従って列 a から列 c に n 枚のプレートを移動します 
ハノイ(n,a,b,c)
 { 
    もし(n > 0 )
    {
        ハノイ(n- 1 ,a,c,b); 
         //列aの上部プレートを列cに移動する 
        c.push(a.pop());
        ハノイ(n- 1 ,b,a,c);
    }
 }

アルゴリズム全体の考え方は次のとおりです。

1. 列aのn-1枚のプレートを一時的に列bに移動する
2. 列aには***ディスクしか残っていないので、それを目的の列cに移動します
3. *** 次に、列bのn-1枚のプレートを目的の列cに移動します。

問題の絞り込み戦略は、n 枚のプレートを a から c に移動する方法であり、同じことが n-1 枚のプレートを a から c に移動する場合にも当てはまります。

n が 3 に減ったら、まず上の 2 つのプレートを b に移動し、次に下のプレートを c に移動し、最後に b 上の 2 つのプレートを c に移動します。
n が 2 に減ると、問題はようやく直感的になります。上部のプレートを b に移動し、次に下部のプレートを c に移動し、最後にプレートを b から c に移動します。
n が 1 に縮小すると、a の上部プレートを c に移動するだけです。

これが問題の終了条件です。

このアルゴリズムの時間計算量は指数関数的に O(2^n) です。導出については、「ハノイの塔の計算量」を参照してください。最小の解決ステップ数は 2^n-1 です。

ハノイの塔の伝説：

伝説によれば、インドのある寺院には 3 本の柱があり、その上に 64 枚の金の板が張られていたそうです。修道院の修道士たちは、古代の予言に従って上記の規則に従ってプレートを動かしました。予言では、プレートが動かされると世界が終わるとされていました。この伝説はブラフマーの塔のパズルと呼ばれています。

伝説が真実であれば、修道士たちがこの作業を完了するには 2^64 − 1 歩必要になります。1 秒間に 1 枚の皿を移動できたとすると、完了までに 5846 億年かかります。宇宙全体の年齢は現在わずか137億年です-.-!

こちらはハノイの塔のデモです:

オリジナルリンク: http://wuzhiwei.net/ds_app_stack/