翼若垂天之云 » 我读·我听·我思·我行

这个寒假读的书及其它

今天，我回到了浙大，我把这算成寒假的结束。上个学期最后一门考试的前一天拿到了一台 Kindle DX，于是这个假期的所有书都是在这台 Kindle 上读的，大致按照读完的顺序如下：

周国平《尼采：在世纪的转折点上》
The Power of Less (Leo Babarta)
陈冠中《盛世》
《中国健康调查报告》
Outliers (Malcolm Gladwell)
Programming in Scala
A Rulebook for Arguments (Anthony Weston)
罗素《西方哲学史》卷一

四本中文书，四本英文书。有小说，有编程，有成功学，有哲学史，有健康指南，有批判思维。虽然数量不算多，不过我相信这是一段富有平衡性、充满营养的阅读体验。这些书读的时候多少都做了一些摘抄、提纲和感悟之类的文字，在此就对每本书做个简短的的读后总结吧。

周国平的《尼采》一书是在ASES读书会中了解到的。我喜欢周国平写的尼采，类似于我欣赏钱穆书中的孔子。钱穆以儒家信徒乃至道统传人的信念写《论语新解》，自然将论语的妙处诠释得淋漓尽致，读者也最能从中受益。（插一句广告，我一直坚定地认为钱穆《论语新解》是用来了解论语以及儒学的最好的入门读物，在此郑重推荐。）我无旁据地揣测，写此书时的周国平必自认为尼采的信徒（虽然不一定会公开承认这一点），而这个角度的介绍，是追求他山之石而非价值判断的我所乐于阅读的。

Leo Babarta 是我订阅了一段时间的英文 blogger，于是它的书 The Power of Less 的英文电子版躺在我硬盘里好久了。真正在 Kindle Store 里买了并从头到尾阅读一遍才如梦初醒，书中完全点明了我拖了那么长时间没抽出空来读它的症结。我非常庆幸能在寒假的开始以及一年的开始时读到这本书，其中的精神整个改变了我的寒假计划，我想也会改变我接下来一年的安排。这本书好像也刚出了中文版，强烈推荐给每个像我一样对“more”有着不懈追求的人。

《盛世》这本书我看的是 Twitter 上分享的陈冠中先生亲自校对和分享的盗版PDF。依我的理解，它从纯粹文学的角度看不算是第一流的小说艺术。对其思想性不评价，主要是因为觉得自己没那个能耐去评价吧。

会去看《中国健康调查报告》这本书是因为有践行书中建议的素食饮食习惯的朋友的推荐。读之前特意在 Google Scholar 里输入了作者的名字，发现确实是个学术大牛，才放心地读了下去。我承认书里的论据和结论都是非常有说服力的。这促使我在过年前的某一天中午对抢我的Kindle看了这书的一部分的我妈说，今天中午吃一顿素食吧。这顿素食带来的后果是我在几个小时之后窜到厨房里对正在准备晚餐的我妈大声喊：“我要吃肉！我要吃肉！”于是这本差不多是素食主义者的圣经的书遇上我这个打小无肉不欢的家伙就完全没起任何作用。嗯……应该说这本书还是带来了一些让我在四十岁或者更老的时候转向素食主义的可能性，至于现在就算了吧……

Malcolm Gladwell 写的 Outliers 一书的副标题是 The Story of Success，最初是在李笑来老师的blog上听说此书的。这本书论证讲述了现实世界中的事业成功被哪些因素左右，并得出了一些有悖于常识却又有说服力的结论。中文译本的书名是叫《异类》，推荐给每个希望了解并达到事业成功的人。

假期里读的唯一一本跟我自己的专业直接相关的书是 Programming in Scala，是因为最近要用到而读的。作为一本编程语言的入门书，它是中规中矩的。至于 Scala 语言本身，我本来想好好写一段技术评论，不过眼界和经验所限，还是不写出来误导人了吧。总之，我的结论是，Scala 绝对大有可为。

会在 Kindle Store 上买了 A Rulebook for Arguments 这本书来读，最初的动力是打算在了解和学习 critical thinking 这个领域内的知识。至于为什么在卷帙浩繁中选了这本作为开始，我也记不清楚了……不过读完了以后意识到这个选择真是如此幸运啊。讲得深入浅出精炼透彻不说，书最后的 Resources 一节全面的介绍了这个领域的各个方面以及相关推荐书目。非常感激作者的用心。这本书我打五颗星。

罗素《西方哲学史》我从假期的一开始就着手读了，一直作为我读英文书编程书之类读累了的调剂，读得断断续续，直到在回杭州的火车上才最终读完题为“古代哲学”的第一卷，主要内容是古希腊哲学。我这种消遣的读法实在没记住什么东西，只是觉得古希腊的文化真是光辉灿烂，那种感觉跟我高中和大一时泛读诸子差不多，就是发现了一座宝藏。接下来还有“天主教哲学”和“近代哲学”两卷要读，我的计划是还这样泛读过去，然后根据兴趣和需要再选一些章节来精读吧。

写到最后想起来，还读了一本叫 Know Can Do! （中文译本《知道做到》）的英文小书。我的鉴定是这是本在书店里翻翻目录及每章的最后一页即可放下的书。算上或者不算上它对我寒假读书的价值几无影响。

然后列下我正在看还没看完的书单：

罗素《西方哲学史》还差两卷要看。
The Elements of Style (Fourth Edition) 刚刚开始看。这本英语写作方面的绝对经典当然是不能错过的。希望它也能在 critical thinking 的领域有所助益。
The Definitive Guide to Lift 是手头的项目所需要尽快看完的。
The Now Habit (Neil A. Fiore) 是讲拖延症的权威著作。以前读过一次，读到一半就由为书中所载的顽疾本身所累半途而废了。现在重新拿起细读，但进展不快，需要加油。

我下一步要读的书目包括：

Authentic Happiness (Martin Seligman)，积极心理学的代表作。我高中的时候读过弗洛伊德在精神分析上的一些代表作，深以为然，以其信徒自居。直到最近才警醒过来，且不论弗洛伊德学说本身的价值，把他的学说当成一种精神指南来信奉绝对是害大于益的。于是我打算阅读对个人发展更有建设性作用的积极心理学方面的著作，有必要的话还会读一本《弗洛伊德批判》来解毒。

Programming Pearls，打算读但一直没读过的经典编程书籍。

Being Logical: A Guide to Good Thinking (Joseph M. Williams)，思维领域的下一本书。

What Is Mathematics?: An Elementary Approach to Ideas and Method，高中时读过的数学科普书。打算重读一遍，一方面是试图重试对数学的兴趣，另外也完全有理由相信现在可以从本书中汲取更多的内容。

Pragmatic Thinking and Learning: Refactor Your Wetware 一书的作者 Andy Hunt 曾以 Pragmatic Programmer 一书深深地影响了高中时期的我。我希望这本书能开启我了解和学习脑科学、认知科学的门径。

Armchair Economist (Steven E. Landsburg)，选择读的第一本通俗经济学读物。

The 7 Habits of Highly Effective People (Stephen R. Covey) 是久闻盛名的经典，下一步打算读。

上面的书单竟全部都是英文书啊。中文书的话，现在唯一确定下一步要看的是钱穆《国史大纲》，等到把大部头《西方哲学史》啃完就开始吧。

除此之外，我还有一个包含23本书的 to-read 列表，一个包含31本书的 sometimes/maybe 书单，而且它们的容量还一直在快速增加……于是深刻体会到“吾生也有涯，而知也无涯”，几要发出“以有涯随无涯，殆已”的悲鸣。可我仍愿尝试“求知若渴，虚心若愚(Stay Hungry, Stay Foolish)”，初生牛犊般无畏地前行。

Comments (7)

February 23, 2010 · Filed under 生活志

SICP习题解答：第二章（上）

^?View Code SCHEME

;; 2.1
(define (make-rat n d)
  (if (< d 0)
      (make-rat (- n) (- d))
      (cons n d)))
 
;; 2.2
(define (make-point x y)
  (cons x y))
(define (x-point p)
  (car p))
(define (y-point p)
  (cdr p))
(define (make-segment start end)
  (cons start end))
(define (start-segment s)
  (car s))
(define (end-segment s)
  (cdr s))
(define (midpoint-segment s)
  (let ((a (start-segment s))
        (b (end-segment s)))
    (make-point (/ (+ (x-point a) (x-point b)) 2)
                (/ (+ (y-point a) (y-point b)) 2))))
 
;; 2.3
 
; 第一种表示
(define (make-rect mid-point width height)
  (cons mid-point
        (cons (/ width 2) (/ height 2))))
(define (rect-left r)
  (- (x-point (car r)) (car (cdr r))))
(define (rect-right r)
  (+ (x-point (car r)) (car (cdr r))))
(define (rect-bottom r)
  (- (y-point (car r)) (cdr (cdr r))))
(define (rect-top r)
  (+ (y-point (car r)) (cdr (cdr r))))
 
; 第二种表示
(define (make-rect bottom-left top-right)
  (cons bottom-left top-right))
(define (rect-left r)
  (x-point (car r)))
(define (rect-right r)
  (x-point (cdr r)))
