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

この問題については、ブログで 3 つの解決策とともに説明しています。循環リストを使用するソリューションは次のとおりです。

(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 人がいて、3 人に 1 人が殺されている場合、ヨセフスは 1 から数えて 31 番目の位置で生き残ります。

> (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 に答える