debedebe回答ポイント 50pt

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

※ 有料アンケート・ポイント付き質問機能は2023年2月28日に終了しました。

ログインして回答する

みんなの回答

flashcafe2005/11/16 22:18:37
満足50pt

http://www.theory.csc.uvic.ca/~cos/inf/tree/BinaryTrees.html
Info on Binary Trees

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

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

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;

}

スター
- debedebe 2005/11/17 21:32:56
  
  プログラムの検証、どうもです。もう関数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!]にするやり方がわかったので、いったん終了します。ありがとうございました。

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

みんなの回答

flashcafe2005/11/16 22:18:37
満足50pt

debedebe 2005/11/17 21:32:56

この質問へのコメント

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

質問の情報

この質問のカテゴリ

この質問に含まれるキーワード

人気の質問

メニュー

PC版

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

みんなの回答

flashcafe2005/11/16 22:18:37 満足50pt

debedebe 2005/11/17 21:32:56

この質問へのコメント

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

質問の情報

この質問のカテゴリ

この質問に含まれるキーワード

人気の質問

メニュー

PC版

flashcafe2005/11/16 22:18:37
満足50pt