278
scheme解決約瑟夫環問題（續）
sicp的習題3.22，也就是以消息傳遞的風格重新實現隊列，我的解答如下：
(define (make-queue)
(let ((front-ptr '())
(rear-ptr '()))
(define (set-front-ptr! ptr) (set! front-ptr ptr))
(define (set-rear-ptr! ptr) (set! rear-ptr ptr))
(define (empty-queue?) (null? front-ptr))
(define (front-queue)
(if (empty-queue?)
(error "FRONT called with an empty queue")
(car front-ptr)))
(define (insert-queue! item)
(let ((new-pair (cons item '())))
(cond ((empty-queue?)
(set-front-ptr! new-pair)
(set-rear-ptr! new-pair))
(else
(set-cdr! rear-ptr new-pair)
(set-rear-ptr! new-pair)))))
(define (delete-queue!)
(cond ((empty-queue?)
(error "DELETE! called with an empty queue" queue))
(else
(set-front-ptr! (cdr front-ptr)))))
(define (dispatch m)
(cond ((eq? m 'front-queue) (front-queue))
((eq? m 'empty-queue?) (empty-queue?))
((eq? m 'insert-queue!) insert-queue!)
((eq? m 'delete-queue!) delete-queue!)
(else
(error "Unknow method" m))))
dispatch))
(define (front-queue z) (z 'front-queue))
(define (empty-queue? z) (z 'empty-queue?))
(define (insert-queue! z item) ((z 'insert-queue!) item))
(define (delete-queue! z) ((z 'delete-queue!)))
(let ((front-ptr '())
(rear-ptr '()))
(define (set-front-ptr! ptr) (set! front-ptr ptr))
(define (set-rear-ptr! ptr) (set! rear-ptr ptr))
(define (empty-queue?) (null? front-ptr))
(define (front-queue)
(if (empty-queue?)
(error "FRONT called with an empty queue")
(car front-ptr)))
(define (insert-queue! item)
(let ((new-pair (cons item '())))
(cond ((empty-queue?)
(set-front-ptr! new-pair)
(set-rear-ptr! new-pair))
(else
(set-cdr! rear-ptr new-pair)
(set-rear-ptr! new-pair)))))
(define (delete-queue!)
(cond ((empty-queue?)
(error "DELETE! called with an empty queue" queue))
(else
(set-front-ptr! (cdr front-ptr)))))
(define (dispatch m)
(cond ((eq? m 'front-queue) (front-queue))
((eq? m 'empty-queue?) (empty-queue?))
((eq? m 'insert-queue!) insert-queue!)
((eq? m 'delete-queue!) delete-queue!)
(else
(error "Unknow method" m))))
dispatch))
(define (front-queue z) (z 'front-queue))
(define (empty-queue? z) (z 'empty-queue?))
(define (insert-queue! z item) ((z 'insert-queue!) item))
(define (delete-queue! z) ((z 'delete-queue!)))
由此，我才知道自己竟然一直沒有想到，scheme完全可以模擬單向循環鏈表，整整第三章都在講引入賦值帶來的影響，而我卻視而不見。在引入了改變函數後，數據對象已經具有OO的性質，模擬鏈表、隊列、table都變的易如反掌。首先，模擬節點對象，節點是一個序對，包括當前節點編號和下一個節點：
(define (make-node n next) (cons n next))
(define (set-next-node! node next) (set-cdr! node next))
(define (set-node-number! node n) (set-car! node n))
(define (get-number node) (car node))
(define (get-next-node node) (cdr node))
(define (set-next-node! node next) (set-cdr! node next))
(define (set-node-number! node n) (set-car! node n))
(define (get-number node) (car node))
(define (get-next-node node) (cdr node))
有了節點，實現了下單向循環鏈表：
(define (make-cycle-list n)
(let ((head (make-node 1 '())))
(define (make-list current i)
(let ((next-node (make-node (+ i 1) '())))
(cond ((= i n) current)
(else
(set-next-node! current next-node)
(make-list next-node (+ i 1))))))
(set-next-node! (make-list head 1) head)
head))
(let ((head (make-node 1 '())))
(define (make-list current i)
(let ((next-node (make-node (+ i 1) '())))
(cond ((= i n) current)
(else
(set-next-node! current next-node)
(make-list next-node (+ i 1))))))
(set-next-node! (make-list head 1) head)
head))
make-cycle-list生成一個有N個元素的環形鏈表，比如(make-cycle-list 8)的結果如下
#0=(1 2 3 4 5 6 7 8 . #0#)
Drscheme形象地展示了這是一個循環的鏈表。那麼約瑟夫環的問題就簡單了：
(define (josephus-cycle n m)
(let ((head (make-cycle-list n)))
(define (josephus-iter prev current i)
(let ((next-node (get-next-node current)))
(cond ((eq? next-node current) (get-number current))
((= 1 i)
(set-next-node! prev next-node)
(josephus-iter prev next-node m))
(else
(josephus-iter current next-node (- i 1))))))
(josephus-iter head head m)))
(let ((head (make-cycle-list n)))
(define (josephus-iter prev current i)
(let ((next-node (get-next-node current)))
(cond ((eq? next-node current) (get-number current))
((= 1 i)
(set-next-node! prev next-node)
(josephus-iter prev next-node m))
(else
(josephus-iter current next-node (- i 1))))))
(josephus-iter head head m)))
從head節點開始計數，每到m，就將當前節點刪除（通過將前一個節點的next-node設置為current的下一個節點），最後剩下的節點的編號就是答案。
文章轉自莊周夢蝶 ，原文發布時間 2008-04-16
最後更新：2017-05-17 18:01:43