ビューティフルコードを読み進めるその4

で、先に読み進めてた結果、例3-5を書いてみる。l=1としてコードを書き換えると以下のコードになる。

void qc(int n){
  int m;
  if ( n <= 1 ) return;
  m = randint(1,n);
  comps += n - 1;
  qc(m-1);
  qc(n-m);
}

うん。これは分かりやすい。確認として、計算回数を見てみてもcompsは前回と同じ162242。すばらしい。

で、その流れで例3-6はただ単純にqc関数をcc関数に変換して、再帰を活用するのみ。

int cc(int n){
  int m;
  if ( n <= 1 ) return 0;
  m = randint(1,n);
  return n - 1 + cc(m - 1) + cc(n - m);
}

計算結果もちゃんと確認して162242となってめでたしめでたし。