とくにあぶなくないRiSKのブログ

危ないRiSKのブログだったかもしれない。本当はRiSKだけどググラビリティとか取得できるIDの都合でsscriskも使ったり。

PKU JudgeOnline 1003 (3)

Welcome To PKU JudgeOnline 1003 -- Hangover
どのようにコードが短くなっていったか。(ネタバレが嫌な方は続きを見ないでねん)

最初のコード:

double f(n){
double r=0;
for(++n;n>1;--n)
r+=1.0/n;
return r;
}
main(n){
double a;
while(scanf("%lf",&a),a){
for(n=1;f(n)<a;++n);
printf("%d card(s)\n",n);
}
}

  1. カードの枚数を引数にとり,hangover(突き出た屋根)の長さを返す関数を書く(内部にループあり)
  2. その関数の引数(カードの枚数)を1ずつ増やして,目標の長さより大きくなったらそれを出力(ループあり)

このコードの問題は,枚数から hangover の長さを一度求めた後,再び同じ計算をすることがあるということです。
つまり,f(2)を求める課程でf(1)の答えが出ています*1。この無駄をなくすには,一度答えをキャッシュする必要があると思います。しかし,そんな事をしたらメモリは食うし,コードも長くなるしでうれしくありません*2。ですから,これは些細な問題となります。
もう一つの問題は,目的の値を出すために2重ループになっていることにあります。これはただ手動インライン展開すれば自然と良くなります。コードも実行時間も短くなりました*3

main(a){
double c,d;
while(scanf("%lf",&c),c){
for(d=0,a=2;(d+=1.0/a)<c;++a);
printf("%d card(s)\n",a-1);
}
}

次に,オブジェクトの数を減らせるか考えます。このためには発想を逆転します。つまり,目標の長さから一枚重ねるたびに hangover する分を引いていくようにします。
main(a){double b;while(scanf("%lf",&b),b){for(a=2;(b-=1.f/a)>0;++a);printf("%d card(s)\n",a-1);}}

だいぶ短くなりました。
おっ,精度が心配だったけど float でも大丈夫みたい。
main(a){float b;while(scanf("%f",&b),b){for(a=2;(b-=1.f/a)>0;++a);printf("%d card(s)\n",a-1);}}

さらに 1.f が冗長ですね。 1. だけで十分。ついに昨日のコードとなりました。
おまけ,同じコード長で別解もあります。
main(){float a,b;for(;scanf("%f",&b),b;){for(a=2;(b-=1/a)>0;++a);printf("%d card(s)\n",a-1);}}

*1:ですから,再帰に置き換えられますね。余談ですけど。

*2:中国の某サイトではJavaにてこの実装を紹介していました。

*3:しかし,なぜかメモリは増えた orz