問題タブ [catalan]

このWolframリンクでは、「ラベル付き」バイナリ ツリーについて少し説明しました。それで、「ラベルのない」二分木と呼ばれるものもありますか？両方の簡潔な説明は本当にいいでしょう。

なぜ私はこれを探しているのですか？
私はこの質問に答えようとしています:

n個の異なる要素のセットと、n個のノードを持つラベルのない二分木が与えられます。二分探索木になるように、与えられた集合を木に移入する方法はいくつありますか?

さて、n 個のノードが与えられたバイナリ ツリーの数が n 番目のカタロニア語であることはわかっていますが、今は混乱しています。

PS：引用符で囲まれた質問の助けもとてもいいでしょう:)

二項係数の方法でカタロニア語の数値を計算するコードがあります。

n が 510 を超えるカタロニア語の数を計算しようとすると、"nan" という結果になります。これはなぜですか? どうすれば解決できますか？

n ペアの括弧のすべての有効な (つまり、適切に開いて閉じた) 組み合わせを出力するアルゴリズムの複雑さを計算するために (Python で) 実装したこのアルゴリズムの時間と空間の複雑さについてご意見をお聞かせください (すべての有効な組み合わせを参照)。括弧の n 対の)

ほとんどの場合、アルゴリズムは時間と空間の点で改善できます。あなたの考えを共有してください。

このコードを使用してカタロニア語数を計算しています。n=6 までは正しい値が返され、その後は間違った値が返されます。電卓を使って手動でチェックしました。例: n=5 カタロニア語番号が 42 の場合は正しいですが、 n=7 の場合、答えは 429 であるため、完全に間違っている 6 になります。何が間違っているのかわかりません。誰か助けてくれませんか？

Lisp または疑似コードで、カタロニア語の関係で並べ替えられたすべてのバイナリ ツリーを一覧表示するアルゴリズムを探しています。

たとえば、入力で次の'(a b c d)結果が得られます。(a (b (c d))) (a ((b c) d)) ((a b) (c d)) ((a (b c)) d) (((a b) c) d)

助けてくれてありがとう。

Catalan Numbersを計算する再帰関数を作成しました。再帰式はです。

私のコード:

ここで、再帰の深さが O(n) であることは明らかです。このアルゴリズムの時間の複雑さはわかりません。再帰ツリーには O(n) 個のノードがあり、任意のノード (葉を除く) で 2 つの呼び出しを行います。辞書に結果が既にあるかどうかのみを確認するため、すべての呼び出しは O(1) です。したがって、時間の複雑さは O(n) です。

私の推論は正しいですか？

ところで、O(n^2) よりも優れた時間計算量で実行される非再帰アルゴリズムを作成するオプションはありますか?

ありがとう！

私は宿題のためにカタロニア語の数ジェネレーターをプログラミングしており、pytohon で再帰的なプログラムを実行しています。

プログラム：

5832 を返します。これは間違った答えですが、

正解は 16796 です。

では、python は PEMDAS に従っていませんか?