問題タブ [catalan]

これは友人と話しているときに出てきたもので、興味深い問題であり、他の人の解決策を見たいので、ここで質問しようと思いました.

タスクは、1...nの整形式ブラケットのすべての組み合わせを出力する関数 Brackets(int n) を作成することです。Brackets(3) の場合、出力は次のようになります。

ここに示されている方法を使用する：http：//cslibrary.stanford.edu/110/BinaryTrees.html#java

n（n-1）（n-2）... 1、つまりn！

メモ化ツールを使用する場合、複雑さはO（n）ですか？

バイナリ ツリーの場合:ツリー ノードの値を考慮する必要はありません。「N」個のノードを持つさまざまなツリー トポロジにのみ関心があります。

二分探索ツリーの場合:ツリー ノードの値を考慮する必要があります。

中括弧ですべての可能性をどのように生成できますか？

N値は私たちに与えられており、私たちはすべての可能性を生み出さなければなりません。

例：

1）N == 1の場合、1つの可能性（）のみ。

2）N == 2の場合、可能性は（（））、（）（）です。

3）N == 3の場合、可能性は（（（）））、（（））（）、（）（）（）、（）（（））..。

注：左中括弧と右中括弧は一致している必要があります。つまり）（N==1の場合は無効です

再発アプローチを使用してこの問題を解決できますか？

世界！私は問題があります。今日は、カタロニア語の数字を見つけるコードを作成しようとしました。しかし、私のプログラムでは長い数字になる可能性があります。分子と分母を見つけました。しかし、長い数字を分割することはできません! また、このプログラムでは標準ライブラリのみを使用する必要がありました。お願い助けて。これは私のコードです

PS私の悪い英語で申し訳ありません=）

それは私が推測する数学の問題であり、プログラミングは何もありません。

があり、のstackを見つけたいとしpermutationsます1,2,3,...n。私はできpushますpop。たとえば、n=2 の場合: push,pop,push,pop1,2 およびpush,push,pop,pop2,1

n=4の場合、 ..を使用して順列14からのみ取得できます。生成できるスタックの数(1 つだけ) を生成できる人はいますか? 例 f(1)=124stackfunction F(n)permutations

f(2)=2

f(4)=14

n 個のノードを持つ二分木を考えてみましょう。考えられる二分木構造はいくつありますか?

私は次のようなものを試しました：

n >1 の場合は 4(n-1) です。n == 1 の場合は 1?

カタラン数のコードを書きたかったのです。カタラン数は次のように定義されています。

C(n) = 2n C n/(n+1)。しかし、計算する代わりに(2n C n)、次の事実を使用してカタラン数をボトムアップで計算したかったのです。

上記の事実を利用して、これは私の次のコードです：

さて、私の質問は、入力が4のときに上記の関数が12を返すのはなぜですか。c（4）= 14であるため、14を返す必要があります。

誰か助けてもらえますか？

整数のセットが与えられた場合、それから構築できる一意の二分探索木がいくつあるかを調べますか？

私によると、答えは整数セットのサイズによって異なります。セット整数のサイズがnの場合、「n」個の一意の二分探索木を作成できます。

答えがわからない..私は正しいですか？