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

ビューティフルコード (THEORY/IN/PRACTICE)

ビューティフルコード (THEORY/IN/PRACTICE)

今日はちょっと遅くなったので、ちょびっとだけ。例3-7。この例はちゃんと本文を読まないと理解が難しい。例3-6とは取り扱っている問題が異なる。問題としては「ランダムな配列を並び替えるのに、クイックソートでは平均で何回の比較を行うか?」が問題となっている点に注意するべし。でないと、本気で訳が分からないことになっちゃう。

コードとしては単純。次のようなコードになります。

#include <stdio.h>
#include <stdlib.h>

double c(int n);

int randint(int min,int max);

int main(void)
{
  int i = 0;

  for( i = 0 ; i < 20 ; i++ ){
    printf("i = %d , c = %f\n",i,c(i));
  }
  return 0;

}

double c(int n){
  if ( n <= 1 ) return 0;
  double sum = 0;
  int i;
  for(i=1;i<=n;i++)
    sum += n-1 + c(i-1) + c(n-i);
  return sum/n;
}

あんまり難しいところもないけど、問題は処理速度。むやみやたらに20って書いてあるところを大きくしないこと。でないと、結構後悔します( ̄Д ̄;;。