(define (rect-bottom r)
  (y-point (car r)))
(define (rect-top r)
  (y-point (cdr r)))
 
; 公用函数
(define (rect-width r)
  (- (rect-right r) (rect-left r)))
(define (rect-height r)
  (- (rect-top r) (rect-bottom r)))
(define (rect-area r)
  (* (rect-width r) (rect-height r)))
(define (rect-perimeter r)
  (* 2 (+ (rect-width r) (rect-height r))))
 
;; 2.4
(define (my-cons x y)
  (lambda (m) (m x y)))
(define (my-car z)
  (z (lambda (p q) p)))
(define (my-cdr z)
  (z (lambda (p q) q)))
 
;; 2.5
(define (cons-n x y) ; x and y are natural numbers
  (if (= x 0)
      (if (= y 0) 1
          (* 3 (cons x (- y 1))))
      (* 2 (cons (- x 1) y))))
(define (car-n z)
  (if (= 0 (remainder z 2))
      (+ 1 (car (/ z 2)))
      0))
(define (cdr-n z)
  (if (= 0 (remainder z 3))
      (+ 1 (cdr (/ z 3)))
      0))
 
;; 2.6 目前最激动人心的题目
(define zero
  (lambda (f) (lambda (x) x)))
(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))
(define one
  (lambda (f) (lambda (x) (f x))))
(define two
  (lambda (f) (lambda (x) (f (f x)))))
(define (add m n)
  (lambda (f) (lambda (x) ((m f) ((n f) x)))))
 
;; 2.7 为什么这么重复的题目啊
(define (make-interval a b) (cons a b))
(define (lower-bound x) (car x))
(define (upper-bound x) (cdr x))
 
;; 2.8
(define (sub-interval x y)
  (make-interval (- (lower-bound x) (upper-bound y))
                 (- (upper-bound x) (lower-bound y))))
 
;; 2.9 对于加法，结果的上（下）界即两上（下）界之和，故宽度就是两宽度之和，即(a-b)+(c-d)=(a-c)-(b-d)。减法有相同的结论。对于乘法，(a-b)*(c-d)!=(ac-bd)；例如宽度相同的(0,1)、(1,2)、(2,3)两两做乘法运算得到(0,2)、(0,3)、(2,6)三个宽度不同的区间。除法类似。
 
;; 2.10
(define (div-interval x y)
  (if (and (< (lower-bound y) 0) (< 0 (upper-bound)))
      (error "Divide by a interval that contains zero -- div-interval")
      (mul-interval x
                    (make-interval (/ 1 (upper-bound y))
                                   (/ 1 (lower-bound y))))))
 
;; 2.11 其实归结起来只有三种情况：0、1或2个区间包括0。
(define (print-interval i)
  (display "[")
  (display (lower-bound i))
  (display ",")
  (display (upper-bound i))
  (display "]\n"))
(define (neg-interval i)
  (make-interval (- (lower-bound i)) (- (upper-bound i))))
(define (mul-interval x y)
  (define (do-it a b c d)
    (cond ((< b 0) (neg-interval(do-it (- b) (- a) c d)))
          ((< d 0) (neg-interval(do-it a b (- d) (- c))))
          ((and (> a 0) (< c 0)) (do-it c d a b))
          ((and (< a 0) (> c 0)) (make-interval (* a d) (* b d)))
          ((and (< a 0) (< c 0)) (make-interval 0 (max (* a c) (* b d))))
          ((and (> a 0) (> c 0)) (make-interval (* a c) (* b d))))
    )
  (let ((a (lower-bound x))
        (b (upper-bound x))
        (c (lower-bound y))
        (d (upper-bound y)))
    (do-it a b c d)))
;;;
(define (mul-interval-test-cases)
  (print-interval (mul-interval (make-interval 2 3) (make-interval 4 5)))
  (print-interval (mul-interval (make-interval 2 3) (make-interval -4 5)))
  (print-interval (mul-interval (make-interval 2 3) (make-interval -5 -4)))
  (print-interval (mul-interval (make-interval -2 3) (make-interval 4 5)))
  (print-interval (mul-interval (make-interval -2 3) (make-interval -4 5)))
  (print-interval (mul-interval (make-interval -2 3) (make-interval -5 -4)))
  (print-interval (mul-interval (make-interval -3 -2) (make-interval 4 5)))
  (print-interval (mul-interval (make-interval -3 -2) (make-interval -4 5)))
  (print-interval (mul-interval (make-interval -3 -2) (make-interval -5 -4))))
 
;; 2.12
(define (make-center-percent center percent)
  (define delta (/ (* center percent) 100))
  (make-interval (- center percent) (+ center percent)))
(define (center i)
  (/ (+ (lower-bound i) (upper-bound i)) 2))
(define (percent i)
  (abs (* 50 (/ (- (upper-bound i) (lower-bound i)) (center i)))))
(define (print-center-percent i)
  (display (center i))
  (display "±")
  (display (percent i))
  (newline)
  )
 
;; 2.13 a(1+b%)*c(1+d%)=ac(1+b%+d%+b%d%)~=ac(1+b%+d%)
 
;; 2.14 程序将 (div-interval A A) 与 (div-interval A B) 做相同的处理，而没有意识到前者的两个参数并非是独立的。也即，当同一个变量在式子中多次出现时，程序不能意识到它的每次出现必须取相同的值。
(define (check-interval-arithmetic)
  (let ((A (make-interval 2 3))
        (B (make-interval 2 3)))
    (print-interval (div-interval A A))
    (print-interval (div-interval A B))))
(define (check-interval-arithmetic-center-percent)
  (let ((A (make-center-percent 100.0 3))
        (B (make-center-percent 100.0 3)))
    (print-center-percent (div-interval A A))
    (print-center-percent (div-interval A B))))
 
;; 2.15 我认为这公式的两个形式是完全等价的，在Alyssa系统上产生的区间限界不同，是由于Alyssa系统的本质缺陷，而非两个形式的优劣。
 
;; 2.16 当同一个变量在式子中多次出现时，程序不能意识到它的每次出现必须取相同的值。每个变量出现的次数不同会导致Alyssa系统得出的结果不同。无缺陷的区间算术包等价于以下问题：多变量的多项式，每个变量有其取值范围，求多项式的值的取值范围。这个问题属于 Interval Computation 的范畴：http://www.lsi.upc.edu/~robert/mirror/interval-comp/
 
;; 2.17
(define (last-pair l)
  (cond ((null? (cdr l)) l)
        (else (last-pair (cdr l)))))
 
;; 2.18
(define (reverse l)
  (define (do-it a b)
    (if (null? a) b
        (do-it (cdr a) (cons (car a) b))))
  (do-it l nil))
 
;; 2.19
(define (cc amount coin-values)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (no-more? coin-values)) 0)
        (else
         (+ (cc amount
                (except-first-denomination coin-values))
            (cc (- amount
                   (first-denomination coin-values))
                coin-values)))))
(define (no-more? l) (null? l))
(define (except-first-denomination l) (cdr l))
(define (first-denomination l) (car l))
; 根据问题的定义，改变表中元素的顺序不会影响回答。
 
;; 2.20
(define (same-parity x . s)
  (define (iter a)
    (if (null? a) nil
        (let ((b (iter (cdr a))))
          (if (even? (- x (car a)))
              (cons (car a) b) b))))
  (cons x (iter s)))
 
;; 2.21
(define (square-list items)
  (if (null? items)
      nil
      (cons (square (car items)) (square-list (cdr items)))))
 
(define (square-list items)
  (map square items))
 
;; 2.22 第一个程序中，程序从前往后处理things中的元素，却每次把平方后的元素加到answer的头部，故结果的顺序会相反。第二个程序中，当cons的两个参数分别是list和元素时，结果并不是把元素加到list后面。
 
;; 2.23
(define (for-each f l)
  (cond ((not (null? l))
         (f (car l))
         (for-each f (cdr l)))))
 
;; 2.24 (1 (2 (3 4)))。
 
