人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

二分木について、要素数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;
}

●質問者: debedebe
●カテゴリ:コンピュータ 科学・統計資料
✍キーワード:C++ TREE にの パターン プログラム
○ 状態 :終了
└ 回答数 : 1/1件

▽最新の回答へ

1 ● flashcafe
●50ポイント

http://www.theory.csc.uvic.ca/~cos/inf/tree/BinaryTrees.html

Info on Binary Trees

見る限り問題ありません。一応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;

}

◎質問者からの返答

プログラムの検証、どうもです。もう関数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!]にするやり方がわかったので、いったん終了します。ありがとうございました。

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