조세 프 링 문제 (동그라미 에 마지막 으로 남 은 숫자) 의 수학 추리 해법

문제 설명
조세 프 링 (Josephuse) 은 수학의 응용 문제 이다. n 개인 (번호 1, 2, 3. n 으로 각각 표시) 이 원탁 주위 에 둘 러 앉 아 있다.번호 가 k 인 사람 부터 번 호 를 매기 고 m 까지 센 사람 이 나 옵 니 다.그의 다음 사람 은 또 1 부터 숫자 를 매기 기 시 작 했 고 m 까지 센 그 사람 이 또 나 왔 다.원탁 주위 사람들 이 모두 나 올 때 까지 이 규칙 을 반복 한다.
가정 하 다
번호 가 0 부터 시작 된다 고 가정 하고 매번 m 번 째 노드 를 삭제 합 니 다.
예 를 들 어 (0, 1, 2, 3, 4) (0, 1, 2, 3, 4) (0, 1, 2, 3, 4) 이 다섯 개의 숫자 는 원 환 을 구성 하고 매번 세 번 째 노드 를 삭제 합 니 다.첫 번 째 로 삭 제 된 것 은 222 이 고 링 이 (0, 1, 3, 4) (0, 1, 3, 4) (0, 1, 3, 4) 로 바 뀌 었 다.삭 제 된 노드 의 다음 단계 부터 노드 3 부터 번 호 를 알 리 는 것 이다. 이때 서열 은 (3, 4, 0, 1) (3, 4, 0, 1) (3, 4, 0, 1) (3, 4, 0, 1) 로 볼 수 있 고 세 번 째 노드 를 삭제 하면 0 이다.이런 식 으로 보면 삭제 순 서 는 2 → 0 → 4 → 12 \ \ to 0 \ \ to 4 \ \ to 1 2 → 0 → 4 → 1 이 고 마지막 에 남 은 숫자 는 3, 3 이다.
흔히 볼 수 있 는 두 가지 해법.

링크 데이터 구조 모방 링 을 사용한다.

수학 추 리 는 전달 공식 을 찾는다.

수학 추리 해법
이 절 은 주로 전달 공식 으로 해결 하 는 방법 을 소개 한다.

n 개의 숫자 (0, 1,.., n - 1) (0, 1, n - 1) (0, 1, n - 1) 에서 m 번 째 숫자 를 삭제 하 는 문제 에 대해 마지막 으로 남 은 숫자 는 f (n, m) f (n, m) f (n, m) f (n, m) 로 나 타 낼 수 있다.f (n, m) f (n, m) f (n, m) 는 이 문제 의 풀이 이 고 숫자 입 니 다.

첫 번 째 숫자 를 삭제 하고 삭 제 된 것 은 반드시 (m - 1)% n (m - 1) \% n (m - 1)% n 으로 (m - 1)% n (m - 1) \% n (m - 1)% n 을 k k k k k 로 기록 합 니 다.

이때 서열 은 (k + 1, k + 2,..., n - 1, 0, 1,...........................................................

한 노드 를 삭제 하면 문제 의 규모 가 11 로 줄어든다.마지막 으로 남 은 그 숫자 는 f (n - 1, m) f (n - 1, m) f (n - 1, m) 로 직접 표시 할 수 없다. 이때 서열 은 0 - 0 에서 시작 되 는 것 이 아니 라 함수 f f f f 가 만족 하지 않 기 때문이다.우 리 는 이 숫자 를 다른 함수 로 표시 할 수 있다. 예 를 들 어 g (n - 1, m) g (n - 1, m) g (n - 1, m).

마지막 에 남 은 그 숫자 는 고정 되 어 있 기 때문에 f (n, m) = g (n - 1, m) f (n, m) = g (n - 1, m) f (n, m) = g (n - 1, m).

우 리 는 서열 (k + 1, k + 1, k + 2,..., n - 1, 0, 1, 1,...................................................................................................................................................... − 1, m) f (n - 1, m) f(n - 1, m) 간 의 전달 관 계 는 다음 과 같다. k + 1   →    0 k+1 \ \ \to \ \ 0 k+1  →  0 k + 2    →    1 k+2 \ \ \to \ \ 1 k+2  →  1 … n − 1    →    n − k − 2 n-1 \ \ \to \ \ n-k-2 n−1  →  n−k−2 0           →    n − k − 1 0 \ \ \ \ \ \ \ \ \ \to \ \ n-k-1 0         →  n−k−1 1           →    n − k 1 \ \ \ \ \ \ \ \ \ \to \ \ n-k 1         →  n−k … k − 1    →    n − 2 k-1 \ \ \to \ \ n-2 k−1  →  n - 2 이때 서열 은 0 에서 시작 하여 이 매 핑 관 계 를 p (x) = (x - k - 1)% n p (x) = (x - k - 1) \ \% n p (x) = (x - k - 1)% n, p (n - 1, m) = f (n - 1, m) p (g (n - 1, m) = f (n - 1, m) p (g - 1, m) p (g (n - 1, m) = f (n - 1, m) = f (n - 1, m) 로 정의 한다.

이 비 비 비 비 비 비 비 비 비 비 비 비 비 비 비 비 비 는 p − 1 (x) = (x + k + 1)% n p ^ {- 1} (x) = (x + k + 1 + 1)% n p (n - 1, m) g (n - 1, m) g (n - 1, m) g (n - 1, m) = p − 1 (f (n - 1, m) = (f (n - 1, m) = (f (n - 1, m) (f (n - 1, m) = (f (n - 1, m) - 1, m) = (f (n - 1, m) - 1, m) (f (n - 1, m) - 1, m) = (f (n - 1, m) - 1, m)) = (f + k + 1) \ \% n p - 1 (f (n - 1, m) = (f (n - 1, m) + k + 1)% n.

k = (m - 1)% n k = (m - 1) \ \% n k = (m - 1)% n 을 전달 공식 에 대 입하 고 f (n, m) = g (n - 1, m) = (f (n - 1, m)% n f (n, m) = g (n - 1, m) = (f (n - 1, m) + m) \% n f (n, m) = g (n - 1, m) = (f (n - 1, m)

n 이 1 인 상황 을 고려 하면 이때 서열 은 1 개의 노드 만 있 기 때문에 마지막 에 남 은 숫자 는 반드시 0 이다.

위의 분석 을 통 해 우 리 는 이미 완전한 전달 공식 을 얻 을 수 있다.
               f ( n , m ) = 0 ,    n = 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ f(n,m) = 0, \ \ n = 1               f(n,m)=0,  n=1                f ( n , m ) = ( f ( n − 1 , m ) + m ) % n    ,   n > 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ f(n,m) = (f(n-1,m)+m)\%n \ \ ,\ n \gt 1               f(n,m)=(f(n−1,m)+m)%n  , n>1
코드 구현
전달 공식 을 얻 은 후 순환 이나 재 귀 를 사용 하 는 것 은 간단 하 다. 다음은 에서 C + + 이 루어 진 순환 해법 (쓰기 가 귀찮다 ~) 이다.

int lastRemaining(int n, int m){
	if(n < 1 || m < 1)
		return -1;
	
	int last = 0;
	for(int i = 2; i <= n; i++){
		last = (last + m) % i;
	}
	return last;
}

본문 이 끝 났 으 니 댓 글 토론 을 환영 합 니 다.