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!)))         由此，我才知道自己竟然一直没有想到，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 (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))     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)))

    从head节点开始计数，每到m，就将当前节点删除（通过将前一个节点的next-node设置为current的下一个节点），最后剩下的节点的编号就是答案。

文章转自庄周梦蝶  ，原文发布时间 2008-04-16