SICP 2.40 2.41 2.42 2.43

原创
2016/08/17 23:08
阅读数 154

2.40

(define (unique-pairs n)
  (flatmap (lambda (i)
             (map (lambda (j) (list i j))
                  (enumerate-interval 1 (- i 1))))
           (enumerate-interval 1 n)))

2.41

(define (gentuple n s)
  (filter (lambda (x)
            (= (accumulate + 0 x) s))
          (flatmap (lambda (i)
                     (flatmap (lambda (j)
                                (map (lambda (k)
                                       (list i j k))
                                     (enumerate-interval 1 (- j 1))))
                              (enumerate-interval 1 (- i 1))))
                   (enumerate-interval 1 n))))

2.42

行号列号从1开始。从右向左逐步构造棋盘

(define empty-board '())

(define (adjoin-position new-row k rest-of-queens)
  (cons new-row rest-of-queens))

(define (safe? k positions)
  (define (iter ex-row ex1 ex2 lst)
    (if (null? lst)
        #t
        (if (or (= ex-row (car lst))
                (= ex1 (car lst))
                (= ex2 (car lst)))
            #f
            (iter ex-row (- ex1 1) (+ ex2 1) (cdr lst)))))
  (let ((c (car positions)))
    (iter c (- c 1) (+ c 1) (cdr positions))))

2.43

对于2.42中的程序,当board-size为n时,queens-cols调用1+n次;

对于Louis的程序:当k=1时,queens-cols会调用board-size次;当k=2时,queens-cols会调用board-size乘以当k=1时的次数;归纳得,queens-cols会调用board-size的board-size次方次。

于是Louis的程序的运行时间大约为2.42程序的board-size的board-size -1次方倍,

即:(* (expt board-size (- board-size 1)) T)

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部