Google Code Jam 2009開催
Googleブログ（Google Japan Blog: Google Code Jam 2009 を開催します）
でお知らせされているように、Google Code Jam 2009が開催されるようです。上記ページ
に、昨年出題された難易度高の問題が掲載されています。ここに転記すると、
(3 + √5)を 1,000,000,000 乗した結果の、整数部分の下 3 桁はどうなるでしょうか?
恐らく、通常のC/C++やJavaを使って解いたとしてもルート5のような無限小数を
1,000,000,000乗することになるので、例え下3桁のmodを取ったとしても普通の
やりかたでは計算誤差が大きくなり、正しい答えは得られないでしょう。
無限小数展開？
ルート5の値を平方根の展開アルゴリズムを使い、十分な長さの桁まで求めた上で
その値を利用して計算することも可能です。しかしこれは、十分な長さの桁が
かなり長くなってしまい、1,000,000,000回もそれを掛け算するというのは現実的じゃ
ないような気がします。
数学的に問題を緩和して計算機を利用する
これが正攻法でしょう。(a+b)^x = ∑[r=0 to x] xCr a^r b^(x-r) で知られている
公式を用い、さらに、3^100 = 3^0 mod 1000, 5^5 = 5^3 mod 1000といった関係式
から、問題をどんどん緩和していくことが可能でしょう。これらの緩和をどんどん
行っていけば、無限小数の掛け算を行う必要がなくなるはずなので、計算誤差も
ほとんど起こらなくなるでしょう。
申し込み
Google Code Jam 2009へのエントリーは
Google Code Jam 2009
のページから行うことができます。興味のある方はぜひエントリーを。
まとめ
おそらく、合同式の関係式を使い、問題を緩和していく方法がベストだと思うの
ですが、実際のところはどうなんでしょうか？実際にやってみた人はどうやったのか
教えてほしいですね。
参考サイト・関連書籍
プログラミング作法 |
|
 |
Brian Kernighan
おすすめ平均 |
入門書の次の次の次くらいに！
繰り返し読む必要あり関連記事
- CentOSでGo（インストール編）
- Androidアプリ開発に関する本の紹介
- GoogleのCAPTCHAを破る新ワームが現る
- Googleサイトの使い勝手 [第1回]
- [Web] Google Web Master Tool 新機能？
[PR]
トラックバック
http://yamablo.com/2009/08/17-171307.php/trackback
![t ]E](http://www.affiliate-b.com/upload_image/984-1198556658-3.gif)
8月 17th, 2009 at 6:31 PM
[...] yamablo » Blog Archive » Google Code Jam 2009開催 [...]