;; 2.25
(car (cdr (car (cdr (cdr '(1 3 (5 7) 9))))))
(car (car '((7))))
(car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr '(1 (2 (3 (4 (5 (6 7))))))))))))))))))
 
;; 2.26
; (1 2 3 4 5 6)
; ((1 2 3) 4 5 6)
; ((1 2 3) (4 5 6))
 
;; 2.27
(define (deep-reverse t)
  (if (list? t)
      (map deep-reverse (reverse t))
      l))
 
;; 2.28
(define (fringe t)
  (cond ((null? t) nil)
        ((list? t) (append (fringe (car t)) (fringe (cdr t))))
        (else (list t))))
 
;; 2.29
(define (make-mobile left right)
  (list left right))
(define (make-branch length structure)
  (list length structure))
 
; (a)
(define (left-branch mobile)
  (car mobile))
(define (right-branch mobile)
  (cadr mobile))
(define (branch-length branch)
  (car branch))
(define (branch-structure branch)
  (cadr branch))
 
; (b)
(define (total-weight x)
  (if (number? x)
      x
      (+ (total-weight (branch-structure (left-branch x))) (total-weight (branch-structure (right-branch x))))))
 
;  (c)
(define (branch-torque x) 
  (* (total-weight (branch-structure x)) 
     (branch-length x)))
 
(define (balanced? x)
  (cond ((number? x) true)
        (else
         (let ((left (left-branch x))
               (right (right-branch x)))
           (and (= (branch-torque left) (branch-torque right)) (balanced? (branch-structure left)) (balanced? (branch-structure right)))))))
 
; (d) 只需更改right-branch和branch-structure中的cadr为cdr
 
;; 2.30
; 直接定义
(define (square-tree t)
  (cond ((null? t) nil)
        ((number? t) (square t))
        (else (cons (square-tree (car t)) (square-tree (cdr t))))))
 
; 使用高阶函数
(define (square-tree t)
  (map (lambda (x)
         (if (list? x)
             (square-tree x)
             (square x)))
       t))
 
;; 2.31
(define (tree-map f t)
  (map (lambda (x)
         (if (list? x)
             (tree-map x)
             (f x)))
       t))
 
;; 2.32 将子集分为包含与不包含(car s)两种情况。
(define (subsets s)
  (if (null? s)
      (list nil)
      (let ((rest (subsets (cdr s))))
        (append rest (map (lambda (x) (cons (car s) x)) rest)))))
 
;; 2.33
(define (unary-map p sequence)
  (accumulate (lambda (x y) (cons (p x) y)) nil sequence))
(define (apppend seq1 seq2)
  (accumulate cons seq2 seq1))
(define (length sequence)
  (accumulate (lambda (x y) (+ 1 y)) 0 sequence))
 
;; 2.34
(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms) (+ this-coeff (* x higher-terms)))
              0
              coefficient-sequence))
 
;; 2.35
(define (count-leaves t)
  (accumulate (lambda (x y)
                (+
                 (if (list? x) (count-leaves x) 1)
                 y))
              0
              t))
; 或
(define (count-leaves t)
  (accumulate + 0 (map (lambda (x) (if (list? x) (count-leaves x) 1)) t)))
 
;; 2.36
(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      nil
      (cons (accumulate op init (map car seqs))
            (accumulate-n op init (map cdr seqs)))))
 
;; 2.37
(define (dot-product v w)
  (accumulate + 0 (map * v w)))
(define (matrix-*-vector m v)
  (map (lambda (x) (dot-product x v)) m))
(define (transpose mat)
  (accumulate-n cons nil mat))
(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map (lambda (x) (matrix-*-vector cols x)) m)))
 
;; 2.38
(define (fold-left op initial sequence)
  (define (iter result rest)
    (if (null? rest)
        result
        (iter (op result (car rest))
              (cdr rest))))
  (iter initial sequence))
(define fold-right accumulate)
; 3/2
; 1/6
; (1 (2 (3 ())))
; (((() 1) 2) 3)
; 结合律，以及inital是op的零元。
 
;; 2.39
(define (reverse sequence)
  (fold-right (lambda (x y) (append y (list x))) nil sequence))
(define (reverse sequence)
  (fold-left (lambda (x y) (cons y x)) nil sequence))
 
;; 2.40
(define (flatmap proc seq)
  (accumulate append nil (map proc seq)))
(define (unique-pairs n)
  (flatmap
   (lambda (i) 
     (map
      (lambda (x) (cons x i))
      (enumerate-interval 1 (- i 1))))
   (enumerate-interval 1 n)))
 
;; 2.41
(define (pair-sum-no-more-than n)
  (flatmap
   (lambda (x)
     (map (lambda (y) (cons y x))
          (enumerate-interval 1 (min (- x 1) (- n x)))))
   (enumerate-interval 1 (- n 1))))
(define (triple-sum-is n)
  (filter
   (lambda (x) (not (or (= (car x) (cadr x)) (= (car x) (caddr x)))))
   (map
    (lambda (x) (list (- n (car x) (cdr x)) (car x) (cdr x)))
    (pair-sum-no-more-than (- n 1)))))
 
;; 2.42
(define empty-board nil)
(define (safe? k p)
  (define (not-same p)
    (null? (filter (lambda (x) (= (car p) x)) (cdr p))))
  (and
   (not-same p)
   (not-same (map + p (enumerate-interval 1 k)))
   (not-same (map + p (reverse (enumerate-interval 1 k))))))
(define (adjoin-position n k r)(cons n r))
(define (queens board-size)
  (define (queen-cols k)
    (if (= k 0)
        (list empty-board)
        (filter
         (lambda (positions) (safe? k positions))
         (flatmap
          (lambda (rest-of-queens)
            (map (lambda (new-row)
                   (adjoin-position new-row k rest-of-queens))
                 (enumerate-interval 1 board-size)))
          (queen-cols (- k 1))))))
  (queen-cols board-size))
 
;; 2.43 原程序中每个 (queen-cols k) 只需调用一次，而这个程序中，为了计算 (queen-cols k)，需要调用 k 次 (queen-cols (- k 1))；大约需要k!T的时间。
 
;; 2.44
(define (up-split painter n)
  (if (= n 0)
      painter
      (let ((smaller (up-split painter (- n 1))))
        (below painter (beside smaller smaller)))))
 
;; 2.45
(define (split combo1 combo2)
  (lambda (painter n)
    (if (= n 0)
        painter
        (let ((smaller (up-split painter (- n 1))))
          (combo1 painter (combo2 smaller smaller))))))
 
;; 2.46
(define (make-vect x y)
  (cons x y))
(define (xcor-vect v)
  (car v))
(define (ycor-vect v)
  (cdr v))
(define (add-vect v w)
  (make-vect (+ (xcor-vect v) (xcor-vect w))
             (+ (ycor-vect v) (ycor-vect w))))
(define (sub-vect v w)
  (make-vect (- (xcor-vect v) (xcor-vect w))
             (- (ycor-vect v) (ycor-vect w))))
(define (scale-vect s v)
  (make-vect (* s (xcor-vect v))
             (* s (ycor-vect v))))
 
;; 2.47
(define (make-frame origin edge1 edge2)
  (list origin edge1 edge2))
(define (origin-frame frame)
  (car frame))
(define (edge1-frame frame)
  (cadr frame))
(define (edge2-frame frame)
  (caddr frame))
 
(define (make-frame origin edge1 edge2)
  (cons origin (cons edge1 edge2)))
(define (edge2-frame frame)
  (cddr frame))
 
;; 2.48
(define (make-segment v w)
  (cons v w))
(define (start-segment s)
  (car s))
(define (end-segment s)
  (cdr s))
 
;; 2.49
; (a)
(define outline-painter
  (let ((left-bottom (make-vect 0 0))
        (left-top (make-vect 0 1))
        (right-bottom (make-vect 1 0))
        (right-top (make-vect 1 1)))
    (segments->painter (list
                        (make-segment left-top left-bottom)
                        (make-segment left-bottom right-bottom)
                        (make-segment right-bottom right-top)
                        (make-segment right-top left-top)))))
; (b)
(define X-painter
  (let ((left-bottom (make-vect 0 0))
        (left-top (make-vect 0 1))
        (right-bottom (make-vect 1 0))
        (right-top (make-vect 1 1)))
    (segments->painter (list
                        (make-segment left-bottom right-top)
                        (make-segment left-top right-bottom)))))
; (c)
(define diamond-painter
  (let ((bottom (make-vect 0.5 0))
        (left (make-vect 0 0.5))
        (top (make-vect 0.5 1))
        (right (make-vect 1 0.5)))
    (segments->painter (list
                        (make-segment bottom left)
                        (make-segment left top)
                        (make-segment top right)
                        (make-segment right bottom)))))
; (d) 来源 http://d.hatena.ne.jp/laughing/20081115/1226737187，有修正
(define wave
  (let ((p0 (make-vect 0.4 1.0))
        (p1 (make-vect 0.35 0.8))
        (p2 (make-vect 0.4 0.6))
        (p3 (make-vect 0.3 0.6))
        (p4 (make-vect 0.15 0.55))
        (p5 (make-vect 0 0.8))
        (p6 (make-vect 0 0.6))
        (p7 (make-vect 0.15 0.4))
        (p8 (make-vect 0.3 0.55))
        (p9 (make-vect 0.35 0.5))
        (p10 (make-vect 0.3 0))
        (p11 (make-vect 0.4 0))
        (p12 (make-vect 0.5 0.3))
        (p13 (make-vect 0.6 0))
        (p14 (make-vect 0.7 0))
        (p15 (make-vect 0.6 0.45))
        (p16 (make-vect 1.0 0.2))
        (p17 (make-vect 1.0 0.4))
        (p18 (make-vect 0.8 0.6))
        (p19 (make-vect 0.6 0.6))
        (p20 (make-vect 0.65 0.8))
        (p21 (make-vect 0.6 1.0)))
    (segments->painter 
     (list
      (make-segment p0 p1)
      (make-segment p1 p2)
      (make-segment p2 p3)
      (make-segment p3 p4)
      (make-segment p4 p5)
      (make-segment p6 p7)
      (make-segment p7 p8)
      (make-segment p8 p9)
      (make-segment p9 p10)
      (make-segment p11 p12)
      (make-segment p12 p13)
      (make-segment p14 p15)
      (make-segment p15 p16)
      (make-segment p17 p18)
      (make-segment p18 p19)
      (make-segment p19 p20)
      (make-segment p20 p21)))))
 
;; 2.50
(define (flip-horiz painter)
  (transform-painter painter
                     (make-vect 1 0)
                     (make-vect 0 0)
                     (make-vect 1 1)))
(define (rotate-180 painter)
  (transform-painter painter
                     (make-vect 1 1)
                     (make-vect 0 1)
                     (make-vect 1 0)))
(define (rotate-270 painter)
  (transform-painter painter
                     (make-vect 0 1)
                     (make-vect 0 0)
                     (make-vect 1 1)))
 
;; 2.51
(define (below painter1 painter2)
  (let ((paint-bottom
         (transform-painter painter1
                            (make-vect 0 0)
                            (make-vect 1 0)
                            (make-vect 0 0.5)))
        (paint-top
         (transform-painter painter2
                            (make-vect 0 0.5)
                            (make-vect 1 0.5)
                            (make-vect 0 1))))
    (lambda (frame)
      (paint-bottom frame)
      (paint-top frame))))
(define (below painter1 painter2)
  (rotate-270 (beside (rotate-90 painter1) (rotate-90 painter2))))
 
;; 2.52
; (a) 略
; (b)
(define (corner-split painter n)
  (if (= n 0)
      painter
      (let ((up (up-split painter n))
            (right (right-split painter n)))
        (let ((top-left up)
              (bottom-right right)
              (corner (corner-split painter (- n 1))))
          (beside (below painter top-left)
                  (below bottom-right corner))))))
; (c)
(define (square-limit painter n)
  (let ((combine4 (square-of-four identity flip-horiz
                                  flip-vert rotate180)))
    (combine4 (corner-split painter n))))

Comments (11)

December 12, 2008 · Filed under 程序园

SICP习题解答：第一章（下）

^?View Code SCHEME

;; 1.29
(define (simpson-integral f a b n)
  (define (coefficient i)
    (cond ((or (= i 0) (= i n)) 1)
          ((even? i) 2)
          (else 4)))
  (let ((h (/ (- b a)n )))
    (* (/ h 3)
       (sum (lambda (i) (* (f (+ a (* i h))) (coefficient i)))
            0
            (lambda (i) (+ i 1))
            n))))
 
;; 1.30
(define (sum term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (+ result (term a)))))
  (iter a 0))
 
