约瑟夫斯计划

Question

约瑟夫斯问题的实施有何不足？对于那些不熟悉约瑟夫斯问题的人来说，目标是删除循环链接列表中的每三个条目，直到只剩下一个。在本例中，我将删除每个"mth“值。

(define (joseph lst)  
(let ((m (+ 1 (random (length lst)))))
(define (joseph-h i xlst mlst)
 (cond ((<= (length xlst) 1) xlst)
       ((null? (cdr mlst)) 
        (joseph-h i xlst xlst))
       ((= i m) 
        (joseph-h 1 (delete (car mlst) xlst) (cdr mlst)))
       (else 
        (joseph-h (+ i 1) xlst (cdr mlst)))))
 (joseph-h 0 lst lst)))

 (joseph (list 1 2 3 4 5 6 7))


 (define (delete v lst)
   (cond ((= v (car lst)) 
          (cdr lst))
         (else
          (cons (car lst) (delete v (cdr lst)))))) 

我总是以名单上的最后一个数字作为答案。我知道这是不对的。

Answer 1

通过创建一个列表并从其中删除元素(“杀死”人)，你就把算法看得太简单了。一个更简单的解决方案是使用算术操作来建模这个问题，下面是一个可能的实现，它来自于我自己的先前的回答

(define (joseph n k)
  (let loop ([i   1]
             [acc 0])
    (if (> i n)
        (add1 acc)
        (loop (add1 i)
              (modulo (+ acc k) i)))))

例如，要查看在杀死每三个人之后在列表'(1 2 3 4 5 6 7)中幸存的位置，请执行以下操作：

(joseph 7 3)
=> 4

维基百科提供了一个关于这个问题的可能解决方案的有趣的讨论，我的解决方案适应了简单的python函数，在将它转换成尾递归之后。

Answer 2

我在我的博客给出了三个解决方案。最直接的版本按m的步骤从n项列表中删除，将列表表示为循环列表：

(define (cycle xs)
  (set-cdr! (last-pair xs) xs) xs)

(define (josephus3 n m)
  (let loop ((k (- m 1)) (alive (cycle (range 0 n))) (dead '()))
    (cond ((= (car alive) (cadr alive))
            (reverse (cons (car alive) dead)))
          ((= k 1)
            (let ((dead (cons (cadr alive) dead)))
              (set-cdr! alive (cddr alive))
              (loop (- m 1) (cdr alive) dead)))

这是通过从alive列表中实际删除被删除的元素并将它们放到dead列表中来进行删除的。range函数来自于我的标准前奏；它将整数从0返回到n-1

(define (range first past . step)
  (let* ((xs '()) (f first) (p past)
         (s (cond ((pair? step) (car step))
                  ((< f p) 1) (else -1)))
         (le? (if (< 0 s) <= >=)))
    (do ((x f (+ x s))) ((le? p x) (reverse xs))
      (set! xs (cons x xs)))))

最初的约瑟夫斯问题在3步中杀死了41人，留下第31个人作为幸存者，从1开始计算：

(josephus3 41 3) (2 5 8 11 14 17 20 23 26 32 32 38 0 4 9 13 22 27 31 36 6 12 25 33 39 7 16 16 37 10 24 1 21 3 34 15 30)

您可能还会喜欢我的博客的其他两个版本。