Problem 5

Scheme

ぬはぁ解けたぁ！！すげー嬉しい。

Problem 5 - PukiWiki

2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり、そのような数字の中では最小の値である。

では、1 から 20 までの整数全てで割り切れる数字の中で最小の値はいくらになるか。

ちょっと考えた。


方針はこう。

  • 1から10までのリストを用意する。
    • (1 2 3 4 5 6 7 8 9 10)
  • 頭か順に見ていく。割り切れたら割る。
    • (1),(2 3 4 5 6 7 8 9 10) - 1で割る
    • (1 2),(3 2 5 3 7 4 9 5) - 2で割る
    • (1 2 3),(2 5 1 7 4 3 5) - 3で割る
    • (1 2 3 2),(5 1 7 2 3 5) - 2で割る
    • 繰り返す。
  • (1 2 3 2 5 1 7 2 3 1)というリスト(実際には逆順だけど)が出来上がるので、全部掛けると、2520


コーディング。

(define (problem5 n)
  (define (iter acc l)
    (if (null? l)
        acc
        (iter (cons (car l) acc)
              (map (lambda (x)
                     (if (zero? (modulo x (car l)))
                         (/ x (car l))
                         x))
                   (cdr l)))))
  (fold * 1 (iter '() (iota n 1))))


(problem5 10) ; 2520
(problem5 20) ; 232792560

うれしい。


ちょっと修正版。

(define (problem5 n)
  (define (iter acc l)
    (if (null? l)
        acc
        (iter (* (car l) acc)
              (map (lambda (x)
                     (if (zero? (modulo x (car l)))
                         (/ x (car l))
                         x))
                   (cdr l)))))
  (iter 1 (iota n 1)))

アキュムレータはリストじゃなくてもいいね。拡張foldが欲しくなるな。