;; 1.31 只需要把sum改动两处。
; 递归实现
(define (product term a next b)
  (if (> a b)
      1
      (* (term a)
         (product term (next a) next b))))
 
; 迭代实现
(define (product term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (* result (term a)))))
  (iter a 1))
 
; 阶乘
(define (factorial n)
  (product (lambda (x) x) 1 (lambda (i) (+ 1 i)) n))
 
; π的近似值
(define (calc-pi n)
  (define (term i)
    (/ (- (square i) 1) (square i)))
  (define (next i)
    (+ 2 i))
  (* 4 (product term 3.0 next n)))
 
;; 1.32
(define (accumulate combiner null-value term a next b)
  (if (> a b)
      null-value
      (combiner (term a)
                (accumulate combiner null-value term (next a) next b))))
 
(define (accumulate combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (combiner result (term a)))))
  (iter a null-value))
 
;; 1.33
; filtered-accumulate 的两种实现
(define (filtered-accumulate combiner null-value term a next b filter)
  (define (do-filter x)
    (if (filter x) x null-value))
  (if (> a b)
      null-value
      (combiner (do-filter (term a))
                (filtered-accumulate combiner null-value term (next a) next b filter))))
 
(define (filtered-accumulate combiner null-value term a next b filter)
  (define (do-filter x)
    (if (filter x) x null-value))
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (combiner result (do-filter (term a))))))
  (iter a null-value))
 
; (a)
(filtered-accumulate + 0 (lambda (x) x) a (lambda (i) (+ 1 i)) b prime?)
; (b)
(filtered-accumulate * 1 (lambda (x) x) 1 (lambda (i) (+ 1 i)) (- 1 n) (lambda (a) (= 1 (gcd a n))))
 
;; 1.34 (f f)相当于(f 2)，相当于(2 2)，会因为2并非可以调用的函数而出错。
 
;; 1.35 证明不动点直接计算即可，计算的(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)。
 
;; 1.36 全部代码如下
(define tolerance 0.00001)
 
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (display guess)
    (newline)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))
 
(define (f x) (/ (log 1000) (log x)))
 
(display (fixed-point f 2))
(newline) (newline)
(display (fixed-point (lambda (x) (average x (f x))) 2))
(newline) (newline)
 
; 使用与不使用平均阻尼的步数分别为9与34步。
 
;; 1.37
; 递归版本
(define (cont-frac n d k)
  (define (shift f)
    (lambda (i) (f (+ 1 i))))
  (if (= 0 k)
      0
      (/ (n 1) (+ (d 1) (cont-frac (shift n) (shift d) (- k 1))))))
 
; 迭代版本
(dsefine (cont-frac n d k)
  (define (iter result i)
    (if (= 0 i)
        result
        (iter (/ (n i) (+ (d i) result)) (- i 1))))
  (iter 0 k))
 
; 当k不小于11时，结果有4位精度。
 
;; 1.38
(define (e-2 k)
  (cont-frac (lambda (i) 1.0)
             (lambda (i)
               (if (= 2 (remainder i 3))
                   (* 2 (/ (+ 1 i) 3))
                   1))
             k))
 
;; 1.39
(define (tan-cf x k)
  (cont-frac (lambda (i)
               (if (= 1 i) x (- (square x))))
             (lambda (i)
               (- (* 2 i) 1))
             k))
 
;; 1.40
(define (cubic a b c)
  (lambda (x)
    (+ c (* x (+ b (* x (+ a x)))))))
 
;; 1.41
; double函数
(define (double f)
  (lambda (x)
    (f (f x))))
 
;; (((double (double double)) inc) 5) 的值为21。因为 (double double) 得到一个把参数过程应用四次的函数，而 (double (double double)) 事实上是将“把参数过程应用四次”的过程应用两次，也就是一个将参数过程应用十六次的函数。
 
;; 1.42
(define (compose f g)
  (lambda (x) (f (g x))))
 
;; 1.43
(define (repeated f n)
  (if (= 1 n)
      f
      (compose f (repeated f (- n 1)))))
 
;; 1.44
(define (n-times-smooth f dx n)
  ((repeated (lambda (f) (smooth f dx)) n) f))
 
;; 1.45
(define (calc-nth-root-with-t-average-damps x n t)
  (fixed-point ((repeated average-damp t) (lambda (y) (/ x (fast-expt y (- n 1))))) 1.0))
 
;; 通过实验，得到的规律是，当 2^t>=n 时，用 t 次平均阻尼求 n 次方根是可行的，于是有下面的程序。
(define (nth-root x n)
  (define (minimal-t n)
    (if (= 1 n)
        0
        (+ 1 (minimal-t (quotient n 2)))))
  (calc-nth-root-with-t-average-damps x n (minimal-t n)))
 
;; 1.46
(define (iterative-improve guess improve good-enough?)
  (if (good-enough? guess)
      guess
      (iterative-improve (improve guess) improve good-enough?)))
 
(define (sqrt x)
  (define (improve y)
    (/ (+ x (square y)) (* 2 y)))
  (define (good-enough? y)
    (> tolerance (abs (- (square y) x))))
  (iterative-improve 1.0 improve good-enough?))
 
(define (fixed-point f first-guess)
  (define (improve x)
    (f x))
  (define (good-enough? x)
    (> tolerance (abs (- (f x) x))))
  (iterative-improve first-guess improve good-enough?))

Comments (2)

November 27, 2008 · Filed under 程序园

SICP习题解答：第一章（上）

^?View Code SCHEME

;; 1.1-2 略
 
;; 1.3
(define (greater-two a b c)
  (-
   (+ a b c)
   (min a b c)))
; 或
(define (greater-two a b c)
  (cond ((and (> b a) (> c a))
         (+ b c))
        ((and (> a b) (> c b))
         (+ a c))
        (else (+ a b))))
 
;; 1.4 (if (> b 0) + -) 根据b的正负性返回函数+或-。
 
;; 1.5 函数p的定义 (define (p) (p)) 是不断递归调用自己，所以欲对其进行求值/展开会产生死循环。调用 (test 0 (p)) 时，若采用应用序求值，会先对函数的参数，包括 (p) 求值，因而产生死循环，无法输出结果；若采用正则序求值，则由于 (p) 的值事实上不会被展开，故会正常返回0。
 
;; 1.6 将在调用函数 new-if 时，应用序要求先算出其所有参数的值，new-if 的后两个参数——代表 if 的两个分支的代码都将被执行。所以 (sqrt-iter guess x) 必然需要调用 (sqrt-iter (improve guess x) x)，这导致死循环。
 
;; 1.7
(define (sqrt x)
  (define (sqrt-iter guess)
    (define (good-enough?)
      (< (abs (/ (- (* guess guess) x) x)) 0.001))
    (define (improve)
      (define (average a b)
        (/ (+ a b) 2))
      (average guess (/ x guess)))
    (if (good-enough?)
        guess
        (sqrt-iter (improve))))
  (sqrt-iter 1.0))
 
