1

约瑟夫斯问题的这种实现在哪里不足？对于那些不熟悉约瑟夫斯问题的人，我们的目标是从循环链表中删除每 3 个条目，直到只剩下一个。在此示例中，我将删除每个“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))))))

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

4

2 回答 2

2

您通过创建一个列表并从中删除元素（“杀死”人）来太从字面上理解算法。一个更简单的解决方案是使用算术运算来模拟问题，这是一个可能的实现，改编自我自己之前的答案：

(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

Wikipedia 提供了有关此问题的可能解决方案的有趣讨论，我的解决方案在将其转换为尾递归后调整了所示的简单 python 函数。

于 2013-12-05T16:24:15.070 回答
1

我在我的博客上给出了三个解决方案。最字面的版本以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功能来自我的Standard Prelude；它返回从 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 开始计数：

(约瑟夫斯3 41 3) (2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15 30)

您也可以在我的博客中欣赏其他两个版本。

于 2013-12-05T16:35:44.407 回答