« Project Euler - Problem 43 : Pandigital 数を作ってしまえ | トップページ | Project Euler - Problem 4 再び »

2009年4月17日 (金)

Project Euler - Problem 1 再び

以前解いた問題も、時間が経ってから見直すと、また違った方法を考えつくことがあります。

というわけで、再び "Problem 1" です。

以前投稿したコードは次のようなものでした。

(define problem-001 (lambda (n) (printf "~d~%" (apply + (filter (lambda (n) (or (zero? (remainder n 3)) (zero? (remainder n 5)))) (iota n)))))) (problem-001 1000)

リストのデータを加工していくという点で、Scheme らしいかな?と思っています。

以前、考えていたもう一つのコードは反復的プロセスを使うパターンでした。

(define problem-001 (lambda (n-max) (let loop ([i 1] [sum 0]) (cond ([= i n-max] (printf "~d~%" sum)) ([or (zero? (remainder i 3)) (zero? (remainder i 5))] (loop (+ i 1) (+ sum i))) (else (loop (+ i 1) sum)))))) (problem-001 1000)

これは手続き言語っぽいやり方ですね。


今回紹介するアルゴリズムは、Ruby でコードを書いていたときに考えついたものです。

ということで、まずは元になった Ruby のコードから……

MAX = 999 a = Array.new(MAX + 1, 0) step = [3, 5] 2.times do |i| 0.step(MAX, step[i]) do |j| a[j] = j end end puts(a.reduce(:+))

自作の「エラトステネスの篩」の応用で、割り算を使わないので結構速いです。

これを Scheme で書くと……

(define problem-001 (lambda (n-max) (define vct (make-vector n-max 0)) (define value-set! (lambda (step) (do ([i 0 (+ i step)]) ([>= i n-max]) (vector-set! vct i i)))) (for-each value-set! '(3 5)) (printf "~d~%" (apply + (vector->list vct))))) (problem-001 1000)

Scheme で代入の "vector-set!" を使うのはあまり好きではないのですが、こういうやり方もあるんだなぁ……ということで。

« Project Euler - Problem 43 : Pandigital 数を作ってしまえ | トップページ | Project Euler - Problem 4 再び »

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

Scheme」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

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

トラックバック

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

この記事へのトラックバック一覧です: Project Euler - Problem 1 再び:

« Project Euler - Problem 43 : Pandigital 数を作ってしまえ | トップページ | Project Euler - Problem 4 再び »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