;; 1.8
(define (cube-root x)
  (define (iter guess)
    (define (good-enough?)
      (< (abs (/ (- (* (* guess guess) guess) x) x)) 0.001))
    (define (improve)
      (/ (+ ( / x (* guess guess)) (* 2 guess)) 3))
    (if (good-enough?)
        guess
        (iter (improve))))
  (iter 1.0))
 
;; 1.9 第一个过程是递归的，表达式被递归地逐渐展开再合并；第二个过程中的递归是尾递归，不妨理解为迭代的。
 
;; 1.10 (f n)是n的2倍，(g n)是2的n次方，(h n)是2的(h (- n 1))次方。
 
;; 1.11
; 递归方式
(define (f n)
  (if (< n 3) n
      (+ (f (- n 1))
         (* 2 (f (- n 2)))
         (* 3 (f (- n 3))))))
 
; 迭代方式
 
(define (f n)
  (define (iter a b c i)
    (if (= i n) c
        (iter b c
              (+ (* 3 a) (* 2 b) c)
              (+ i 1))))
  (if (< n 3) n
      (iter 0 1 2 2)))
 
;; 1.12
(define (C n i)
  (if (or (= i 0) (= i n))
      1
      (+ (C (- n 1) (- i 1)) (C (- n 1) i))))
 
;; 1.13 可利用归纳法和定义直接证。
 
;; 1.14 空间复杂度为 O(amount)，因为任何时刻调用链的长度（栈上的函数数量）不超过 amount+1；时间复杂度为 O(amount * result)，因为每得到一种方案都调用一次 (cc 0 kinds-of-coins)。
 
;; 1.15 空间与时间复杂度均为O(log a)。
 
;; 1.16 prod*a^m是不变量。
(define (fast-expt b n)
  (define (iter prod a m)
    (if (= 0 m) prod
        (if (= 0 (remainder m 2))
            (iter prod (* a a) (/ m 2))
            (iter (* prod a) (* a a) (/ (- m 1) 2)))))
  (iter 1 b n))
 
;; 1.17
(define (fast-multi a b)
  (if (= 1 a) b
      (if (= 0 (remainder a 2))
          (double (fast-multi (halve a) b))
          (+ b (double (fast-multi (halve (- a 1)) b))))))
 
;; 1.18
(define (fast-multi a b)
  (define (iter sum i n)
    (if (= 0 n) sum
        (if (= 0 (remainder n 2))
            (iter sum (double i) (halve n))
            (iter (+ sum i) (double i) (halve (- n 1))))))
  (iter 0 a b))
 
;; 1.19 p’ = pp + qq，q’ = qq + 2pq。
 
;; 1.20 应用序需要4次；正则序需要更多，没仔细数，因为gcd函数体中出现了三处b，当b是调用remainder的形式时，它需要被展开若干次。
 
;; 1.21 略。
 
;; 1.22-24 我用的DrScheme没有定义runtime……555
 
;; 1.25 如果不在计算乘幂时随时取模，每次乘法将由于被乘数位数的迅速增长而不能被看做单位时间的原子操作。
 
;; 1.26 每次(expmod base exp m)当exp为正偶数时会调用两次而非一次(expmod base exp m)，f(N)=2*f(N/2)+Θ(1)导致f(N)=Θ(N)，而原始版本的f(N)=f(N/2)+Θ(1)导致f(N)=Θ(log N)。
 
;; 1.27 以下程序中，(find-carmichael n)找出不超过n的Carmichael数
 
(define (prime? n)
  (define (iter i)
    (cond
      ((> (square i) n) true)
      ((= 0 (remainder n i)) false)
      (else (iter (+ i 1)))))
  (iter 2))
 
(define (carmichael? n)
  (define (iter i)
    (cond
      ((= i n) true)
      ((not (= i (expmod i n n))) false)
      (else (iter (+ i 1)))))
  (and (not (prime? n)) (iter 2)))
 
(define (find-carmichael n)
  (define (iter i)
    (cond ((carmichael? i) (display i) (display "\n")))
    (cond ((< i n) (iter (+ i 1)))))
  (iter 2))
 
;; 1.28
(define (miller-rabin n)
  (define (exp-iter prod base exp)
    (cond ((and (< 1 prod) (< prod (- n 1)) (= (remainder (* prod prod) n) 1)) 0)
          ((= 0 exp) prod)
          (else (if (even? exp)
                    (exp-iter
                     prod
                     (remainder (* base base) n)
                     (/ exp 2))
                    (exp-iter
                     (remainder (* prod base) n)
                     (remainder (* base base) n)
                     (/ (- exp 1) 2))))))
  (define (check i)
    (= 1 (exp-iter 1 i (- n 1))))
  (define (check-iter i)
    (cond ((= i 0) true)
          (else (if (check (+ 2 (random (- n 3))))
                    (check-iter (- i 1)) false))))
  (or (= 2 n) (= 3 n)
      (and (< 2 n) (= 1 (remainder n 2)) (check-iter 20))))

Comments (5)

November 26, 2008 · Filed under 程序园

2008年11月24日

昨天，ACM/ICPC杭州赛区以金奖（第五名）谢幕。对于Genesis队，本赛季的所有比赛已经结束，以后不大可能再在比赛中看到我们这支队伍了，希望Genesis得到的两块regional金牌以及一直以来的表现能让关注我们的人满意。

对于我已经研一的两名队友，这大约是他们最后一次以队员的身份出现在ACM/ICPC的赛场上；与高远(xgy)、杨克特(T_T)两位学长的无间配合是太过愉快的经历，学长的经验也让我受益良多。

而对于我，一名正式进入大学才三个月的大一新生，一切才刚刚开始；前方还长的路让人激动憧憬，请相信我会带来更多惊喜。

其实，这赛季能够连拿两金，取得对于我这种新手来说可称辉煌的成绩，不仅取决于全队的努力，对于我自己来说，其实不乏运气成分。这学期我主要的突破是仔细读了本《简明数论》（其实这书只有一半名副其实，“明晰”是无疑的，“简单”则谈不上），打下了还算扎实的数论基础，差不多能应付Regional中通常的数论题了，结果我们队参加的哈尔滨和杭州两个赛区正好都有数论题出现，特别是我们在哈尔滨最后才解出的B题更是我们夺金的关键。另外，在杭州赛的前几天，我匆匆浏览了《柔性字符串匹配》的后半部分，主要内容是用有限自动机做正则表达式匹配。对那本书的主题我自然是一知半解，不过倒对有限自动机有了较多的感受和认识。没想到杭州赛区的H题就是判断两个有限确定性自动机是否等价的题目。虽然没见过，但正好这几天见识了很多与自动机有关的内容，灵光一现就得出了算法，使我们队解出了第6题，也是场上解出的最后一道关键题目。

这样看来，我第一年的ACM/ICPC征程真可称顺风顺水，似乎幸运眷顾，完全没遇到挫折地走下来。当然，以后还是老老实实提高自身实力才是王道，近期打算学学Java，读读SICP之类的书。

这个学期还剩下大约一半，除了为了保持状态做点SRM以外，就不再寻求编程竞赛方面的突破了，应该多尝试点不同的内容。学Java达到与目前的C++近似的熟练程度，读SICP、Concrete Maths、Programming Pearls是必须完成的内容，如果还有闲暇就打算读读Algorithm Design以及一些AI方面的书目。最近一本《数学分析原理》让我多少发现了纯数学的美感，虽然这学期应该不大可能了，但以后还是要读些纯数学的经典教材的。物理是这学期多少令人头疼的科目，得抓紧看一下，希望能培养出兴趣。

好吧，读书去了。

Comments (8)

November 24, 2008 · Filed under 军机处, 生活志

《数学分析原理》旁注（上）

注：凡“旁注”性质的笔记，都是无规划不成系统的读书随想。尤其与我大多数短篇的读书笔记一样，并不求别人也看懂。

第1章 (2008.11.16)

1.24：引入复数的一切都很完美，只是这个乘法的定义还是略显突兀。能否通过M1~M5以及零元、幺元等内容将这个定义更顺畅地推导或引入呢？换句话说，有了很自然的加法的定义，要满足(1,0)为幺元以及M1~M5，有了这些条件能否得出“合理”的乘法定义有哪些？于是就是函数方程了。如果这是唯一满足的定义那就完美了，不过我的推测是：它是函数方程所有解中明显、特殊、或朴素的一个。

1.35：又是那种“神来之笔”的证明……怎样理解这优美的构造？

1.A.9：任何两个具有最小上界性的有序域同构。我会找到它的证明。

第2章 (2008.11.17)

这章的目的为何？完全不明白，也没办法搞清定理之间的联系。

2.12：可数个可数集的并是可数集。

2.23：所以同为开集与闭集的集就仅有空集和全集。

2.23：紧集，对于集合的每个开覆盖，存在一个有限子集也是开覆盖。

2.44：Cantor集的概念。

第3章 (2008.11.17)

这章的目的应该是判断及求得数列以及级数的极限。

3.1：极限的概念可以直接在度量空间中定义。

3.21：定理能按数列与级数两种语言来叙述与应用。

