Hatena::Groupcsnagoya-sicp

クラなんとかの日記 このページをアンテナに追加 RSSフィード

 | 

2009-07-05このニコタマが好きだから

2.41

| 2.41 - クラなんとかの日記 を含むブックマーク はてなブックマーク - 2.41 - クラなんとかの日記 2.41 - クラなんとかの日記 のブックマークコメント

n に対し 0 < i < j < k <= n という三つの数字の組のうち,

合計が s になるものをみつけたい.

問題文では,i, j, k の大小について記述されていないが,

順序が無い場合は回答重複するだけなので,省いてもよい.

まいどおなじみの accumurate の中で再帰しています.

再帰は,size を減らしていって,accumurate のループは,

決まった数値より後ろの部分で回ります.

#!/usr/bin/env gosh
;; -*- coding: utf-8; -*-
; 

;; 準備
(define nil (list))

;; 2.2.3 より (日本語版 p.66)
(define (filter predicate sequence)
  (cond ((null? sequence) nil)
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

;; 2.2.3 より (日本語版 p.67)
(define (enumerate-interval low high)
  (if (> low high)
      nil
      (cons low (enumerate-interval (+ low 1) high))))

;; 問題文より

;; 答え
(define (make-unique-tupple size max)
  (define (iter size n)
    (if (= size 0)
        (list nil)
        (accumulate append nil
                    (map (lambda (i)
                           (map (lambda (l)
                                  (cons i l))
                                (iter (- size 1) (+ i 1))))
                         (enumerate-interval n max)))))
  (iter size 1))

(define (find-parted-3-numbers n s)
  (filter (lambda (triple)
            (= s (+ (car triple)
                    (cadr triple)
                    (caddr triple))))
          (make-unique-tupple 3 n)))

;; 確認
(define n 10)
(define s 15)

(format #t "n = ~d" n) (newline) ; 10
(format #t "s = ~d" s) (newline) ; 15
(display (find-parted-3-numbers n s)) (newline) ; ((1 4 10) (1 5 9) (1 6 8) (2 3 10) (2 4 9) (2 5 8) (2 6 7) (3 4 8) (3 5 7) (4 5 6))
 |