Posted on 2008-03-20 19:15
dennis 阅读(733)
评论(2) 编辑 收藏 所属分类:
计算机科学与基础
看了javaeye上一个解决约瑟夫环的问题的帖子，就想能不能用scheme来解决。如果采用推导出的数学公式来处理当然很简单了：
(define (joseph n m)
(define (joseph-iter init s)
(if (> init n)
(+ s 1)
(joseph-iter (+ init 1) (remainder (+ s m) init))))
(joseph-iter 2 0))
我想是否可以用一般的模拟算法来实现？也就是模拟一个循环链表，每次删除第m个元素。弄了个比较丑陋的实现：
(define (enumrate-interval low high)
(if (> low high)
'()
(cons low (enumrate-interval (+ low 1) high))))
(define (delete-last list)
(if (eq? (cdr list) '())
'()
(cons (car list) (delete-last (cdr list)))))
(define (joseph-iter init list it)
(let ((m (remainder it (length list))))
(cond ((= m 0) (delete-last list))
((= m 1) (append (cdr list) (reverse init)))
(else
(joseph-iter (cons (car list) init) (cdr list) (- m 1))))))
(define (joseph n m)
(define (joseph-list list m)
(display list)
(newline)
(if (eq? (cdr list) '())
(car list)
(joseph-list (joseph-iter '() list m) m)))
计算（joseph 8 3)的过程如下：
(1 2 3 4 5 6 7 8)
(4 5 6 7 8 1 2)
(7 8 1 2 4 5)
(2 4 5 7 8)
(7 8 2 4)
(4 7 8)
(4 7)
(7)
7
看了这个计算过程就知道我这个方法多糟糕，每次都重新构造列表。不知道看blog的大大们有没有更好的思路？