問題タブ [catalan]

このコードを使用して Python でカタロニア語の数を計算しようとしていますが、うまくいきません。どうすれば修正できますか？

ここに私が持っているコードがあります:

ブール式を括弧で囲む方法の数を計算します。たとえば、ブール式は 1^0|0|1 のようなもので、演算子は ^、&、| のいずれかになります。

いくつかの参照と計算を行ったところ、方法の数は常に (2n)!/((n+1)!n!) のようです。ここで、n は演算子の数です。方法の数が常に (2n)!/((n+1)!n!) である理由を誰かが知っている場合は、洞察を共有していただきありがとうございます。

これは、括弧の異なる方法をどのように意味するかについての例です。たとえば、括弧の 2 つの異なる方法は、両方とも False になります。

1^((0|0)|1) 1^(0|(0|1))

前もって感謝します、リン

カタロニア語の数字を計算するためにメモ化を使用しようとしていますが、うまくいかないようです。何を変更する必要がありますか?

ありがとう！

対角線の上を通過しない、n × n の正方形セル ( pic )

を持つグリッドのエッジに沿った単調格子パスのカタロニア語数を計算する再帰関数を作成するように依頼されました ( pic )。ループ、再帰呼び出しのみ...これは私がしたことです:

このコードが最適かどうかはわかりませんが、機能します... この関数をメモ化関数に変換したいと考えています。しかし、それが機能をより効率的にする方法と理由を理解できません。メモ化されたフィボナッチの方が効率的である理由は理解できますが、ここでは常にパスの最後に到達してから 1 または 0 を返さなければならないので、配列内に 1 / 0 を格納するとどうなりますか?

あらゆる種類の助けをありがとう

私はこの問題についてしばらく考えていました：

2*n 個の括弧を正しく*配置する方法はいくつありますか?
*正しく配置された一連の括弧には、その末尾に同数の開き括弧と閉じ括弧があり、シーケンス全体で閉じ括弧よりも大きいか等しい量の開き括弧があります。

たとえば、 の場合、次の方法n=3があり5ます((())), ()(()), ()()(), (())(), (()())。

ネストされた括弧をツリーとして表現することを考えていましたが、うまくいきませんでした。

int リストから可能なすべてのツリーを生成したいのですが、生成する[Int] -> [T]ツリーは 1 つだけです。

これらのカタロニア数字のように。リストのサイズが 3 の場合、可能なツリーを 5 つ、4 の場合は 14 の可能なツリーを生成します。

コード：

例えば：toT [1..3]

出力:N (L 1) (N (L 2) (L 3))とN (N (L 1) (L 2)) (L 3).

今、私はこれが好きでした

どうやってやるの ？再帰的に同じリストを送信しますが、長さは下降します [1,2,3] サイズ 3 を再度送信します [1,2,3] 長さ 2 を送信します