3.27：正项不增序列a_i的级数收敛当且仅当2^k a_{2^k}的级数收敛。这可以用相对很稀疏的项判断级数的收敛性。

3.38：幂级数的收敛圆（由根值法推出）。

3.42：∑a_n有界，b_n单调递减到0，∑a_n b_n收敛。（分部法）推论：交错递减则收敛。

3.47：级数乘积的定义有卷积的味道。

3.53：对（收敛但非绝对收敛的）级数重排会改变收敛的值！奇妙……

数列：单调有界定理，比较法，Cauchy准则。

级数：比较法，3.27，另一种形式叙述的Cauchy准则，比率法与根值法（3.37说明前者有效的后者一定有效），收敛半径，分部法及推论。

第4章 (2008.11.18)

4.8：函数 f: X->Y 连续，当且仅当对于Y的每个开集V，f^-1(V)是是X中的开集。（由于开集的补集是闭集，所以叙述中可以换成闭集。）

4.18：一致连续是函数（在某个定义域上）的性质，而连续是函数在点上的性质。然而在紧集上，这两个概念等价。

4.23：函数的连续性保持定义域的连通性。

这章应该是探讨了函数的连续性与第2章中集合的特性的关系。2、4两章应该都是构建后文微分、积分理论大厦的基石与原材料。

第5章 (2008.11.19)

5.9：直接证一般中值定理，很赞。

5.12：导函数可以不连续，但不能有第一类间断，且在区间内能像连续函数一样取到所有中间值。

5.13：L’Hospital法则的证明，看上去很不直观。Wikipedia上的证明似乎更优美。

5.15：这个证Taylor定理/Lagrange余项的方法简洁得很诡异，其实没看懂……Wikipedia上的先证integral reminder再用积分中值定理直接得到Lagrange reminder的方法直接且精炼。

第6章 (2008.11.20-21)

6.1：这个定义与Wikipedia上的Darboux integral完全相同。上积分、下积分——它们必定存在，可积性便等价于二者是否相等——于我是新鲜的概念。以下便用这些定义（还有一个“加细”）证明了若干关于可积性的性质。

6.2：在概念中增添“-Stieltjes”之后，让关于x的Riemann积分可以关于任意函数α(x)，扩充的要点是，α不必可导，甚至不必连续。

6.15：有点绕……第一遍没看明白。不过的确是一下子让人发现Riemann-Stieltjes对于Riemann的扩充，然后函数值、级数(6.16)都可用一个Riemann-Stieltjes积分来表示，6.18是点出本质的总结。

6.20-21：微积分基本定理的两部分。我总是觉得Wikipedia上的证明一下子就能看懂，这书故作高深的倾向却要让人看很久才知道他是怎么证出来的……这种从定义就开始“立意求高”类似于“伤人乎不？问马。”，教材中的例子有萧树铁的《大学数学——代数与几何》中对行列式的定义。这样的教材的确有境界，不过最好还是借助大众化的Wikipedia补充一下。

Comments (2)

November 21, 2008 · Filed under 生活志

《简明数论》的简明笔记（中）：13~21节

Euler函数φ(m)，定义，积性不完全；
- $\phi(m)=m\prod_{p|m}(1-\frac{1}{p})$ ；
- $\phi(m)=m\sum_{d|m}\frac{\mu(d)}{d}$ ；
- 。
  - 用积性证很简单；证明二：按与m的最大公约数分类。
f(n)的Mobius变换：；
- Mobius逆变换：；
  - 以上两式等价，f(n)与F(n)的积性也等价。
- f与g的Dirichlet卷积： $h(n)=\sum_{d|n}f(d)g(\frac{n}{d})$ ，h保持f与g的积性。
同余：
- a对模m的最小非负剩余、绝对最小剩余；
- 同余式是等价关系；同余式可加减乘；ca≡cb (mod m)等价于a≡b (mod m/(c,m) )；
- 对模m的逆的定义。
同余类、完全剩余系定义；
- 既约剩余系包含的同余类个数即φ(m)。
- (a,m)=1时，x遍历m的完全/既约剩余系当且仅当ax遍历m的完全/既约剩余系。
  - 用这个可轻松证明Fermat-Euler定理。
Wilson定理，即(p-1)! ≡ -1 (mod p)。
- 证：除了-1外，其它因子可与（不相等的）逆元配对抵消。
- 即，p的既约剩余系的积模p得-1。
  - 扩展：p可换成p^k，2p^k（这两者p是奇素数）。
- 事实上，r不取1,2,4,p^k,2p^k时，r的既约剩余系的积模r得1。
ax≡b (mod m) 型的同余方程。
- (a,m)|b 是有解的充要条件，解有(a,m)个。
  - 可求a对m的所有逆元。
- 注意到一个解是 $x_0 = a^{\phi(m)-1}b$ ，也可用扩展欧几里德求特解。
- 所有解是 $x_0 + \frac{m}{(a,m)}t$ ，其中0<=t<(a,m)。
形如的一次同余方程组。
- 若{m_i}两两既约，则解数必为1（中国剩余定理）。
  - 解为 $x \equiv \sum M_i M_i^{-1}a_i \pmod{m}$ 。
  - 其中 $m = \prod m_i = M_i m_i$ ， $M_i M_i^{-1} \equiv 1 \pmod{m_i}$ 。
  - 当a_i分别遍历m_i的完全/既约剩余系时，x遍历m的完全/既约剩余系。
- 若{m_i}并非两两既约，例如(m_i,m_j)=a时，可将模m_i与m_j的两个方程化成模a、m_i/a、m_j/a的三个方程。
  - 编程时，直接化为若干个模p^k的方程似更简便，其中p^k || [m_1,m_2,...,m_i,...]。
- f(x)≡0 (mod n) 的解数设为 T(f;n)，则T(f;n)是关于n的积性函数。
  - 于是只需研究f(x)≡0 (mod p^k)型方程的解法。
  - 即求解多个方程后再解个模{p^k}的一次同余方程组。

ACM/ICPC – Asia Harbin 2008 小结

10月8日晚的火车，三十多个小时的旅途，去往一座遥远陌生的北方城市，哈尔滨。

上火车后，惊喜地发现，我们硬卧车厢的走廊窗口下竟然有两相和三相的电源插座！可以无顾忌地使用电脑，似乎会给旅途增添不少趣味和意义。火车上，我把觉得比较有用的论文看了一遍，又对照着CD看了几章《听音乐》。

我在重要的比赛或考试之前容易滋生紧张情绪，这也是NOI2007的败笔之一。不过这次不同，一路上有队友相伴，本应枯燥的车厢里，充满欢声笑语。

灿哥通过神奇方式买到的火车票十张全是上铺，不过大家发现这种新式车厢的上铺非常舒服。更何况，在某人的下铺处有一只天真无邪可爱动人如假包换的小萝莉……这个话题不展开了，请自行YY。

T_T同学出了一些猥琐的迷题（e.g. 一只公牛和一只母牛同时踩坏了别人家的田，为何公牛主人赔偿三分之一而母牛主人赔偿三分之二？），令大家都很惊讶的，某位dd同学几乎每次都反应很快地第一个说出答案。好吧……在此我申明三点：第一，那些迷题没有一个是我之前听过的；第二，之所以我每次都能最先得出答案，我的唯一解释就是：我的思维敏捷、智商高；第三，我很天真哒，我的话讲完啦。

火车上的每顿饭都去餐车吃，虽然贵且不好吃，但毕竟是能找到的最佳选择了。这时T_T同学的母亲在德州站送上来的三只扒鸡正如雪中送炭，众饕餮很快就将那些可怜的无毛二足动物杀得片甲不留，对其二足尤不留情^_^。

火车到站时间是10日早晨5时许，一群几乎都没来过东北的人立即领教了寒风的威力。一干人等饥寒交迫地奔赴某盖头gg事先选定的车站门口的KFC，却发现人满为患无处容身。我通过手机上的Google Map搜索到了最近的另一家KFC，大家便打车前往。BTW，发现哈尔滨的GPRS网络很棒，明显感觉到比杭州的快，然而不知为何某只很拉风的iPhone在哈尔滨却无论怎样都连不上GPRS……

KFC的早餐让大家都找回了久违的饱腹感，充电完成的一干人等玩起了由gdb引进的多人纸牌游戏“盖棉被”。如果仅描述规则的话，听起来真是一个挺傻气且低技术含量的游戏：若干人轮流出牌，同时循环报数1至13；若某人打出的牌和说出的数字恰相同，所有人都需要尽量快地将手掌盖向牌堆，盖在最上面的手掌（也即反应最慢的）需要拿走所有的牌；手中无牌者胜。不过大家都玩得不亦乐乎，情不自禁高声大叫，引来了KFC MM礼貌的制止。在KFC的经历，让大家明白了一个深刻的道理（做小学生作文状）：南北风俗不一样！好吧，看不懂的请略过或自行YY -___-。

打车来到哈尔滨工程大学……门口的八一宾馆报到，然后在志愿者MM的带领下入住十五元一天的学生宿舍-___-，还好后来在我们强烈要求下换成八一宾馆的标准间了^_^，偶和可爱的xgy队长gg一间哦~

