« 「アフター・ドット問題」の高度じゃないコード(高速編) | トップページ | 「プライム・ホッパー問題」の高度じゃないコード »

2016年7月20日 (水)

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

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

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

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

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

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

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

言語には、数字の上位6桁・有効数字分の桁を取り出すのが最も簡単だということで Ruby を選んで作ったのが次のコードです。

一応、有効桁数は60桁とかなり多めにしてみましたが、試してみると、この問題では11桁では誤答となりましたが、12桁以上あれば正解が出ました。意外と少なくても大丈夫なんですね。

|

« 「アフター・ドット問題」の高度じゃないコード(高速編) | トップページ | 「プライム・ホッパー問題」の高度じゃないコード »

コメント

類題を作ってみました。

整数nに対し、nの階乗(n!)の上6桁をF1(n)と定義します。
また、最下位の連続する0を除外して残った下6桁をF2(n)と定義します。
例えば、F1(12)=479001、F2(12)=790016です。(12!=479001600)

F1(n)とF2(n)が等しくなる最小のnを求めてください。

ただし、F1(n)とF2(n)が同じ部分を参照する場合は、当然同じ値になるので除外します。
例えば、F1(11)=F2(11)=399168ですが、11!=39916800で同じ部分を参照しているので対象外です。

投稿: Yasu.Hara. | 2016年7月20日 (水) 15時16分

類題その2です。

整数nに対し、nの階乗(n!)の上5桁をF1(n)と定義します。
また、最下位の連続する0を除外して残った下5桁を逆向きに数字を入れ替えた値をF2(n)と定義します。
例えば、F1(11)=39916、F2(11)=86199です。(11!=39916800)

F1(n)とF2(n)が等しくなる最小のnを求めてください。

投稿: Yasu.Hara. | 2016年7月20日 (水) 15時34分

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/99795/63941263

この記事へのトラックバック一覧です: 「階乗フィーバー数問題」の高度じゃないコード:

« 「アフター・ドット問題」の高度じゃないコード(高速編) | トップページ | 「プライム・ホッパー問題」の高度じゃないコード »