看了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的大大们有没有更好的思路?
文章转自庄周梦蝶 ,原文发布时间 2008-03-20