10日一天都没什么安排，继续盖几圈棉被以后，一堆无聊人士围坐一圈玩起了同样低技术含量的梭哈，用另一副牌当筹码。赌博的结果是有的人（可怜的xgy gg，cmft）输到倾家荡产，有的人（就是我啦^_^，嘻嘻）成了大资本家，我赢了比翻倍还要多哦~

午饭选在某忘记了名字的火锅店，灿哥中途从机场赶来加入。相信大家都吃饱了，而且我自己认为吃得还不错，只是某人点了过多的丸子浪费不少……

下午和晚上，除了必要的赛前准备，大家仍然把时间用在了打牌与谈天之类娱乐放松的项目上。期间七个人玩两副牌的接龙还是挺好玩的。顺便炫耀下，在哈尔滨玩的很多盘接龙的分数都记录了下来，在幸运与实力的双重照耀下，dd同学是总积分的最后赢家~oh yeah~

期间值得一提的事情是，我们目睹了某欧阳极囧的脸红过程，并拍下了真相。欲知详情，请私下交流或自行YY……关键字：罩杯-___-。

10日晚上一直玩到午夜才睡。

11日上午貌似仍然是谈天玩牌。哈工程“大学生美食广场”午饭后，Genesis+gdb的猥琐男们在哈工程的长椅上懒洋洋地晒太阳，顺便开展猥琐的分手现场偷窥行动以及路过MM打分行动，期间小耗子乱入-___-。

下午试机，觉得电脑上的NetBeans还算好用，决定第二天比赛就用它了。试机期间，主办方的组织让人不能满意：每队三个人只有一份题目且不说，最不能忍受的是judge故障连连。我默默祈祷正式比赛时最好不要出现judge问题。

11日晚上，大家没有过分的娱乐，早早回到了各自的房间里养精蓄锐。我看了lrj“习题指导”和北大出版社《简明数论》两本书中的重要章节，听了贝交第五全曲，九点半安然入睡。

12日早晨六点半，醒来后的我感到前所未有的精神焕发，觉得这应该就是所谓的最佳比赛状态了。早餐中，灿哥给我们讲了若干“坚持到最后一分钟翻盘”的传奇故事。我相信听者没人想到，那天的比赛中，我们中的一支队伍会创造另一个传奇，一个毫不逊色，且注定被一遍遍讲述的传奇。

开赛半小时前进入场地，我们的装备大致如下：德芙巧克力一盒、红牛饮料若干罐、圣经一本（和合本+NIV对照）、牛津高阶词典一本、以及常用参考书一堆。

比赛开始了，共有十题，从A到J。按照一贯的读题分配：T_T看ABC，xgy看DEFG，我看HIJ。

我分到的题目都比较长，H大致看懂了，断定绝不是前期能写的题；I题意很简单，给定一个顶点的度序列，问是否存在对应的无向简单图，我觉得这应该是的经典问题，但却完全没看过类似的问题或算法；J的题意也不难理解，但可以看出，相当有大自然题的潜质。

大家把题都看的差不多了以后，互相两两交流了一下题意，没发现明显可做的题目。这时看到大屏幕上已经有四个队过题了，过的都是I。我意识到，I肯定不是难题，便专心yy之。期间xgy和我都怀疑是否只判断一下度的奇偶性就可以了，不过很快找到了反例。仿佛灵光一闪，我脑中突然出现了一个贪心构造的方法，讨论后，大家都没思路证明其正确性，却也找不到反例，于是我便上去敲了代码并提交之。

这时看到有牛队过了A，T_T给我讲了题意后，我写出前N层和的表达式给了他，他完善了一下二分答案的细节，便上去写了。写完后发现，按照我给的表达式计算的话，虽然输入不会超过六十四位整数，然而计算的中间过程完全可能会溢出，一时没有找到解决之道，只好由xgy把这个C++程序翻译成Java用BigInteger来写，交上去以后很快返回了Yes。这时已经拖了不知多久的I终于返回了，还好是个Yes。拿到两个气球的我们排名并不乐观。

在此之前，xgy给我讲了他对F的想法，我在他的基础上很快推出了完整的充要条件，但我俩都不太确定该怎么实现比较好。T_T听见后表示，如果充要条件是这样的话，那么他完全能写，因为写过很类似的题目。于是他上去用DP/递推的方式写了个程序，很快Yes了。三道题都1Y的我们第一次冲进了前十名。

写F期间，我和xgy在讨论G题，这道题的文字叙述得挺模糊的，不过通过仔细阅读加合理推测，我们很快发现原来就是一个有向无环图上的博弈问题，拓扑排序一遍再DP就行了，我上去写了以后也1Y了。当我们第4题的AC反映在大屏幕上的时候，我发现，在比赛时间过去约一半时，我们是全场第一个AC 4题的队伍，排名第一。旁边堪称全明星的清华IronGods队也只有三个气球。

这是我第一次感到情绪波动的时候，在此之前，我一直都保持着平和淡定的情绪，精神非常集中，头脑非常清醒，基本上处于巅峰状态，思考和敲题的效率都很高。然而此刻，看着大屏幕上飘扬在最上方的team53（我们的队伍编号），我出现了不应该有的过分激动以及过分自信。现在，我（多少有些羞愧地）承认，在那一瞬间，我想到了斯德哥尔摩。暂时领先造成的情绪波动直接影响到了我后半程的发挥，这也是我个人本次比赛得到的最重要的教训。

C题大概是早就得出了二分图最优匹配的算法，T_T上去写，似乎是用了令我难以置信的短暂时间就敲完了。交上去以后，返回了我们的第一个WA。我提醒T_T是否注意到船到达port以后不能再出来的条件，他意识到忽视了这一点，很快改好了，没想到仍然是WA。于是T_T打印了代码让xgy和我看。给代码查错应该是最需要集中精力的活，而我在看那份代码时却完全做不到这点，草草地、甚至一目十行地在看，怎么看都觉得没错误。很无奈的我们便想，是不是题目比较阴险必须用64位整数才可以过呢？其实赛后来看，这绝对是不必要的想法。因为当时至少有十多支队伍过了C，不少队伍都是作为第四道题过的C，且其中不乏1Y。这可以推断出，WA不大可能源于出题人的阴险，而是应该源于我们自身的问题。不过，当时的情况是，改了long long，依然WA。这期间，4题甚至5题的队伍越来越多，我们的rank一直在跌，前景非常不容乐观。看来我的缺点就是这样……处于顺境的时候容易被冲昏头脑，只有适当的逆境才能达到冷静。我再次看T_T的代码，不漏过一个字符的认真看，终于发现了程序中的低级bug。——只是注释掉了一行代码，程序就AC了。那个错误的根本原因是T_T在写那一小段时稍微有点想错了，而我从局外的角度看这段代码时，本应很快意识到这个几近愚蠢的错误，然而由于第一遍的不专心，我直到若干次WA之后第二遍阅读代码时才发现了它，这题做得不好，我至少应该承担一半的责任。

还好，虽然C题罚时比较多，在我们前四道题全部1Y的基础上，终于五题的我们名次还不错。接下来可做的题只有B和D。前者是数论题，我已经推导出了一个结果，有算法了；后者是纯粹的高斯消元而已；二者的共同点是都需要用到大数，最好是用Java来写。嗯……应该是我们队的另一个缺陷吧，我们没有人能把Java写得跟C++一样熟，所以必须用Java写的题在敲代码的速度上是吃亏的，甚至有些有关语言特性的东西还需要在赛场上试一试才知道。我们三人中写Java最熟练的xgy队长觉得B似乎更容易实现，于是便上去写。花费了比通常要多的时间，但却是严格地按照我给定的算法写出来的，没想到交上去以后WA了，只好打印出来交给我们查错，而他自己接着写D。——我想在这时我们的缺陷就完全暴露出来了：剩下两道可以写的题都需要用Java写，而赛前的训练中用Java写过题的竟只有xgy一人。这导致此时能写D的仍然只有xgy，而自己写的B还没能AC的xgy恐怕无法专心全力去写D，T_T和我在下面对着打印出来的B的Java代码YY其bug……T_T和我一致认为那Java代码十分“诡异”，表达算法时显得很不直白，但分析的结果也无法找到错误。我建议把那代码改成不那么诡异的形式再试试，大家同意了，便放下D来改B的代码。终于改出了比较清晰易懂的代码以后，测试的结果却似乎与刚才“诡异”的程序并无区别……（期间我还忍不住下手帮着写了几行，现在回忆时发现，赛场上的那几行其实是我平生第一次写Java代码- -。。。）貌似又是在我的撺掇下，把那个改完以后完全看不到区别的程序提交了，结果又是WA。这时进入比赛的最后一小时已经有一段时间了，封了board，各个队伍的排名已经不再实时公布，但从现场升起的气球情况来看，貌似已经有七题的队伍了，如果我们再不抓紧时间搞出第六题，能否拿到金牌相当未知……这时xgy继续写不知道有多大希望的D，而T_T和我做了一个相当正确的决定：我们从题意开始，对推导的过程完整地讨论地检查了一遍。期间，T_T的一句话启发了我，我发现原来是我在一开始的数学推导中少考虑了一种情况，难怪一直WA到死……我谢罪。。。还好把那种情况的代码加到程序里并不困难，加上以后就AC了，在比赛还剩十多分钟的时候，我们终于六题。

