二分木について、要素数nの場合、全部で何パターン考えられるのでしょうか。一般式を教えてください。

条件
・根も要素として数える
・右の子と左の子を区別して考える
n=1のとき1パターン、n=2のとき2パターン、
n=3で5パターン、n=4で14、n=5で42、n=6で132になる。。。はずです。
もう一つ。
この問題を再帰的に解決する(要素数nを受け取り、パターン数を返す)関数treeをC++の構文にのっとって書いた場合、以下のプログラムであってますでしょうか。(nは1以上の整数)
int tree(int n){
int p=0;
if((n==0)||(n==1)) return 1;
for(int i=0;i<n;i++)
p += tree(i)*tree((n-1)-i);
return p;
}

回答の条件
  • URL必須
  • 1人2回まで
  • 登録:2005/11/16 21:41:18
  • 終了:--

回答(1件)

id:flashcafe No.1

flashcafe回答回数50ベストアンサー獲得回数02005/11/16 22:18:37

ポイント50pt

見る限り問題ありません。一応n=13まで確かめて見ましたが、それでも問題ありませんでした。

ただこれを提出する場合は計算結果を配列に維持しなければn=20あたりですでになかなk計算が終わらないでしょう。


1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, 18367353072152, 69533550916004


確かめていませんのでエラーが出るかもしれませんがイメージさえつかめれば。こういう感じで処理すれば良いでしょう。


// グローバル変数を設定する

int treeret[50];

// 予め初期化する

for (i = 0; i < 50; i++) treeret[i] = 0;

// 0と1は入れておく

treeret[0] = 1; treeret[1] = 1;


// 出力はこんな感じでいけるはず

printf(”%d”, tree(20));


int tree(int n){

int p = 0;

// すでに計算済みか調べ、計算済みならその値を返す

if (treeret[n] != 0) return treeret[n];

for(int i = 0; i < n; i++)

p += tree(i) * tree((n - 1) - i);

// 計算結果を記録しておく

treeret[n] = p;

return p;

}


// PHPで実験したのでこちらのコードもはっておきます

for ($i = 0; $i < 30; $i++) echo tree($i) . ”¥n”;

$tree = array(1, 1);

function tree($n){

global $tree;

if (isset($tree[$n])) return $tree[$n];

if(($n==0)||($n==1)) return 1;

for($i=0;$i<$n;$i++)

$p += tree($i)*tree(($n-1)-$i);

$tree[$n] = $p;

return $p;

}

id:debedebe

プログラムの検証、どうもです。もう関数treeに関してはいいです。記述方法としてC++を選んだだけ、今回は数学的に、二分木に興味があるので。特にこれで何かシステムを運用しようというわけではないです。が、勉強になりました。

id:flashcafe

で、がんばってURLの文を読んでみたんですが、今回私の欲している式というのは

(2n)!/[(n+1)!n!]

こいつですか。

以下、これの導出方法を説明してくださる方を募集します。

なぜ、(2n)!/[(n+1)!n!]になるのか。

それともすでにそのページに書いてあるんかな。。。、

とりあえず、

http://www2.ocn.ne.jp/~mizuryu/jyugyo/bokansu3.htm

ここを見たら関数treeを(2n)!/[(n+1)!n!]にするやり方がわかったので、いったん終了します。ありがとうございました。

2005/11/17 21:32:56

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません