« 2016年6月 | トップページ | 2016年8月 »

2016年7月20日 (水)

「階乗フィーバー数問題」の高度じゃないコード

「高度じゃないコード」シリーズその15「階乗フィーバー数問題」です。この問題は、7月16日に開催されたCodeIQ感謝祭の階乗・・・じゃない、会場限定で出題された問題で、解けた方には賞品も出たそうです。私も行きたかったけど、その日はエアコン取り付け工事の仕事も入っていたし、地方在住なのでなかなかこういったのに行く機会がないからなぁ・・・。

そして、その後、ネットで問題が公開されました。

【階乗フィーバー数問題】

最初は、ずっとくそ真面目に全桁計算をしていました。前回インラインアセンブラで敗北したC(gcc)を使って、1バイト1桁・4バイト4桁・4バイト6桁などで区切って計算しましたが、全て実行くんで1秒では全く終わる気配がありません。結局、家のPCでVCを使って計算しました。CPUがしょぼいせいもあるかもしれませんが、答えが出るのに数十秒かかりました。

しばらく、そのままで放置していましたが、ふと、正解ページの掲示板に「stirlingの公式で近似」と書かれているのを読んでようやく気がつきました。上位の6桁だけが間違いなく計算できさえすればよくて、全桁計算する必要なんて全くないことに・・・。

これに気が付きさえすれば後は簡単です。上位6桁の計算に影響を及ぼさない有効桁数を決め、それより下はばっさり捨てます。本当は、四捨五入した方がいいのかもしれませんが、桁数を増やせば切捨てで問題ないと予想。もちろん、指数部分も結果とは関係ないので無視します。

続きを読む "「階乗フィーバー数問題」の高度じゃないコード"

| | コメント (2) | トラックバック (0)

2016年7月 7日 (木)

「アフター・ドット問題」の高度じゃないコード(高速編)

「高度じゃないコード」シリーズその14「アフター・ドット問題」、その後編(高速編)です。

前回のままのやり方ではそんなに高速にはならないだろうから、根本的に処理を変える必要がありました。まず、前回、b を 2 と 5 で割れるだけ割って b' を求めましたが、逆に、この b' を基準に考えてみます。さて、b' とは 2 でも 5 でも割り切れない数字なので、一の位が 1, 3, 7, 9 の自然数です。それ以外の、一の位が 0, 2, 4, 5, 6, 8 の数字は、b' に 2 と 5 をある回数掛けることで出てきます。

ここで、ある b' に対して、2 と 5 のべき乗の積を掛けたのが b ということになるので、n ÷ b' 以内に存在する 2 と 5 のべき乗の積の数が b の取り得る値の数(これを x とします)、そして、a の取り得る値の数は、前回と同様、n ÷ b'(これを y とします)なので、その2つの積( x × y )を求めればいいわけです。

さて、このように、n 以下で、一の位が 1, 3, 7, 9 の自然数全てで上記の計算をやれば答えは求めることができますが、個別に計算していたらやはり時間がかかります。そこで、上記の x が同じ値になるものを纏め、またその中で、y に関しても商によって個別で計算する部分と、同じ商が並ぶ部分は纏めて計算することで高速化することにしました。まずは、Ruby のままで、この考え方でコードを作ってみました。実行くんで 1011 が 0.9s でした。(ただし、バージョンアップ後は 0.67s に向上)

続きを読む "「アフター・ドット問題」の高度じゃないコード(高速編)"

| | コメント (0) | トラックバック (0)

「アフター・ドット問題」の高度じゃないコード(ゴルフ編)

「高度じゃないコード」シリーズその14は「アフター・ドット問題」です。今回の記事は、高速編がでかくなりそうなので、前編・後編と2回に分けますが、その前編(ゴルフ編)です。

自然数 n に対し、1 ≦ a ≦ n,1 ≦ b ≦ n を満たし、かつ小数で表した a÷b が有限小数となるような自然数の組 (a, b) の個数を F(n) と定義します。
(有限小数…小数点以下の桁数が有限である小数。)
標準入力から、自然数 n(1 ≦ n ≦ 104)が与えられます。
標準出力に F(n) の値を出力するプログラムを書いてください。

最初に、a ÷ b が有限小数となるための条件を考えます。どんな自然数でも、2 のべき乗と 5 のべき乗で割ると有限小数となるので、b を 2 と 5 で割れるだけ割ります。そして、a がその商 b' の倍数であれば有限小数になります。1 ≦ a ≦ n におけるその個数は、n ÷ b' の整数部ということになります。後は、1 ≦ b ≦ n の条件でループさせれば、F(n) を求めることができます。

今回は、ゴルフ解を作って一旦終了したように思えましたが、自然数 n(1 ≦ n ≦ 104)の制限を外し、どこまで大きな値まで計算できるかを競うことになり、非常に悩みましたがとても楽しませていただきました。

続きを読む "「アフター・ドット問題」の高度じゃないコード(ゴルフ編)"

| | コメント (0) | トラックバック (0)

« 2016年6月 | トップページ | 2016年8月 »