問題タブ [catalan]

有効な括弧の数を調べなければなりません。括弧は 2 つのタイプ[] ,()です。の X と Y の数を使用して有効なシーケンスを構築する方法はいくつありますか[] ,()? この問題について([])は、無効な方法、つまり() can't hold []. 再帰よりも優れた解決策があると考えています。

n ペアの括弧のすべての有効な組み合わせを出力するアルゴリズムを実装するために、古典的な問題を実行しようとしました。

このプログラムを見つけました（完全に機能します）：

私が理解しているように、可能な限り左括弧を追加するという考えです。右括弧の場合、右括弧の残りの数が左括弧より多い場合にのみ追加します。左右の括弧をすべて使用した場合は、新しい組み合わせを結果に追加します。重複して構築された文字列がないことを確認できます。

私にとって、この再帰は、たとえばツリーで作業し、たとえば事前注文トラバーサルを行うときのようなものです。左のノードに移動するたびに可能ですが、そうでない場合は右に移動し、次に左に移動しようとしますこのステップの直後。できない場合は、「戻ってきて」右に進み、トラバーサルを繰り返します。私の意見では、ここではまったく同じ考えです。

だから、単純に、時間の複雑さは O(log(n))、O(n.log(n)) のようなものになると思いました。しかし、それについて調べてみると、括弧の組み合わせの数を数える「カタランの数」というものを見つけました....( https://anonymouscoders.wordpress.com/2015/07 /20/そのすべて-カタロニア語/ )

あなたの意見では、時間の複雑さはどのくらいですか? ここで主定理を適用できるかどうか。

n ペアの括弧のすべての有効な組み合わせを出力するアルゴリズムを実装するために、古典的な問題を実行しようとしました。そして、私はこのプログラムを見つけました（これは完全に機能します）：

次に、カタロニア語の数字のアプリケーションを検索していたときに、非常に興味深いアプリケーションを見つけました: https://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics それは言った:

カタロニア語の数字を使用して、n 回の上昇ストロークと n 回の下降ストロークをすべて元の線より上に維持する山脈を形成できます。山脈の解釈は、山が地平線の下に行くことは決してないというものです

そのため、上記のコードを再利用して、この問題の解決策を実装しようとしました。よくわかりませんが、同じ「ロジック」を持っているように見えるので、このコードを再利用できると思います。残念ながら、括弧を「/」と「\」に置き換えるために多くのことを試みましたが、失敗しました。

私はそのようなことをしようとしました:

私にとって、それらは同じロジックを持っています。ブラケットのように、左ブラケット '(' 毎回可能ですが、右ブラケット ')' を追加するのは、右ブラケットの数が左よりも大きい場合にのみ追加します。ここでも同じ理由付けを行うことができますか？「/」を追加するたびに可能ですが、「\」の場合は前に「/」の数を数える必要があります...

ここで特に難しいと感じたのは、すべての正しい山を表示するために、ここに新しい行を挿入するにはどうすればよいかということです。

可能であれば、このコードを再利用するのを手伝ってくれませんか? または、別のコードを最初から開始する必要がありますか?

行列チェーン乗算の問題を研究し、アルゴリズムが何をするかを理解しています。最近、かっこの問題を解くときに重宝するカタロニア語の数字に出くわしました。この問題は、Matrix Chain Multiplication と非常によく似ているように見えました。実際、CLRS では、行列連鎖乗算の章でカタロニア語の数について言及しています。

行列連鎖乗算をカタロニア語のアルゴリズムで解くことができますか? 私の考えは: いいえ、カタロニア語の数字は行列を括弧で囲む方法の数を記述しているため、解決できませんが、元の行列チェーンの問題は別の質問をします-最小のコストを与える括弧を配置する特定の方法.

私の考えは正しいですか？