3

与えられた数の二分木ノード（X）は、Xノードを持つ二分木のランダム順列の数を返すメソッドを記述します。

例：

X = 1：1

     o

X = 2：2

     o    o
   o        o

X = 3：5

        o    o          o     o        o
      o        o      o         o    o   o
    o            o      o     o

私は結局：

    public static int numOfPerms(int numOfNodes) {
       if (numOfNodes<=2 && numOfNodes > 0) {
           return numOfNodes;
       }
       int res = 1;
       for (int i=1; i<=numOfNodes; i++) {
           res = res*(4*i-1)/(i+1);
       }
       return res;
    }

ここでより良い解決策を共有していただければ幸いです。

4

3 に答える 3

5

カタラン数はあなたの木を数えることができると思います（組み合わせ論のアプリケーションに関する部分を参照してください）。それらは、通常、この漸化式によって定義されるよく知られたシーケンスを形成します。

C_nの漸化式

この再発は、ツリーまたは再帰構造に関する列挙の問題で発生することが多いため、十分に研究されています。私がリンクしたウィキペディアのエントリは、n番目のカタラン数に役立つ閉じた形の式をいくつか示しています。

閉じた式

それらはすべてコードの実装に適しており、再帰的なアプローチよりもはるかに高速です。

于 2012-07-09T15:02:49.237 に答える
4

わかりました、私が見る限り、あなたの解決策は正しくありませんよね？（numOfNodes=414ではなく12を返すため）

直感的には、再帰的なアプローチを採用します。

  1. 1つのノードを親ノードとして使い切る
  2. 2つのセットへのすべての可能な分割について、両方のセットの関数を再帰的に呼び出します
  3. 各部門の2つのセットの結果を乗算し、すべての部門の積を合計します
  4. 合計を返す

しかし、それを実装する前に、私はこれのための簡単な公式がないことを確認します。クイックで1つ見つかりませんでした（これは、1つがないという意味ではありません）。

編集：別の回答ですでに述べたように：n番目のカタラン数を計算することもできます。

于 2012-07-09T14:59:15.577 に答える
2

この再帰的な方法を試してください。

static int numOfPerms(int numOfNodes) {
    if (numOfNodes == 1) {
        return 1; 
    }

    numOfNodes = numOfNodes - 1;
    return ((numOfPerms(numOfNodes) * (2*numOfNodes+2) * 
            (2*numOfNodes+1))/((numOfNodes+1)*(numOfNodes+2)));
}
于 2012-07-09T15:40:03.167 に答える