Serendip

Web Studio

2.2.3 写像の入れ子

正の整数 n があり、1<=j<i<=n である異なる正の整数 i と j の順序対で、i+j が素数になるものをすべて見つける。

n = 6 の場合

i<=n の各整数に、整数 j<i を数え上げる。

(map (lambda (i) (enumerate-interval 1 (- i 1)))
     (enumerate-interval 1 6))
gosh> (() (1) (1 2) (1 2 3) (1 2 3 4) (1 2 3 4 5))

i と j に対 (i, j) を生成する。

(map (lambda (i)
             (map (lambda (j) (list i j))
                  (enumerate-interval 1 (- i 1))))
     (enumerate-interval 1 6))
gosh> (() ((2 1)) ((3 1) (3 2)) ((4 1) (4 2) (4 3)) ((5 1) (5 2) (5 3) (5 4)) ((6 1) (6 2) (6 3) (6 4) (6 5)))

全ての i についての並びを組み合わせる（append でアキュムレートする）。

(accumulate append
            ()
            (map (lambda (i)
                         (map (lambda (j) (list i j))
                              (enumerate-interval 1 (- i 1))))
                 (enumerate-interval 1 6)))
gosh> ((2 1) (3 1) (3 2) (4 1) (4 2) (4 3) (5 1) (5 2) (5 3) (5 4) (6 1) (6 2) (6 3) (6 4) (6 5))

対の値の和が素数であるものを見つける。

(filter prime-sum? '((2 1) (3 1) (3 2) (4 1) (4 2) (4 3) (5 1) (5 2) (5 3) (5 4) (6 1) (6 2) (6 3) (6 4) (6 5)))
gosh> ((2 1) (3 2) (4 1) (4 3) (5 2) (6 1) (6 5))

フィルタされた対を、対の二つの要素とその和からなる三つ組みからなる並びを生成する。

(map make-pair-sum '((2 1) (3 2) (4 1) (4 3) (5 2) (6 1) (6 5)))
gosh> ((2 1 3) (3 2 5) (4 1 5) (4 3 7) (5 2 7) (6 1 7) (6 5 11))

(define (flatmap proc seq)
  (accumulate append () (map proc seq)))

(define (prime-sum? pair)
  (prime? (+ (car pair) (cadr pair))))

(define (make-pair-sum pair)
  (list (car pair) (cadr pair) (+ (car pair) (cadr pair))))

(define (prime-sum-pairs n)
  (map make-pair-sum
       (filter prime-sum?
               (flatmap
                 (lambda (i)
                         (map (lambda (j) (list i j))
                              (enumerate-interval 1 (- i 1))))
                 (enumerate-interval 1 n)))))

(prime-sum-pairs 6)
gosh> ((2 1 3) (3 2 5) (4 1 5) (4 3 7) (5 2 7) (6 1 7) (6 5 11))

計算機プログラムの構造と解釈

posted with amazlet at 08.11.07

ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542

Amazon.co.jp で詳細を見る