2

我想在给定的位置和人数之后找到下一个幸存者。

(define renumber
 (lambda (position n)
(if (< position 3)
        (+ position (- n 3))
        (- position 3))))



(define survives?
  (lambda (position n)
    (if (< n 3)
    #t
    (if (= position 3)
        #f
    (survives? (renumber position n) (- n 1))))))


(define first-survivor-after
(lambda (position n)
  (cond ((and (<= n 3)(<= position 3)) null)
        ((or (>= n 3)(>= position 3))(survives? position n)
             (if = #f survives?)
                (survives? (+ 1 position) n)
                "Surviving position"))))

我只需要用幸存位置的确切数字替换最后一位。该程序将运行直到找到幸存者，我只是不知道如何给出这个位置作为答案，因为现在一切都是真假。谢谢！

4

2 回答 2

0

您的算法似乎不正确，并且存在语法错误。例如，这个条件是完全错误的：(if = #f survives?). 这不是您if在 Scheme 中编写表达式的方式 - 也许您的意思是(if (equal? (survives? position n) #f) ...). 从正确的基础开始！

在Wikipedia中，您会找到对解决方案的详细解释，以及一些实现，它们应该很容易用 Scheme 编写。只是为了好玩，这是我对一个有效的尾递归解决方案的看法，使用命名let：

(define (first-survivor-after position n)
  (let loop ([i   1]
             [acc 0])
    (if (> i n)
        (add1 acc)
        (loop (add1 i)
              (modulo (+ acc position) i)))))

或者等效地，使用辅助过程的非尾递归版本：

(define (first-survivor-after position n)
  (define (loop i)
    (if (= i 1)
        0
        (modulo (+ (loop (sub1 i)) position) i)))
  (add1 (loop n)))
于 2013-09-21T13:04:05.057 回答
0

我在我的博客上讨论了这个问题，提供了三种解决方案。这是一个使用循环列表的解决方案：

(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)))

例如，圈子里有 41 人，每三分之一人被杀，约瑟夫斯存活在第 31 位，从 1 开始计数：

> (josephus 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-09-21T14:58:28.027 回答