;my work is between the two asterisk lines
(define (make-leaf symbol weight)
  (list 'leaf symbol weight))
(define (leaf? object)
  (eq? (car object) 'leaf))
(define (symbol-leaf x) (cadr x))
(define (weight-leaf x) (caddr x))

(define (make-code-tree left right)
  (list left
        right
        (append (symbols left) (symbols right))
        (+ (weight left) (weight right))))

(define (left-branch tree) (car tree))
(define (right-branch tree) (cadr tree))

(define (symbols tree)
  (if (leaf? tree)
      (list (symbol-leaf tree))
      (caddr tree)))
(define (weight tree)
  (if (leaf? tree)
      (weight-leaf tree)
      (cadddr tree)))

(define (decode bits tree)
  (define (decode-1 bits current-branch)
    (if (null? bits)
        '()
        (let ((next-branch
               (choose-branch (car bits) current-branch)))
          (if (leaf? next-branch)
              (cons (symbol-leaf next-branch)
                    (decode-1 (cdr bits) tree))
              (decode-1 (cdr bits) next-branch)))))
  (decode-1 bits tree))
(define (choose-branch bit branch)
  (cond ((= bit 0) (left-branch branch))
        ((= bit 1) (right-branch branch))
        (else (error "bad bit -- CHOOSE-BRANCH" bit))))
;*********************
(define (element-of-set? x set)
  (cond ((null? set) #f)
        ((equal? x (car set)) #t)
        (else (element-of-set? x (cdr set)))))

(define (encode message tree)
  (if (null? message)
      '()
      (append (encode-symbol (car message) tree)
              (encode (cdr message) tree))))

(define (encode-symbol symbol tree);it would be better to apply some tree checking method here
  (encode-symbol1 symbol '() (left-branch tree) (right-branch tree)))
 

(define (encode-symbol1 symbol result left-b right-b)
  (cond ((element-of-set? symbol (symbols left-b))
         (if (leaf? left-b)
             (append result '(0))
             (encode-symbol1 symbol (append result '(0)) (left-branch left-b) (right-branch left-b))))
        ((element-of-set? symbol (symbols right-b))
         (if (leaf? right-b)
             (append result '(1))
             (encode-symbol1 symbol (append result '(1)) (left-branch right-b) (right-branch right-b))))
        (else (error "encounter symbol could not be encoded with current dictionary:" symbol))))

 

;*********************
(define sample-tree
  (make-code-tree (make-leaf 'A 4)
                  (make-code-tree
                   (make-leaf 'B 2)
                   (make-code-tree (make-leaf 'D 1)
                                   (make-leaf 'C 1)))))

(define sample-message '(0 1 1 0 0 1 0 1 0 1 1 1 0))
(define sample-symbols (decode sample-message sample-tree))
(encode sample-symbols sample-tree);test if my procedure could encode message right
(encode '(A B S) sample-tree);test the error reporting func.

是想要告诉大家虽然平衡二叉树的索引效率较高，做集合运算还是将先其转换为序列比较有效率？应该是这样吧。

以递归的方法将一序列转换成平衡二叉树的方法简要来说就是

1.找出序列中间的元素n0

2.将原序列以n0为分割，分割成不含n0的前方序列t1和后方t2

3.以n0为node，将序列t1和t2转换后的平衡二叉树分别作为其左右分支，从而构建出更大的平衡二叉树

具体实现方法可以有细微的区别，书中给出的partial-tree定义简洁优雅，相当强!

 

由于转换过程实际上遍例序列中所有元素一次，其步骤复杂度为theta(n),n为序列元素个数

(define (union-set set1 set2)
  (if (null? set2)
      set1
      (union-set-good set1 set2 set2)))
(define (union-set-good set1 result set2base)
  (if (null? set1)
      result
      (if (element-of-set? (car set1) set2base)
          (union-set-good (cdr set1) result set2base)
          (union-set-good (cdr set1) (cons (car set1) result) set2base))))

    
(define (element-of-set? x set)
  (cond ((null? set) #f)
        ((equal? x (car set)) #t)
        (else (element-of-set? x (cdr set)))))

;只改进加法部分，乘法类似

(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        ((eq? (car a2) '+) (cons '+ (cons a1 (cdr a2))));though not necessary, I try to reduce the result to a simpler form
        (else (list '+ a1 a2))))
(define (=number? exp num)
  (and (number? exp) (= exp num)))

(define (augend s)
  (if (pair? (cdddr s));check if s havs more than 2 terms
      (cons '+ (cddr s))
      (caddr s)))

 

 

(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)         
         (make-sum
           (make-product (multiplier exp)
                         (deriv (multiplicand exp) var))
           (make-product (deriv (multiplier exp) var)
                         (multiplicand exp))))
        ((exponentiation? exp) ;what we derive here should be limited to certain combination
         (make-product
         (make-product (exponent exp)
                       (make-exponent  (base exp)  (- (exponent exp) 1)))
         (deriv (base exp) var)
         ))
        
        (else
         (error "unknown expression type -- DERIV" exp))))

;data abstraction layer
(define (variable? x) (symbol? x))

(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))

(define (make-sum a1 a2) (list '+ a1 a2))

(define (make-product m1 m2) (list '* m1 m2))

(define (sum? x)
  (and (pair? x) (eq? (car x) '+)))

(define (addend s) (cadr s))

(define (augend s) (caddr s))

(define (product? x)
  (and (pair? x) (eq? (car x) '*)))

(define (multiplier p) (cadr p))

(define (multiplicand p) (caddr p))

;my definition start here
(define (exponentiation? x)
  (and (pair? x) (eq? (car x) '**)))

(define (make-exponent b e)
  (list '** b e))

(define (base e)
  (cadr e))

(define (exponent e)
  (caddr e))

 

sicp课程录像          sicp两位原著作者早期授课的录像

 

---------
In the US, 90% of vitamin C (ascorbic acid) is now from China.

All the US needs to do is piss China off a bit more and they will spike the vitamin C with a deadly Asian flu virus (or other bio-weapon).

As vitamin C is in many food products, almost all 'energy' drinks, 'fruit' drinks, vitamin pills themselves, etc., China could wipe out 75% of the US population this way.

Or that matter, they can easily kill many pets in American through spiking the ingredients they sell that are in virtually every brand of pet food. Oh wait, they already did the test run on that one. And it worked.

How about the death of oak trees in the US and other countries -- traced to a Chinese fungus that US intelligence believes was distributed throughout the US by Chinese agents.

Or Chinese fish introduced into US water systems that have decimated US fish populations. Same as above.

And the list goes on and on.

China is a true menace. 1B+ strong, smart, and totally dedicated to the pursuit of money above all other things. In other words, 100% evil.

Some of the greatest people in history have educated themselves to a large degree using a process known as autodidacticism. This is something that's more easily undertaken these days with the great wealth of online tools available to anyone.

Whether you've gone to college or not, you can learn just about anything these days on your own. Want to learn about the classics? Carpentry and home maintenance? Philosophy or cooking? Chess or computer programming? It's all online, and with a little bit of excitement, you can motivate yourself to learn a subject in a growing number of ways.

Why self-education? Well, besides the obvious reasons of wanting to improve yourself, prepare yourself for success, and just learn as much as you can, self-education offers a few extra benefits: you can learn at your own pace, and in your own way. You can follow your passions, and learn about things that excite you. There's no price for failure, but there's every reward for success.

How do you go about becoming an autodidact? The answer is simple: any way you want. I would suggest you set aside just a little time each day to learn a specific subject, but that really depends on your learning style. Some people learn all in one great rush: they'll stay up late hours for a few days in a row, consuming everything they possibly can about a subject. Others are overwhelmed by an approach like that, and would rather learn a little each day.

However you go about it, here are some of the best tools for the modern autodidact:

1. Wikipedia. A vast repository of great and useful articles, Wikipedia is the autodidact's dream. You could surf it for hours, days on end, or you could use one of many tools to make daily learning a breeze. One of the best is the Articles of the Day feature --sign up to get it in your email box. Another great option that I've tried is making Wikipedia's random page your home page.
   
   
2. Online Courses. Today you can learn from the best colleges and universities, from the comfort of your own home. Just a few of the online offerings: Berkeley, MIT, Carnegie Mellon, Johns Hopkins, Notre Dame.
   
   
3. Chapter a day. Don't have time for books? Read them the easy way: a chapter a day is emailed to you or added to your RSS reader by DailyLit.com, which has a growing selection of free books.
   
   
4. Word a day. Improve your vocabulary by leaps and bounds through the FreeDictionary, which has some great features you can subscribe to,including these RSS feeds: Article of the Day, In the News, and This Day in History.
   
   
5. Take quizzes. One of the most fun ways of learning is through games and quizzes. If you do a quick Google search, you can find quizzes on just about any topic, including math, grammar, the U.S. Constitution ... you name it. Also try flashcards for effective learning.
   
   
6. Art a day. If you'd like to learn about art, one of the best tools is Your Daily Art. Subscribe to the feed, and every day you'll get a famous piece of art, along with some notes to help your contemplation.
   
   
7. Podcasts. Not a fan of heavy reading? Get your knowledge through listening. You can listen to a course while driving, while relaxing in the bath, or while your boss thinks you're working. Just kidding about that last one. Here are just a few of the
   available podcasts: UCLA podcasts, Berkeley on iTunes, Stanford on iTunes, Purdue University Podcasts, University
   Channel (Princeton).
   
   
8. Free ebooks. Of course, there are thousands of great books online, available for free. Read them during your spare time, print them out for bathroom reading ... it doesn't matter how you use them, they're free! Here are some sites to start you out:
   Project Gutenberg, Wikibooks, Free Audio Books, Free Academic Textbooks.
   
   
9. Learn languages. Tons of language courses are available online (BBC languages, FSI Language Courses to name a couple), and you can even learn them through iTunes: Chinese, Arabic, French, German, Italian, Greek and much more.
   
   
10. Wikiversity. A growing number of courses are being offered through a great resource, Wikiversity. Also try BBC Learning.