2008-03-20

scheme解决约瑟夫环问题

关键字: scheme 约瑟夫环

    看了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

看了这个计算过程就知道我这个方法多糟糕，每次都重新构造列表。不知道牛人们有没有更好的思路来实现模拟算法？

评论
dennis_zane 2008-05-04
嗯，我觉的各位偏离我的我的意思了，我的意思是用单向循环链表的传统方式来解决这个问题，不过已经解决，谢谢。
manbearpig1 2008-05-03
约瑟夫环的有O(1)的解，类似于位运算左移一位，具体数学(concrete maths)第一章有详细证明。
lichray 2008-03-21
用列表实现循环链表然后还随机删除。。。。这效率。。。。
发表评论

您还没有登录，请登录后发表评论

dennis_zane
搜索本博客
存档
最新评论