요세푸스 퍼즐에서 주어진 위치에서 "첫 번째 생존자"를 찾는 방법은 무엇입니까?

Question

나는 주어진 위치와 사람의 수를 다음 생존자를 찾고 싶다.

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

마지막 비트를 생존 위치의 정확한 숫자로 바꾸면됩니다. 이 프로그램은 생존자를 찾을 때까지 실행됩니다. 이제는 모든 것이 진위와 거짓의 관점에서이기 때문에 답을 제시하는 방법을 모르겠습니다. 고맙습니다!

Answer 1

알고리즘이 올바르지 않거나 구문 오류가 있습니다. 예를 들어,이 조건은 보통 잘못되었습니다 : (if = #f survives?). Scheme에 if 표현식을 쓰는 방법이 아닙니다. 아마도 (if (equal? (survives? position n) #f) ...)을 의미 할 것입니다. 기본 원리를 올바르게 시작하여 시작하십시오!

Wikipedia에는 Scheme에 작성하기 쉬운 몇 가지 구현과 함께 솔루션에 대한 자세한 설명이 나와 있습니다.

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

Answer 2

나는 그냥 재미를 위해, 여기에 let라는 이름을 사용하여 효율적인 꼬리 재귀 솔루션에 내 걸릴입니다 세 가지 해결책으로 내 blog에서이 문제를 논의하십시오. 여기서 순환에서 사용하는 용액이다 : 예를 들어

(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 사람들이 세프 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)