anarchy golf - Fifth Identity 解答編

anarchy golf - Fifth Identity

n項目までのフィボナッチ数の二乗和を求める問題。

最後のつめていくところでタイムアップでした。

そもそも、フィボナッチ数の特性っていうのは皆さん知っているものなのか？

いろいろ調べてやっと出来たわけですが。

フィボナッチ数自体はf(0)=0、f(1)=1として、f(n)=f(n-1)+f(n-2)となる数列です

ここから再帰で書くと

f(n){return n<2?n:f(n-1)+f(n-2);}

ただgolf的には長いので、近似式として

f(n)=(int)(((1+√5)/2)^n/√5+1/2)

を使うことになります。(wikipedia参照)

・・・ぱっと見長いですがw

さて、今回の問題ではもう少し必要で

f(0)^2+f(1)^2+ ・・・+ f(n)^2=f(n)*f(n+1)

という法則を使います。(こちらを参照しました。)

先ほどの近似式の1/2は誤差調整分なので置いておいて、

f(n)*f(n+1)

=(((1+√5)/2)^n/√5)*(((1+√5)/2)^(n+1)/√5)

=((1+√5)/2)^(2*n+1)/5

でおおよその値が求められます。

ここから僕の解答

main(i){for(;~scanf("%d",&i);i-10&&printf("%.f\n",pow(.5+sqrt(5)/2,i*2+1)/5+.2));}

が出来ました。

ただ、√5なんかは定数ですのでここから誤差のでない程度の定数、黄金比率に置き換える

と良かったんですが、実験する時間がなくなりました^^;;

ほかの方の解答を見ると

nnさん

main(n){for(;~scanf("%d",&n);)n%5&&printf("%.f\n",pow(sqrt(5)/2+.5,n-~n)/5);}

n*2+1とするところをn-~nとしているのがうまいです。

(~n=-n-1)

inaniwaさん

main(f,n){for(;gets(n);)--f&&printf("%.f\n",pow(1.6180339887,2*atoi()+1)/5);}

黄金比率の直書きです

teebeeさん

main(f,n){for(;gets(n);)--f&&printf("%.f\n",pow(2.618033989,atoi()+.5)/5);}

黄金比率の２乗としています。

これで2*n+1がn+.5でよくなるわけです。

で、見てて思ったんですが、誤差補正って要らないんですね^^;

やっぱとりかかりが遅かったのが痛い。77byteまでならいけたと思います^^;;