« 自作の手続き for Project Euler | トップページ | Project Euler - Problem 2 : 再帰的アルゴリズムと反復的アルゴリズム »

2009年11月 1日 (日)

Project Euler - Problem 1 : 今度は Scheme で……

問題はこちらをご覧ください。


この問題はいろいろな解き方があります。

例えば繰り返しを使って和を求めるもの。

Scheme では繰り返しは再帰を使って表現するのですが、それにもいくつか方法があります。

(なお、以下の手続きはすべて、「n 未満の和」を求めるものです。(problem-001-1 1000) といった具合に、引数に "1000" を与えるとこの問題の答えが出ます。また、自作の手続きについてはこちらをご覧ください)

内部定義を使うもの。

;; 内部定義を使って繰り返し(末尾再帰) (define problem-001-1 (lambda (n) (define iter (lambda (m sum) (cond ([>= m n] sum) ([or (zero? (remainder m 3)) (zero? (remainder m 5))] (iter (+ m 1) (+ sum m))) (else (iter (+ m 1) sum))))) (iter 1 0)))

"retlec" や "named let" を使っても同じことができます。

;; letrec を使って繰り返し (define problem-001-2 (lambda (n) (letrec ([iter (lambda (m sum) (cond ([>= m n] sum) ([or (zero? (remainder m 3)) (zero? (remainder m 5))] (iter (+ m 1) (+ sum m))) (else (iter (+ m 1) sum))))]) (iter 1 0))))

;; named let を使って繰り返し (define problem-001-3 (lambda (n) (let iter ([m 1] [sum 0]) (cond ([>= m n] sum) ([or (zero? (remainder m 3)) (zero? (remainder m 5))] (iter (+ m 1) (+ sum m))) (else (iter (+ m 1) sum))))))

条件に合うリストを作っておいて、それを加工していく方法もあります。

;;; list を加工して計算する 1 (define problem-001-5 (lambda (n) (apply + (filter (lambda (x) (or (zero? (remainder x 3)) (zero? (remainder x 5)))) (seq 1 (- n 1))))))

これは 1 から n までの数を並べたリストから条件に合う数だけを抜き出して、足していく手続きです。("seq" は等差数列を作る自作の手続きです)


;;; list を加工して計算する 2 (define problem-001-6 (lambda (n) (let ([lst1 (seq 0 (- n 1) 3)] ; 3 の倍数のリスト [lst2 (seq 0 (- n 1) 5)]) ; 5 の倍数のリスト (apply + (unique (append lst1 lst2))))))

これは予め「3 の倍数のリスト」と「5 の倍数のリスト」を連結して、重複したものを取り除いたうえで和を求めています。("unique" はリストの要素から重複したものを取り除く自作の手続きです)


ちなみに、こんな解き方もあります。

(define problem-001-7 (lambda (n) (let* ([m (- n 1)] [sum1 (apply + (seq 0 m 3))] ; 3 の倍数の和 [sum2 (apply + (seq 0 m 5))] ; 5 の倍数の和 [sum3 (apply + (seq 0 m 15))]) ; 15 の倍数の和 (- (+ sum1 sum2) sum3))))

一つの問題でもアプローチの仕方やコードの書き方にはいろいろな方法があります。解き方のバリエーションを考えるのもなかなか面白いものです。

« 自作の手続き for Project Euler | トップページ | Project Euler - Problem 2 : 再帰的アルゴリズムと反復的アルゴリズム »

Project Euler」カテゴリの記事

Scheme」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

この記事へのトラックバック一覧です: Project Euler - Problem 1 : 今度は Scheme で……:

« 自作の手続き for Project Euler | トップページ | Project Euler - Problem 2 : 再帰的アルゴリズムと反復的アルゴリズム »

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            
フォト

最近のトラックバック

無料ブログはココログ