Josephus 순열을위한 강사의 출력을 재현 할 수 없습니다.

Question

데이터 구조 클래스에있어 강사가 제공 한 예제 데이터를 재현 할 수 없습니다. 문제는 사용자가 제공 한 회원 수, 단계 간격 및 시작 위치와 관련된 고전적인 요세푸스 문제입니다.

구체적으로 말하자면, 23 세부터 99 세까지 5 세가되는 사람은 마지막 사람으로 서 84 명을 남겨 두어야한다고 들었습니다.

내가 가지고 올 : 65 내가 도망 다시이 생산 (23)의 간격으로 5에서 시작, 99명되었을 수도 입력을 생각 : (42)

내 할당 솔루션은 원형 연결리스트를 포함, 그러나이 코드는 모든 경우에 동일한 출력을 생성합니다.

#include <stdio.h> 

int josephus(int n, long k) 
{ 
    if (n == 1) 
    return 1; 
    else 
    /* The position returned by josephus(n - 1, k) is adjusted because the 
    *  recursive call josephus(n - 1, k) considers the original position 
    *    k%n + 1 as position 1 */ 
return (josephus(n - 1, k) + k-1) % n + 1; 
} 

int main() 
{ 
int n = 99; 
int k = 23; 
printf("The chosen place is %d\n", josephus(n, k) + 5); 
return 0; 
} 

다시 한번 감사드립니다.

Answer 1

LaFore는 한 발짝 내딛는 것으로 계산됩니다. 즉, 1시에 시작하면 2로 계산하면 먼저 사람 4가 죽습니다. 본문에는 한 가지 예가 들어 있습니다. 이것은 직관적이지 않으며 LaFore는 이런 식으로 계산하는 유일한 저자 인 것처럼 보입니다.