two-one-of youtube 视频
这章视频还是可以看的，能看懂, 在画cross product table的时候多留意，不行就按暂停
这里小编想用另外一个例子讲一下
说我们想按从小到达 merge 两个sorted list l1 和 l2
l1 l2
merge empty (list 1 3 5) -> (list 1 3 5)
merge (list 0 2 4) empty -> (list 0 2 4)
merge (list 0 2 4) (list 1 3) -> (list 0 1 2 3 4)
先画个table
l2
|empty | (cons Number ListOfNumber)
____________________________________________________________
empty | (1) | (2)
l1 __________________________ | _______________________________________________
(cons Number ListOfNumber) | (3) | (4)
| |
对于每一个case我们举例分析一下
l1 l2
case1: empty empty -> empty (l2)
case2: empty (list 1 3 5) -> (list 1 3 5) (l2)
case3: (list 0 2 4) empty -> (list 0 2 4) (l1)
case4: (list 0 2 4) (list 1 3 5) -> (list 0 1 2 3 4)(recuriosn)
把结果填回去
l2
|empty | (cons Number ListOfNumber)
____________________________________________________________
empty | l2 | l2
l1 __________________________ | _______________________________________________
(cons Number ListOfNumber) | l1 | recursion(put the else part code back here)
| |
case (1) 和 (2)结果是一样的，所以可以合并
l2
|empty | (cons Number ListOfNumber)
____________________________________________________________
empty | l2
l1 __________________________ | _______________________________________________
(cons Number ListOfNumber) | l1 | recursion(put the else part code back here)
| |
可以写merge了
(check-expect (merge empty empty) empty)
(check-expect (merge empty (list 1 3 5)) (list 1 3 5))
(check-expect (merge (list 0 2 4) empty) (list 0 2 4))
(check-expect (merge (list 0 2 4) (list 1 3)) (list 0 1 2 3 4))
(define (merge l1 l2)
(cond [(empty? l1) l2] ;;case (1) and (2)
[(empty? l2) l1] ;;case(3)
[else ;;case(4)
(if (<= (first l1) (first l2))
(cons (first l1)
(merge (rest l1) l2))
(cons (first l2)
(merge l1 (rest l2))))]))
以(merge (list 1 4) (list 2 3))看一下过程
(merge (list 1 4) (list 2 3)) ;; 1 < 4
= (cons 1
(merge (list 4) (list 2 3))) ;; 4 > 2
=(cons 1
(cons 2
(merge (list 4) (list 3)))) ;; 4 > 3
=(cons 1
(cons 2
(cons 3
(merge (list 4) ())))) ;; l2 is empty
=(cons 1
(cons 2
(cons 3
(list 4))))
=(list 1 2 3 4)