ビューティフルコード (THEORY/IN/PRACTICE)
- 作者: Brian Kernighan,Jon Bentley,まつもとゆきひろ,Andy Oram,Greg Wilson,久野禎子,久野靖
- 出版社/メーカー: オライリージャパン
- 発売日: 2008/04/23
- メディア: 大型本
- 購入: 30人 クリック: 617回
- この商品を含むブログ (171件) を見る
今日はちょっと遅くなったので、ちょびっとだけ。例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って書いてあるところを大きくしないこと。でないと、結構後悔します( ̄Д ̄;;。