看到屏幕上的Yes的时候，我们全都激动地站了起来振臂欢呼。这是出现了一个喜剧性的小插曲，比赛的志愿者MM给我们送气球时弄错了：应该给我们的是B题对应的浅紫色气球，她却拿来了J题对应的深紫色气球。据说当时观众席上立刻一片哗然，没人想到会有队伍在比赛中把最不可做的J给做出来。周维民教授（ICPC中国区秘书长）也马上带着一堆摄影记者走过来对着我们不住地拍照。（嗯，以上文字有野史的风范，若有不确切之处请一笑而过^_^。。。）

最后几分钟的时间里xgy在敲D，不过花在这题上的时间和精力的确是比较少，加之我们不知道高斯消元在无需考虑精度的情况下会有比标准的做法好写很多的实现，所以直到最后也没能写完。至于旁边我们的Sirius凭借最后一分钟提交的D题冲至第五的神迹，我们也只有深深膜拜了。。。Orz

金牌到手的我们无忧无虑，下午我玩了会儿牌，听了会儿音乐，晚上代表队伍上台领奖（非常感谢队里的两位gg给我这个荣耀的时刻）。

接下来的时间里，Genesis与Sirius们都兴高采烈，发挥失误获得银牌的三个gdb则无法避免地淡淡失落。不过大家都知道团结勤奋的gdb实力还是相当强的，相信你们下次在成都的比赛中会弥补这次的遗憾！

其实我发现……比赛结束以后的事情我大都不太清楚了，因为颁奖结束的那天晚上起我就全身心地沉迷在一本奇书里。包括在归途火车上也一直是捧着电脑在进行一千多页的脑力激荡与思维历险……嗯，接下来我会抽空慢慢写点关于GEB的读后感的，虽然一下子很难整理出繁复的思绪。。。

哦……这次的哈尔滨之行Sirius与gdb各自也有非常精彩的小结，请原谅这篇略有些虎头蛇尾的文章吧，这五千多字已经写得我要吐血啦。。。有什么脱误遗漏错愕指出请指出，我一定修改。

好了，下一站杭州，在自己家门口比赛，相信通过对哈尔滨之行的总结，我们会越发完美。Genesis加油！

Comments (16)

October 19, 2008 · Filed under 军机处, 生活志

《简明数论》的简明笔记（上）：1~12节

按：数论貌似是我目前还接触太少的领域，遵从vls的推荐借了北大出版社的《简明数论》来浏览，还是很好玩儿的……下面是从中总结的一些比较新鲜的结论。

{a_i} 的最大公约数等于 {a_i} 的所有整系数线性组合组成的集合中的最小正整数；
- 事实上，被最大公约数整除，等价于能表示成整系数线性组合。

一次不定方程 ∑a_i*x_i=c 有解的充要条件是 c|({a_i})；
- 解一次不定方程的算法（待实现）。

x^2+y^2=z^2 的本原解：x=r^2-s^2, y=2rs, z=r^2+s^2；
- 其中r>s>0, (s,r)=1, 2不整除r+s；
- 等价地刻画了单位圆周上的有理点。

Chebyshev不等式：，；
- 其实重点在于：O(π(x))=x/log x，O(p_n)=n log n。
  - （π(x)即不大于x的素数个数；p_n即第n个素数。）

数论函数：[完全]积性函数的充要条件；
- 除数和函数 $\sigma(n)=\prod_{j=1}^{r}\frac{p_j^{a_j+1}-1}{p_j-1}$ ；
- F(n)=∑_{d|n}f(d) 保持f(n)的积性。（除数即Divisor）

Mobius函数：；
- - 事实上与容斥原理很有关联；
  - 引理： $\sum_{d|n}\mu(d)=[\frac{1}{n}]$
- 集合A中与K互质的元素个数 $S(A;K)= \sum_{d|K}\mu(d)|A_d|}$ ，其中A_d是A中被d整除的子集；
- 将A取不超过x的实数，K取不超过的所有素数的乘积，可得，这样可以在已知不超过的素数的前提下求π(x)。
  - 从算法的角度看似无意义？

Comments (3)

October 2, 2008 · Filed under 生活志

病中的贝多芬，及其它

上周六，第一场正式的ACM/ICPC比赛，哈尔滨赛区网络预赛，结束以后，我感冒了。（……有联系么？- -）直到今天，仍处于很难受的状态。近几年，我的感冒一年最多一两次，但每次都让我难受得要命。

昨天上午，我坐在电脑前，头昏脑胀、浑身无力、流涕不止，为翘课且没交作业而沮丧。听了几首巴赫、几首莫扎特，罕见地觉得不合口味，判断为感冒影响了听力。非常偶然地，我打开了Bernstein指挥的“命运”，贝多芬第五交响曲……

我有一年多没听过贝多芬了，上次听大概是07年8月卓越上Günter Wand的贝交全集打折的时候买了一套，但只听了一两遍就放下了。因为不喜欢，甚至厌恶——声嘶力竭的铜管，持续轰鸣的定音鼓，那种让人想起军乐的进行曲色彩，以及没完没了的表现斗争与反抗的不和谐音。——贝多芬交响曲并非全都如此，但至少从小听人津津乐道的“英雄”第三、“命运”第五以及“合唱”第九或多或少带有这些特质。我能接受的最富斗争色彩的古典乐，恐怕止于肖邦的“革命”练习曲，至少钢琴的音色总还是悠扬的，不像富于煽动的铜管。

但昨天，轻微的肉体上的痛苦，突然让我开始理解贝多芬！——斗争的主题，并不一定代表低下的音乐。（遗憾的是，我以前的看法与此相反。）但是，如果带着富足、平和甚至出世的心境去聆听贝多芬那些富有斗争性的篇章，只会听到无谓的嘈杂与吵闹，难以感受其中的力量之美。（被问及“假设一个唱片店飞向太空，你认为外星人会喜欢怎样的古典排行榜”时，Glenn Gould答道：“这很难讲，但我认为有一个作曲家不会上榜，那就是贝多芬———这不包括他的晚期作品和几首早期作品。”）

后来，我又在看Karajan八十年代指挥贝交的视频，重点在第九交响曲“合唱”的第四乐章。我喜爱合唱这门艺术，目前还有加入合唱团的打算（虽然声音和体貌都不一定合格= =）。然而，我曾无知地认为欢乐的主题也是低下的（貌似这与我的古典启蒙老师约翰·施特劳斯被我始乱终弃有关-____-）。对欢乐的赞颂，在我看来也许不如对神的赞颂那样有感染力。但要明白，贝多芬写作此曲时的晚年境遇（一个全无听觉的音乐家）应该是极度痛苦的！在欢乐中歌颂欢乐，类似于“真是好啊真是好”，是无谓且无味的。但在痛苦中对欢乐的追寻，如同在尘世中歌颂天堂，给痛苦中的人们带来的是大彻大悟般的洗涤。

合唱团唱出《欢乐颂》的主旋律，每一个音节都清晰地斩钉截铁。激动得脸部发热、浑身冒汗的我甚至觉得困扰多天的感冒已经不药而愈了！直到Karajan挥下最后一个短促坚定的手势，乐声开始绕梁，才意识到感冒之蛊只是暂时蛰伏，却从未离我而去……我还是得边擤鼻涕边咳嗽边写blog……

~~~~~~~~我讨厌感冒的分割线~~~~~~~~

现在要隆重宣布的是……本blog要转型了！从这篇开始，它将成为一个主要谈论古典音乐、兼谈个人生活的blog。

其实，不知是否有人注意到，本blog是经历过转型的。最初写blog的时候，这里的主题是现代诗，有不少作品及创作谈之类的东西。后来，由于参加各种编程竞赛，主题变成了与编程相关的种种，尤其是算法相关的东西很有一些。嗯，那时的名字叫”左手程序右手诗”。而现在，很久没更新了，这两个主题中的任何一个都让我提不起兴趣写到blog里，可悲地发现似乎进入了blogging的倦怠期。解决的方法就是，转型！趁现在处于狂热喜爱古典音乐的时期，多听，多写。

我不清楚是什么样的人在订阅我的blog。有一天我很惊讶地发现仅在Google Reader上的订阅数就有三位数！这鞭策我在保持风格的前提下，注重自己文章的质量。希望正在阅读的你也能喜欢我接下来关于古典音乐的文章。

p.s. 你见过被手握自己学分的任课教师逼迫催促更新的blogger吗？555~我真可怜啊。。。

Comments (6)

September 24, 2008 · Filed under 曾绕梁

« Older Posts

这个寒假读的书及其它

SICP习题解答：第二章（上）

SICP习题解答：第一章（下）

SICP习题解答：第一章（上）

2008年11月24日

《数学分析原理》旁注（上）

《简明数论》的简明笔记（中）：13~21节

ACM/ICPC – Asia Harbin 2008 小结

《简明数论》的简明笔记（上）：1~12节

病中的贝多芬，及其它

分类

历程

留痕

分类

标签

历程

留痕