追記
丸3年放置していましたが、2013/08/07辺りから再開しました。
shunsuk さんの勧めで、取りあえず1問やってみました。こういう場合、勧めなのか薦めなのか。。
以下コード。
いつものことですが、名前付けがどうもしっくりこないです。かと言って英語の勉強まで手を広げる気にもなれません。
Project Euler は数学色が強いと聞いていたので敬遠していましたが、取りあえず躓くまでやってみようと思います。
L-99 の方も滞っています。
そうえば Chrome がバージョンアップして Ctrl+b でブックマークバーが出なくなって戸惑いました。Ctrl+Shift+b になったんですね。
「等差数列の和」の公式が使えます。
返信削除Wikipedia 等が参考になります。
http://ja.wikipedia.org/wiki/%E7%AD%89%E5%B7%AE%E6%95%B0%E5%88%97
3 の等差数列の和と 5 の等差数列の和を足すと、 3 の倍数であり 5 の倍数でもあるような数値 (即ち 15 の倍数) は重複してカウントしてしまうのでその分を最後に引くと答えが出ます。
Scheme で書くならこんな感じです。
(define (arithmetic-series x lim)
(let* ((m (quotient lim x))
(n (* m x)))
(/ (* (+ n x) m) 2)))
(-
(+
(arithmetic-series 3 1000)
(arithmetic-series 5 1000)
)
(arithmetic-series 15 1000))
「等差数列の和」は数学的な話ではありますが、それほど高等なものではないです。
例として、 20 以下の 3 の等差数列を考えてみましょう。
[3， 6， 9，12，15，18]
この数列の最初の 3 と最後の 18 を足すと 21 となります。
同様に、 6 と 15 を足したものも 21 となりますね。
即ち、 21 が 3 個あることになりますので、その合計値は 21×3=63 です。
この考え方を公式にしたものが上述のものということになります。
これだと計算量は O(1) です。
単純にループした場合は O(n) なので、大幅な効率化が出来たことになります。
序盤の問題はだいたい紙とペンがあれば解けます。
このあたりの考え方はたぶん高校あたりでやってるはず (私は高専卒なので普通の高校で扱う範囲を知らないのですが、等差数列の和は常識ですよね…？) の簡単なことなので、それがこの問題に当て嵌められるという最初の着想に至るかどうかで差がでるんじゃないかと思ってます。
もちろん、数学でなくプログラミングの練習の題材として使うのもアリだと思いますが、それだと相当最初の方で躓いてしまうと思うので…。
ありがとうございます！
返信削除いやー、お恥ずかしいです。。実は私、算数の時点で躓いたタイプでして・・・orz
私の場合、プロジェクトオイラーは自分で考えるより、他の方のソースを読んだ方が良いかもしれませんね＾＾；
だいぶ前に書かれた記事に対してコメントで恐縮です。
返信削除プロジェクトオイラー、すっごく面白いです。はまりますね。
最初はあんまり難しく考えることはないですよ。数学を使わないで強引に解いてもいいと思います。いずれそのやり方では解けない問題に遭遇しますから、そこでアレコレ調べてみるとあちらこちらに使えそうな数学があることがわかります。
そうやってその数学を発見すると喜びも倍増します。
初等整数論からかなり出題されているみたいですよ。
いえいえ！コメントありがとうございます！
返信削除数学が苦手なので、続けようかなぁどうしようかなぁと思っていました。実際に躓くまでやってみるのも良いかもしれませんね！
いいっすね～。数学、楽しみましょう。数学を楽しむことがプロジェクトの狙いでしょうし、数学者オイラーも草場の陰で喜んでいると思いますよ。
返信削除そうですよね！何より楽しめれば、それが良いですね！
返信削除最近、遠山啓さんの「数学入門」を読んで、もしかしたら楽しいのかもしれない、と思うようにはなりました（笑）
プロジェクトオイラーも良い機会かもしれませんね。